/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 | | } |