Botan 3.9.0
Crypto and TLS for C&
code_based_key_gen.cpp
Go to the documentation of this file.
1/*
2 * (C) Copyright Projet SECRET, INRIA, Rocquencourt
3 * (C) Bhaskar Biswas and Nicolas Sendrier
4 *
5 * (C) 2014 cryptosource GmbH
6 * (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
7 * (C) 2015 Jack Lloyd
8 *
9 * Botan is released under the Simplified BSD License (see license.txt)
10 *
11 */
12
13#include <botan/mceliece.h>
14
15#include <botan/internal/code_based_util.h>
16#include <botan/internal/loadstor.h>
17#include <botan/internal/mce_internal.h>
18#include <botan/internal/polyn_gf2m.h>
19
20namespace Botan {
21
22namespace {
23
24class binary_matrix final {
25 public:
26 binary_matrix(size_t m_rown, size_t m_coln);
27
28 void row_xor(size_t a, size_t b);
29 secure_vector<size_t> row_reduced_echelon_form();
30
31 /**
32 * return the coefficient out of F_2
33 */
34 uint32_t coef(size_t i, size_t j) { return (m_elem[(i)*m_rwdcnt + (j) / 32] >> (j % 32)) & 1; }
35
36 void set_coef_to_one(size_t i, size_t j) {
37 m_elem[(i)*m_rwdcnt + (j) / 32] |= (static_cast<uint32_t>(1) << ((j) % 32));
38 }
39
40 void toggle_coeff(size_t i, size_t j) {
41 m_elem[(i)*m_rwdcnt + (j) / 32] ^= (static_cast<uint32_t>(1) << ((j) % 32));
42 }
43
44 size_t rows() const { return m_rown; }
45
46 size_t columns() const { return m_coln; }
47
48 const std::vector<uint32_t>& elem() const { return m_elem; }
49
50 private:
51 size_t m_rown; // number of rows.
52 size_t m_coln; // number of columns.
53 size_t m_rwdcnt; // number of words in a row
54 std::vector<uint32_t> m_elem;
55};
56
57binary_matrix::binary_matrix(size_t rown, size_t coln) : m_rown(rown), m_coln(coln), m_rwdcnt(1 + ((m_coln - 1) / 32)) {
58 m_elem = std::vector<uint32_t>(m_rown * m_rwdcnt);
59}
60
61void binary_matrix::row_xor(size_t a, size_t b) {
62 for(size_t i = 0; i != m_rwdcnt; i++) {
63 m_elem[a * m_rwdcnt + i] ^= m_elem[b * m_rwdcnt + i];
64 }
65}
66
67//the matrix is reduced from LSB...(from right)
68secure_vector<size_t> binary_matrix::row_reduced_echelon_form() {
69 secure_vector<size_t> perm(m_coln);
70 for(size_t i = 0; i != m_coln; i++) {
71 perm[i] = i; // initialize permutation.
72 }
73
74 uint32_t failcnt = 0;
75
76 size_t max = m_coln - 1;
77 for(size_t i = 0; i != m_rown; i++, max--) {
78 bool found_row = false;
79
80 for(size_t j = i; !found_row && j != m_rown; j++) {
81 if(coef(j, max) > 0) {
82 if(i != j) //not needed as ith row is 0 and jth row is 1.
83 {
84 row_xor(i, j); //xor to the row.(swap)?
85 }
86
87 found_row = true;
88 }
89 }
90
91 //if no row with a 1 found then swap last column and the column with no 1 down.
92 if(!found_row) {
93 perm[m_coln - m_rown - 1 - failcnt] = static_cast<int>(max);
94 failcnt++;
95 if(max == 0) {
96 perm.clear();
97 }
98 i--;
99 } else {
100 perm[i + m_coln - m_rown] = max;
101 for(size_t j = i + 1; j < m_rown; j++) //fill the column downwards with 0's
102 {
103 if(coef(j, max) > 0) {
104 row_xor(j, i); //check the arg. order.
105 }
106 }
107
108 //fill the column with 0's upwards too.
109 for(size_t j = i; j != 0; --j) {
110 if(coef(j - 1, max) > 0) {
111 row_xor(j - 1, i);
112 }
113 }
114 }
115 } //end for(i)
116 return perm;
117}
118
119void randomize_support(std::vector<gf2m>& L, RandomNumberGenerator& rng) {
120 for(size_t i = 0; i != L.size(); ++i) {
121 gf2m rnd = random_gf2m(rng);
122
123 // no rejection sampling, but for useful code-based parameters with n <= 13 this seem tolerable
124 std::swap(L[i], L[rnd % L.size()]);
125 }
126}
127
128std::unique_ptr<binary_matrix> generate_R(
129 std::vector<gf2m>& L, polyn_gf2m* g, const GF2m_Field& sp_field, size_t code_length, size_t t) {
130 //L- Support
131 //t- Number of errors
132 //n- Length of the Goppa code
133 //m- The extension degree of the GF
134 //g- The generator polynomial.
135
136 const size_t r = t * sp_field.get_extension_degree();
137
138 binary_matrix H(r, code_length);
139
140 for(size_t i = 0; i != code_length; i++) {
141 gf2m x = g->eval(lex_to_gray(L[i])); //evaluate the polynomial at the point L[i].
142 x = sp_field.gf_inv(x);
143 gf2m y = x;
144 for(size_t j = 0; j < t; j++) {
145 for(size_t k = 0; k < sp_field.get_extension_degree(); k++) {
146 if((y & (1 << k)) != 0) {
147 //the co-eff. are set in 2^0,...,2^11 ; 2^0,...,2^11 format along the rows/cols?
148 H.set_coef_to_one(j * sp_field.get_extension_degree() + k, i);
149 }
150 }
151 y = sp_field.gf_mul(y, lex_to_gray(L[i]));
152 }
153 } //The H matrix is fed.
154
155 secure_vector<size_t> perm = H.row_reduced_echelon_form();
156 if(perm.empty()) {
157 throw Invalid_State("McEliece keygen failed - could not bring matrix to row reduced echelon form");
158 }
159
160 auto result = std::make_unique<binary_matrix>(code_length - r, r);
161 for(size_t i = 0; i < result->rows(); ++i) {
162 for(size_t j = 0; j < result->columns(); ++j) {
163 if(H.coef(j, perm[i]) > 0) {
164 result->toggle_coeff(i, j);
165 }
166 }
167 }
168
169 std::vector<gf2m> Laux(code_length);
170 for(size_t i = 0; i < code_length; ++i) {
171 Laux[i] = L[perm[i]];
172 }
173
174 for(size_t i = 0; i < code_length; ++i) {
175 L[i] = Laux[i];
176 }
177 return result;
178}
179} // namespace
180
181McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator& rng, size_t ext_deg, size_t code_length, size_t t) {
182 const size_t codimension = t * ext_deg;
183
184 if(code_length <= codimension) {
185 throw Invalid_Argument("invalid McEliece parameters");
186 }
187
188 auto sp_field = std::make_shared<GF2m_Field>(ext_deg);
189
190 //pick the support.........
191 std::vector<gf2m> L(code_length);
192
193 for(size_t i = 0; i != L.size(); i++) {
194 L[i] = static_cast<gf2m>(i);
195 }
196 randomize_support(L, rng);
197 polyn_gf2m g(sp_field); // create as zero
198
199 bool success = false;
200 std::unique_ptr<binary_matrix> R;
201
202 // NOLINTNEXTLINE(*-avoid-do-while)
203 do {
204 // create a random irreducible polynomial
205 g = polyn_gf2m(t, rng, sp_field);
206
207 try {
208 R = generate_R(L, &g, *sp_field, code_length, t);
209 success = true;
210 } catch(const Invalid_State&) {}
211 } while(!success);
212
213 std::vector<polyn_gf2m> sqrtmod = polyn_gf2m::sqrt_mod_init(g);
214 std::vector<polyn_gf2m> F = syndrome_init(g, L, static_cast<int>(code_length));
215
216 // Each F[i] is the (precomputed) syndrome of the error vector with
217 // a single '1' in i-th position.
218 // We do not store the F[i] as polynomials of degree t , but
219 // as binary vectors of length ext_deg * t (this will
220 // speed up the syndrome computation)
221 //
222 const size_t co32 = bit_size_to_32bit_size(codimension);
223 std::vector<uint32_t> H(co32 * code_length);
224 uint32_t* sk = H.data();
225 for(size_t i = 0; i < code_length; ++i) {
226 for(size_t l = 0; l < t; ++l) {
227 const size_t k = (l * ext_deg) / 32;
228 const size_t j = (l * ext_deg) % 32;
229 sk[k] ^= static_cast<uint32_t>(F[i].get_coef(l)) << j;
230 if(j + ext_deg > 32) {
231 if(j > 0) {
232 sk[k + 1] ^= F[i].get_coef(l) >> (32 - j);
233 }
234 }
235 }
236 sk += co32;
237 }
238
239 // We need the support L for decoding (decryption). In fact the
240 // inverse is needed
241
242 std::vector<gf2m> Linv(code_length);
243 for(size_t i = 0; i != Linv.size(); ++i) {
244 Linv[L[i]] = static_cast<gf2m>(i);
245 }
246 std::vector<uint8_t> pubmat(R->elem().size() * 4);
247 for(size_t i = 0; i < R->elem().size(); i++) {
248 store_le(R->elem()[i], &pubmat[i * 4]);
249 }
250
251 return McEliece_PrivateKey(g, H, sqrtmod, Linv, pubmat);
252}
253
254} // namespace Botan
static std::vector< polyn_gf2m > sqrt_mod_init(const polyn_gf2m &g)
gf2m lex_to_gray(gf2m lex)
std::vector< polyn_gf2m > syndrome_init(const polyn_gf2m &generator, const std::vector< gf2m > &support, int n)
McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator &rng, size_t ext_deg, size_t code_length, size_t t)
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:736
gf2m random_gf2m(RandomNumberGenerator &rng)
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:69
size_t bit_size_to_32bit_size(size_t bit_size)
uint16_t gf2m