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