/
cmce_poly.cpp
176 lines (142 loc) · 6.02 KB
/
cmce_poly.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
/*
* Classic McEliece Polynomials
* Based on the public domain reference implementation by the designers
* (https://classic.mceliece.org/impl.html - released in Oct 2022 for NISTPQC-R4)
*
* (C) 2023 Jack Lloyd
* 2023,2024 Fabian Albert, Amos Treiber - Rohde & Schwarz Cybersecurity
*
* Botan is released under the Simplified BSD License (see license.txt)
**/
#include <botan/internal/cmce_poly.h>
#include <botan/internal/ct_utils.h>
#include <botan/internal/stl_util.h>
namespace Botan {
namespace {
/**
* @brief loads @p bytes into a GF_Elem vector in Little Endian.
*
* Replaces load_le<GF_Elem> as it cannot be compiled on Big Endian architectures
*
* @param bytes input bytes
* @return The vector of GF_Elem elements
*/
std::vector<GF_Elem> load_le_gf_vec(std::span<const uint8_t> bytes) {
std::vector<GF_Elem> result;
BufferSlicer bs(bytes);
result.reserve(bytes.size() / sizeof(GF_Elem));
for(size_t i = 0; i < bytes.size() / sizeof(GF_Elem); ++i) {
result.emplace_back(load_le<uint16_t>(bs.take<sizeof(GF_Elem)>()));
}
return result;
}
} // namespace
Classic_McEliece_GF Classic_McEliece_Polynomial::operator()(Classic_McEliece_GF a) const {
BOTAN_ASSERT(a.modulus() == coef_at(0).modulus(), "Galois fields match");
Classic_McEliece_GF r(GF_Elem(0), a.modulus());
for(auto it = m_coef.rbegin(); it != m_coef.rend(); ++it) {
r *= a;
r += *it;
}
return r;
}
Classic_McEliece_Polynomial Classic_McEliece_Polynomial_Ring::multiply(const Classic_McEliece_Polynomial& a,
const Classic_McEliece_Polynomial& b) const {
std::vector<Classic_McEliece_GF> prod(m_t * 2 - 1, {GF_Elem(0), m_poly_f});
for(size_t i = 0; i < m_t; ++i) {
for(size_t j = 0; j < m_t; ++j) {
prod.at(i + j) += (a.coef_at(i) * b.coef_at(j));
}
}
for(size_t i = (m_t - 1) * 2; i >= m_t; --i) {
for(auto& [idx, coef] : m_position_map) {
prod.at(i - m_t + idx) += coef * prod.at(i);
}
}
prod.erase(prod.begin() + m_t, prod.end());
return Classic_McEliece_Polynomial(std::move(prod));
}
Classic_McEliece_Polynomial Classic_McEliece_Polynomial_Ring::create_element_from_bytes(
std::span<const uint8_t> bytes) const {
BOTAN_ARG_CHECK(bytes.size() == m_t * 2, "Correct input size");
auto coef = load_le_gf_vec(bytes);
return create_element_from_coef(coef);
}
Classic_McEliece_Polynomial Classic_McEliece_Polynomial_Ring::create_element_from_coef(
const std::vector<GF_Elem>& coeff_vec) const {
std::vector<Classic_McEliece_GF> coeff_vec_gf;
GF_Elem coeff_mask = GF_Elem((uint16_t(1) << Classic_McEliece_GF::log_q_from_mod(m_poly_f)) - 1);
std::transform(coeff_vec.begin(), coeff_vec.end(), std::back_inserter(coeff_vec_gf), [&](auto& coeff) {
return Classic_McEliece_GF(coeff & coeff_mask, m_poly_f);
});
return Classic_McEliece_Polynomial(coeff_vec_gf);
}
bool operator==(const Classic_McEliece_Polynomial_Ring::Big_F_Coefficient& lhs,
const Classic_McEliece_Polynomial_Ring::Big_F_Coefficient& rhs) {
return lhs.coeff == rhs.coeff && lhs.idx == rhs.idx;
}
std::optional<Classic_McEliece_Minimal_Polynomial> Classic_McEliece_Polynomial_Ring::compute_minimal_polynomial(
std::span<const uint8_t> seed) const {
auto polynomial = create_element_from_bytes(seed);
std::vector<Classic_McEliece_Polynomial> mat;
mat.push_back(create_element_from_coef(concat_as<std::vector<GF_Elem>>(
std::vector<GF_Elem>{GF_Elem(1)}, std::vector<GF_Elem>(degree() - 1, GF_Elem(0)))));
mat.push_back(polynomial);
for(size_t j = 2; j <= degree(); ++j) {
mat.push_back(multiply(mat.at(j - 1), polynomial));
}
// Gaussian
for(size_t j = 0; j < degree(); ++j) {
for(size_t k = j + 1; k < degree(); ++k) {
auto cond = GF_Mask::is_zero(mat.at(j).coef_at(j));
for(size_t c = j; c < degree() + 1; ++c) {
mat.at(c).coef_at(j) += cond.if_set_return(mat.at(c).coef_at(k));
}
}
if(mat.at(j).coef_at(j).is_zero()) {
// Fail if not systematic.
return std::nullopt;
}
auto inv = mat.at(j).coef_at(j).inv();
for(size_t c = j; c < degree() + 1; ++c) {
mat.at(c).coef_at(j) *= inv;
}
for(size_t k = 0; k < degree(); ++k) {
if(k != j) {
const auto t = mat.at(j).coef_at(k);
for(size_t c = j; c < degree() + 1; ++c) {
mat.at(c).coef_at(k) += mat.at(c).coef_at(j) * t;
}
}
}
}
auto minimal_poly_coeffs = mat.at(degree()).coef();
// Add coefficient 1 since polynomial is monic
minimal_poly_coeffs.emplace_back(GF_Elem(1), poly_f());
return Classic_McEliece_Minimal_Polynomial(std::move(minimal_poly_coeffs));
}
secure_vector<uint8_t> Classic_McEliece_Minimal_Polynomial::serialize() const {
BOTAN_ASSERT_NOMSG(!coef().empty());
auto& all_coeffs = coef();
// Store all except coef for monomial x^t since polynomial is monic (ISO Spec Section 9.2.9)
auto coeffs_to_store = std::span(all_coeffs).first(all_coeffs.size() - 1);
secure_vector<uint8_t> bytes(sizeof(uint16_t) * coeffs_to_store.size());
BufferStuffer bytes_stuf(bytes);
for(auto& coef : coeffs_to_store) {
store_le(bytes_stuf.next<sizeof(GF_Elem)>(), coef.elem().get());
}
BOTAN_ASSERT_NOMSG(bytes_stuf.full());
return bytes;
}
Classic_McEliece_Minimal_Polynomial Classic_McEliece_Minimal_Polynomial::from_bytes(std::span<const uint8_t> bytes,
GF_Mod poly_f) {
BOTAN_ASSERT_NOMSG(bytes.size() % 2 == 0);
auto coef_vec = load_le_gf_vec(bytes);
std::vector<Classic_McEliece_GF> coeff_vec_gf;
std::transform(coef_vec.begin(), coef_vec.end(), std::back_inserter(coeff_vec_gf), [poly_f](auto& coeff) {
return Classic_McEliece_GF(coeff, poly_f);
});
coeff_vec_gf.emplace_back(GF_Elem(1), poly_f); // x^t as polynomial is monic
return Classic_McEliece_Minimal_Polynomial(coeff_vec_gf);
}
} // namespace Botan