Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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