Botan 2.1.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 struct binary_matrix
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 }
Botan::McEliece_PrivateKey
Definition: mceliece.h:70
Botan::Invalid_Argument
Definition: exceptn.h:34
Botan::bit_size_to_32bit_size
uint32_t bit_size_to_32bit_size(uint32_t bit_size)
Definition: code_based_util.h:50
Botan::RandomNumberGenerator
Definition: rng.h:25
Botan::Invalid_State
Definition: exceptn.h:61
Botan::GF2m_Field
Definition: gf2m_small_m.h:25
m_rown
uint32_t m_rown
Definition: code_based_key_gen.cpp:49
m_rwdcnt
uint32_t m_rwdcnt
Definition: code_based_key_gen.cpp:51
m_coln
uint32_t m_coln
Definition: code_based_key_gen.cpp:50
Botan::lex_to_gray
gf2m lex_to_gray(gf2m lex)
Definition: code_based_util.h:40
Botan::generate_mceliece_key
McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator &rng, uint32_t ext_deg, uint32_t code_length, uint32_t t)
Definition: code_based_key_gen.cpp:208
Botan::gf2m
uint16_t gf2m
Definition: gf2m_small_m.h:20
Botan
Definition: alg_id.cpp:13
Botan::CT::max
T max(T a, T b)
Definition: ct_utils.h:173
Botan::polyn_gf2m::sqrt_mod_init
static std::vector< polyn_gf2m > sqrt_mod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:678
Botan::polyn_gf2m
Definition: polyn_gf2m.h:24
m_elem
std::vector< uint32_t > m_elem
Definition: code_based_key_gen.cpp:52
code_length
uint32_t code_length
Definition: gf2m_rootfind_dcmp.cpp:48
Botan::syndrome_init
std::vector< polyn_gf2m > syndrome_init(polyn_gf2m const &generator, std::vector< gf2m > const &support, int n)
Definition: polyn_gf2m.cpp:723
Botan::random_gf2m
gf2m random_gf2m(RandomNumberGenerator &rng)
Definition: polyn_gf2m.cpp:64
Botan::store_le
void store_le(uint16_t in, uint8_t out[2])
Definition: loadstor.h:457