Coverage Report

Created: 2021-11-25 09:31

/src/botan/src/lib/pubkey/mce/code_based_key_gen.cpp
Line
Count
Source (jump to first uncovered line)
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
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
0
         {
36
0
         return (m_elem[(i) * m_rwdcnt + (j) / 32] >> (j % 32)) & 1;
37
0
         }
38
39
      void set_coef_to_one(size_t i, size_t j)
40
0
         {
41
0
         m_elem[(i) * m_rwdcnt + (j) / 32] |= (static_cast<uint32_t>(1) << ((j) % 32)) ;
42
0
         }
43
44
      void toggle_coeff(size_t i, size_t j)
45
0
         {
46
0
         m_elem[(i) * m_rwdcnt + (j) / 32] ^= (static_cast<uint32_t>(1) << ((j) % 32)) ;
47
0
         }
48
49
0
      size_t rows() const { return m_rown; }
50
51
0
      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
0
   {
64
0
   m_coln = coln;
65
0
   m_rown = rown;
66
0
   m_rwdcnt = 1 + ((m_coln - 1) / 32);
67
0
   m_elem = std::vector<uint32_t>(m_rown * m_rwdcnt);
68
0
   }
69
70
void binary_matrix::row_xor(size_t a, size_t b)
71
0
   {
72
0
   for(size_t i = 0; i != m_rwdcnt; i++)
73
0
      {
74
0
      m_elem[a*m_rwdcnt+i] ^= m_elem[b*m_rwdcnt+i];
75
0
      }
76
0
   }
77
78
//the matrix is reduced from LSB...(from right)
79
secure_vector<size_t> binary_matrix::row_reduced_echelon_form()
80
0
   {
81
0
   secure_vector<size_t> perm(m_coln);
82
0
   for(size_t i = 0; i != m_coln; i++)
83
0
      {
84
0
      perm[i] = i; // initialize permutation.
85
0
      }
86
87
0
   uint32_t failcnt = 0;
88
89
0
   size_t max = m_coln - 1;
90
0
   for(size_t i = 0; i != m_rown; i++, max--)
91
0
      {
92
0
      bool found_row = false;
93
94
0
      for(size_t j = i; !found_row && j != m_rown; j++)
95
0
         {
96
0
         if(coef(j, max))
97
0
            {
98
0
            if(i != j) //not needed as ith row is 0 and jth row is 1.
99
0
               {
100
0
               row_xor(i, j);//xor to the row.(swap)?
101
0
               }
102
103
0
            found_row = true;
104
0
            }
105
0
         }
106
107
      //if no row with a 1 found then swap last column and the column with no 1 down.
108
0
      if(!found_row)
109
0
         {
110
0
         perm[m_coln - m_rown - 1 - failcnt] = static_cast<int>(max);
111
0
         failcnt++;
112
0
         if(!max)
113
0
            {
114
0
            perm.resize(0);
115
0
            }
116
0
         i--;
117
0
         }
118
0
      else
119
0
         {
120
0
         perm[i+m_coln - m_rown] = max;
121
0
         for(size_t j=i+1;j<m_rown;j++)//fill the column downwards with 0's
122
0
            {
123
0
            if(coef(j, max))
124
0
               {
125
0
               row_xor(j,i);//check the arg. order.
126
0
               }
127
0
            }
128
129
         //fill the column with 0's upwards too.
130
0
         for(size_t j = i; j != 0; --j)
131
0
            {
132
0
            if(coef(j - 1, max))
133
0
               {
134
0
               row_xor(j - 1, i);
135
0
               }
136
0
            }
137
0
         }
138
0
      }//end for(i)
139
0
   return perm;
140
0
   }
141
142
void randomize_support(std::vector<gf2m>& L, RandomNumberGenerator& rng)
143
0
   {
144
0
   for(size_t i = 0; i != L.size(); ++i)
145
0
      {
146
0
      gf2m rnd = random_gf2m(rng);
147
148
       // no rejection sampling, but for useful code-based parameters with n <= 13 this seem tolerable
149
0
      std::swap(L[i], L[rnd % L.size()]);
150
0
      }
151
0
   }
