Botan  2.19.1
Crypto and TLS for C++11
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/polyn_gf2m.h>
17 #include <botan/loadstor.h>
18 
19 namespace Botan {
20 
21 namespace {
22 
23 class 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  private:
54  size_t m_rown; // number of rows.
55  size_t m_coln; // number of columns.
56  size_t m_rwdcnt; // number of words in a row
57  public:
58  // TODO this should be private
59  std::vector<uint32_t> m_elem;
60  };
61 
62 binary_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 
70 void 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)
79 secure_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 
142 void 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 
153 std::unique_ptr<binary_matrix> generate_R(std::vector<gf2m> &L, polyn_gf2m* g, std::shared_ptr<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.size() == 0)
186  {
187  throw Invalid_State("McEliece keygen failed - could not bring matrix to row reduced echelon form");
188  }
189 
190  std::unique_ptr<binary_matrix> result(new 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 
216 McEliece_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  std::shared_ptr<GF2m_Field> sp_field(new 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->m_elem.size() * 4);
290  for(size_t i = 0; i < R->m_elem.size(); i++)
291  {
292  store_le(R->m_elem[i], &pubmat[i*4]);
293  }
294 
295  return McEliece_PrivateKey(g, H, sqrtmod, Linv, pubmat);
296  }
297 
298 }
SIMD_8x32 H
size_t bit_size_to_32bit_size(size_t bit_size)
int(* final)(unsigned char *, CTX *)
size_t m_coln
static std::vector< polyn_gf2m > sqrt_mod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:676
gf2m lex_to_gray(gf2m lex)
uint16_t gf2m
Definition: gf2m_small_m.h:22
Definition: alg_id.cpp:13
std::vector< uint32_t > m_elem
SIMD_8x32 F
std::vector< polyn_gf2m > syndrome_init(polyn_gf2m const &generator, std::vector< gf2m > const &support, int n)
Definition: polyn_gf2m.cpp:721
McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator &rng, size_t ext_deg, size_t code_length, size_t t)
size_t m_rown
gf2m random_gf2m(RandomNumberGenerator &rng)
Definition: polyn_gf2m.cpp:64
size_t m_rwdcnt
void store_le(uint16_t in, uint8_t out[2])
Definition: loadstor.h:454