Botan 3.0.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#include <botan/internal/mce_internal.h>
15#include <botan/internal/code_based_util.h>
16#include <botan/internal/loadstor.h>
17#include <botan/internal/polyn_gf2m.h>
18
19namespace Botan {
20
21namespace {
22
23class binary_matrix final
24 {
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)
35 {
36 return (m_elem[(i) * m_rwdcnt + (j) / 32] >> (j % 32)) & 1;
37 }
38
39 void set_coef_to_one(size_t i, size_t j)
40 {
41 m_elem[(i) * m_rwdcnt + (j) / 32] |= (static_cast<uint32_t>(1) << ((j) % 32)) ;
42 }
43
44 void toggle_coeff(size_t i, size_t j)
45 {
46 m_elem[(i) * m_rwdcnt + (j) / 32] ^= (static_cast<uint32_t>(1) << ((j) % 32)) ;
47 }
48
49 size_t rows() const { return m_rown; }
50
51 size_t columns() const { return m_coln; }
52
53 const std::vector<uint32_t>& elem() const { return m_elem; }
54
55 private:
56 size_t m_rown; // number of rows.
57 size_t m_coln; // number of columns.
58 size_t m_rwdcnt; // number of words in a row
59 std::vector<uint32_t> m_elem;
60 };
61
62binary_matrix::binary_matrix(size_t rown, size_t coln)
63 {
64 m_coln = coln;
65 m_rown = rown;
66 m_rwdcnt = 1 + ((m_coln - 1) / 32);
67 m_elem = std::vector<uint32_t>(m_rown * m_rwdcnt);
68 }
69
70void binary_matrix::row_xor(size_t a, size_t b)
71 {
72 for(size_t i = 0; i != m_rwdcnt; i++)
73 {
74 m_elem[a*m_rwdcnt+i] ^= m_elem[b*m_rwdcnt+i];
75 }
76 }
77
78//the matrix is reduced from LSB...(from right)
79secure_vector<size_t> binary_matrix::row_reduced_echelon_form()
80 {
81 secure_vector<size_t> perm(m_coln);
82 for(size_t i = 0; i != m_coln; i++)
83 {
84 perm[i] = i; // initialize permutation.
85 }
86
87 uint32_t failcnt = 0;
88
89 size_t max = m_coln - 1;
90 for(size_t i = 0; i != m_rown; i++, max--)
91 {
92 bool found_row = false;
93
94 for(size_t j = i; !found_row && j != m_rown; j++)
95 {
96 if(coef(j, max))
97 {
98 if(i != j) //not needed as ith row is 0 and jth row is 1.
99 {
100 row_xor(i, j);//xor to the row.(swap)?
101 }
102
103 found_row = true;
104 }
105 }
106
107 //if no row with a 1 found then swap last column and the column with no 1 down.
108 if(!found_row)
109 {
110 perm[m_coln - m_rown - 1 - failcnt] = static_cast<int>(max);
111 failcnt++;
112 if(!max)
113 {
114 perm.resize(0);
115 }
116 i--;
117 }
118 else
119 {
120 perm[i+m_coln - m_rown] = max;
121 for(size_t j=i+1;j<m_rown;j++)//fill the column downwards with 0's
122 {
123 if(coef(j, max))
124 {
125 row_xor(j,i);//check the arg. order.
126 }
127 }
128
129 //fill the column with 0's upwards too.
130 for(size_t j = i; j != 0; --j)
131 {
132 if(coef(j - 1, max))
133 {
134 row_xor(j - 1, i);
135 }
136 }
137 }
138 }//end for(i)
139 return perm;
140 }
141
142void randomize_support(std::vector<gf2m>& L, RandomNumberGenerator& rng)
143 {
144 for(size_t i = 0; i != L.size(); ++i)
145 {
146 gf2m rnd = random_gf2m(rng);
147
148 // no rejection sampling, but for useful code-based parameters with n <= 13 this seem tolerable
149 std::swap(L[i], L[rnd % L.size()]);
150 }
151 }
152
153std::unique_ptr<binary_matrix> generate_R(std::vector<gf2m> &L, polyn_gf2m* g, const GF2m_Field& sp_field, size_t code_length, size_t t)
154 {
155 //L- Support
156 //t- Number of errors
157 //n- Length of the Goppa code
158 //m- The extension degree of the GF
159 //g- The generator polynomial.
160
161 const size_t r = t * sp_field.get_extension_degree();
162
163 binary_matrix H(r, code_length);
164
165 for(size_t i = 0; i != code_length; i++)
166 {
167 gf2m x = g->eval(lex_to_gray(L[i]));//evaluate the polynomial at the point L[i].
168 x = sp_field.gf_inv(x);
169 gf2m y = x;
170 for(size_t j=0;j<t;j++)
171 {
172 for(size_t k=0;k<sp_field.get_extension_degree();k++)
173 {
174 if(y & (1<<k))
175 {
176 //the co-eff. are set in 2^0,...,2^11 ; 2^0,...,2^11 format along the rows/cols?
177 H.set_coef_to_one(j*sp_field.get_extension_degree()+ k,i);
178 }
179 }
180 y = sp_field.gf_mul(y,lex_to_gray(L[i]));
181 }
182 }//The H matrix is fed.
183
184 secure_vector<size_t> perm = H.row_reduced_echelon_form();
185 if(perm.empty())
186 {
187 throw Invalid_State("McEliece keygen failed - could not bring matrix to row reduced echelon form");
188 }
189
190 auto result = std::make_unique<binary_matrix>(code_length - r, r);
191 for(size_t i = 0; i < result->rows(); ++i)
192 {
193 for(size_t j = 0; j < result->columns(); ++j)
194 {
195 if(H.coef(j, perm[i]))
196 {
197 result->toggle_coeff(i,j);
198 }
199 }
200 }
201
202 std::vector<gf2m> Laux(code_length);
203 for(size_t i = 0; i < code_length; ++i)
204 {
205 Laux[i] = L[perm[i]];
206 }
207
208 for(size_t i = 0; i < code_length; ++i)
209 {
210 L[i] = Laux[i];
211 }
212 return result;
213 }
214}
215
216McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator & rng, size_t ext_deg, size_t code_length, size_t t)
217 {
218 const size_t codimension = t * ext_deg;
219
220 if(code_length <= codimension)
221 {
222 throw Invalid_Argument("invalid McEliece parameters");
223 }
224
225 auto sp_field = std::make_shared<GF2m_Field>(ext_deg);
226
227 //pick the support.........
228 std::vector<gf2m> L(code_length);
229
230 for(size_t i = 0; i != L.size(); i++)
231 {
232 L[i] = static_cast<gf2m>(i);
233 }
234 randomize_support(L, rng);
235 polyn_gf2m g(sp_field); // create as zero
236
237 bool success = false;
238 std::unique_ptr<binary_matrix> R;
239
240 do
241 {
242 // create a random irreducible polynomial
243 g = polyn_gf2m(t, rng, sp_field);
244
245 try
246 {
247 R = generate_R(L, &g, *sp_field, code_length, t);
248 success = true;
249 }
250 catch(const Invalid_State &)
251 {
252 }
253 } while (!success);
254
255 std::vector<polyn_gf2m> sqrtmod = polyn_gf2m::sqrt_mod_init( g);
256 std::vector<polyn_gf2m> F = syndrome_init(g, L, static_cast<int>(code_length));
257
258 // Each F[i] is the (precomputed) syndrome of the error vector with
259 // a single '1' in i-th position.
260 // We do not store the F[i] as polynomials of degree t , but
261 // as binary vectors of length ext_deg * t (this will
262 // speed up the syndrome computation)
263 //
264 std::vector<uint32_t> H(bit_size_to_32bit_size(codimension) * code_length);
265 uint32_t* sk = H.data();
266 for(size_t i = 0; i < code_length; ++i)
267 {
268 for(size_t l = 0; l < t; ++l)
269 {
270 const size_t k = (l * ext_deg) / 32;
271 const uint8_t j = (l * ext_deg) % 32;
272 sk[k] ^= static_cast<uint32_t>(F[i].get_coef(l)) << j;
273 if(j + ext_deg > 32)
274 {
275 sk[k + 1] ^= F[i].get_coef(l) >> (32 - j);
276 }
277 }
278 sk += bit_size_to_32bit_size(codimension);
279 }
280
281 // We need the support L for decoding (decryption). In fact the
282 // inverse is needed
283
284 std::vector<gf2m> Linv(code_length) ;
285 for(size_t i = 0; i != Linv.size(); ++i)
286 {
287 Linv[L[i]] = static_cast<gf2m>(i);
288 }
289 std::vector<uint8_t> pubmat(R->elem().size() * 4);
290 for(size_t i = 0; i < R->elem().size(); i++)
291 {
292 store_le(R->elem()[i], &pubmat[i*4]);
293 }
294
295 return McEliece_PrivateKey(g, H, sqrtmod, Linv, pubmat);
296 }
297
298}
static SIMD_4x64 y
static std::vector< polyn_gf2m > sqrt_mod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:627
int(* final)(unsigned char *, CTX *)
Definition: alg_id.cpp:12
constexpr void store_le(uint16_t in, uint8_t out[2])
Definition: loadstor.h:465
gf2m lex_to_gray(gf2m lex)
std::vector< polyn_gf2m > syndrome_init(polyn_gf2m const &generator, std::vector< gf2m > const &support, int n)
Definition: polyn_gf2m.cpp:672
McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator &rng, size_t ext_deg, size_t code_length, size_t t)
gf2m random_gf2m(RandomNumberGenerator &rng)
Definition: polyn_gf2m.cpp:64
size_t bit_size_to_32bit_size(size_t bit_size)
uint16_t gf2m
Definition: gf2m_small_m.h:20