152
153
std::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
0
   {
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
0
   const size_t r = t * sp_field.get_extension_degree();
162
163
0
   binary_matrix H(r, code_length);
164
165
0
   for(size_t i = 0; i != code_length; i++)
166
0
      {
167
0
      gf2m x = g->eval(lex_to_gray(L[i]));//evaluate the polynomial at the point L[i].
168
0
      x = sp_field.gf_inv(x);
169
0
      gf2m y = x;
170
0
      for(size_t j=0;j<t;j++)
171
0
         {
172
0
         for(size_t k=0;k<sp_field.get_extension_degree();k++)
173
0
            {
174
0
            if(y & (1<<k))
175
0
               {
176
               //the co-eff. are set in 2^0,...,2^11 ; 2^0,...,2^11 format along the rows/cols?
177
0
               H.set_coef_to_one(j*sp_field.get_extension_degree()+ k,i);
178
0
               }
179
0
            }
180
0
         y = sp_field.gf_mul(y,lex_to_gray(L[i]));
181
0
         }
182
0
      }//The H matrix is fed.
183
184
0
   secure_vector<size_t> perm = H.row_reduced_echelon_form();
185
0
   if(perm.size() == 0)
186
0
      {
187
0
      throw Invalid_State("McEliece keygen failed - could not bring matrix to row reduced echelon form");
188
0
      }
189
190
0
   auto result = std::make_unique<binary_matrix>(code_length - r, r);
191
0
   for(size_t i = 0; i < result->rows(); ++i)
192
0
      {
193
0
      for(size_t j = 0; j < result->columns(); ++j)
194
0
         {
195
0
         if(H.coef(j, perm[i]))
196
0
            {
197
0
            result->toggle_coeff(i,j);
198
0
            }
199
0
         }
200
0
      }
201
202
0
   std::vector<gf2m> Laux(code_length);
203
0
   for(size_t i = 0; i < code_length; ++i)
204
0
      {
205
0
      Laux[i] = L[perm[i]];
206
0
      }
207
208
0
   for(size_t i = 0; i < code_length; ++i)
209
0
      {
210
0
      L[i] = Laux[i];
211
0
      }
212
0
   return result;
213
0
   }
214
}
215
216
McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator & rng, size_t ext_deg, size_t code_length, size_t t)
217
0
   {
218
0
   const size_t codimension = t * ext_deg;
219
220
0
   if(code_length <= codimension)
221
0
      {
222
0
      throw Invalid_Argument("invalid McEliece parameters");
223
0
      }
224
225
0
   auto sp_field = std::make_shared<GF2m_Field>(ext_deg);
226
227
   //pick the support.........
228
0
   std::vector<gf2m> L(code_length);
229
230
0
   for(size_t i = 0; i != L.size(); i++)
231
0
      {
232
0
      L[i] = static_cast<gf2m>(i);
233
0
      }
234
0
   randomize_support(L, rng);
235
0
   polyn_gf2m g(sp_field); // create as zero
236
237
0
   bool success = false;
238
0
   std::unique_ptr<binary_matrix> R;
239
240
0
   do
241
0
      {
242
      // create a random irreducible polynomial
243
0
      g = polyn_gf2m(t, rng, sp_field);
244
245
0
      try
246
0
         {
247
0
         R = generate_R(L, &g, *sp_field, code_length, t);
248
0
         success = true;
249
0
         }
250
0
      catch(const Invalid_State &)
251
0
         {
252
0
         }
253
0
      } while (!success);
254
255
0
   std::vector<polyn_gf2m> sqrtmod = polyn_gf2m::sqrt_mod_init( g);
256
0
   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
0
   std::vector<uint32_t> H(bit_size_to_32bit_size(codimension) * code_length);
265
0
   uint32_t* sk = H.data();
266
0
   for(size_t i = 0; i < code_length; ++i)
267
0
      {
268
0
      for(size_t l = 0; l < t; ++l)
269
0
         {
270
0
         const size_t k = (l * ext_deg) / 32;
271
0
         const uint8_t j = (l * ext_deg) % 32;
272
0
         sk[k] ^= static_cast<uint32_t>(F[i].get_coef(l)) << j;
273
0
         if(j + ext_deg > 32)
274
0
            {
275
0
            sk[k + 1] ^= F[i].get_coef(l) >> (32 - j);
276
0
            }
277
0
         }
278
0
      sk += bit_size_to_32bit_size(codimension);
279
0
      }
280
281
   // We need the support L for decoding (decryption). In fact the
282
   // inverse is needed
283
284
0
   std::vector<gf2m> Linv(code_length) ;
285
0
   for(size_t i = 0; i != Linv.size(); ++i)
286
0
      {
287
0
      Linv[L[i]] = static_cast<gf2m>(i);
288
0
      }
289
0
   std::vector<uint8_t> pubmat(R->m_elem.size() * 4);
290
0
   for(size_t i = 0; i < R->m_elem.size(); i++)
291
0
      {
292
0
      store_le(R->m_elem[i], &pubmat[i*4]);
293
0
      }
294
295
0
   return McEliece_PrivateKey(g, H, sqrtmod, Linv, pubmat);
296
0
   }
297
298
}