/src/botan/src/lib/pubkey/mce/polyn_gf2m.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/polyn_gf2m.h> |
14 | | #include <botan/internal/code_based_util.h> |
15 | | #include <botan/internal/bit_ops.h> |
16 | | #include <botan/rng.h> |
17 | | #include <botan/exceptn.h> |
18 | | #include <botan/loadstor.h> |
19 | | |
20 | | namespace Botan { |
21 | | |
22 | | namespace { |
23 | | |
24 | | gf2m generate_gf2m_mask(gf2m a) |
25 | 0 | { |
26 | 0 | gf2m result = (a != 0); |
27 | 0 | return ~(result - 1); |
28 | 0 | } |
29 | | |
30 | | /** |
31 | | * number of leading zeros |
32 | | */ |
33 | | unsigned nlz_16bit(uint16_t x) |
34 | 0 | { |
35 | 0 | unsigned n; |
36 | 0 | if(x == 0) return 16; |
37 | 0 | n = 0; |
38 | 0 | if(x <= 0x00FF) {n = n + 8; x = x << 8;} |
39 | 0 | if(x <= 0x0FFF) {n = n + 4; x = x << 4;} |
40 | 0 | if(x <= 0x3FFF) {n = n + 2; x = x << 2;} |
41 | 0 | if(x <= 0x7FFF) {n = n + 1;} |
42 | 0 | return n; |
43 | 0 | } |
44 | | } |
45 | | |
46 | | int polyn_gf2m::calc_degree_secure() const |
47 | 0 | { |
48 | 0 | int i = this->coeff.size() - 1; |
49 | 0 | int result = 0; |
50 | 0 | uint32_t found_mask = 0; |
51 | 0 | uint32_t tracker_mask = 0xffff; |
52 | 0 | for( ; i >= 0; i--) |
53 | 0 | { |
54 | 0 | found_mask = expand_mask_16bit(this->coeff[i]); |
55 | 0 | result |= i & found_mask & tracker_mask; |
56 | 0 | // tracker mask shall become zero once found mask is set |
57 | 0 | // it shall remain zero from then on |
58 | 0 | tracker_mask = tracker_mask & ~found_mask; |
59 | 0 | } |
60 | 0 | const_cast<polyn_gf2m*>(this)->m_deg = result; |
61 | 0 | return result; |
62 | 0 | } |
63 | | |
64 | | gf2m random_gf2m(RandomNumberGenerator& rng) |
65 | 0 | { |
66 | 0 | uint8_t b[2]; |
67 | 0 | rng.randomize(b, sizeof(b)); |
68 | 0 | return make_uint16(b[1], b[0]); |
69 | 0 | } |
70 | | |
71 | | gf2m random_code_element(unsigned code_length, RandomNumberGenerator& rng) |
72 | 0 | { |
73 | 0 | if(code_length == 0) |
74 | 0 | { |
75 | 0 | throw Invalid_Argument("random_code_element() was supplied a code length of zero"); |
76 | 0 | } |
77 | 0 | const unsigned nlz = nlz_16bit(code_length-1); |
78 | 0 | const gf2m mask = (1 << (16-nlz)) -1; |
79 | 0 |
|
80 | 0 | gf2m result; |
81 | 0 |
|
82 | 0 | do |
83 | 0 | { |
84 | 0 | result = random_gf2m(rng); |
85 | 0 | result &= mask; |
86 | 0 | } while(result >= code_length); // rejection sampling |
87 | 0 |
|
88 | 0 | return result; |
89 | 0 | } |
90 | | |
91 | | polyn_gf2m::polyn_gf2m(polyn_gf2m const& other) |
92 | | :m_deg(other.m_deg), |
93 | | coeff(other.coeff), |
94 | | m_sp_field(other.m_sp_field) |
95 | 0 | { } |
96 | | |
97 | | polyn_gf2m::polyn_gf2m( int d, std::shared_ptr<GF2m_Field> sp_field) |
98 | | :m_deg(-1), |
99 | | coeff(d+1), |
100 | | m_sp_field(sp_field) |
101 | 0 | { |
102 | 0 | } |
103 | | |
104 | | std::string polyn_gf2m::to_string() const |
105 | 0 | { |
106 | 0 | int d = get_degree(); |
107 | 0 | std::string result; |
108 | 0 | for(int i = 0; i <= d; i ++) |
109 | 0 | { |
110 | 0 | result += std::to_string(this->coeff[i]); |
111 | 0 | if(i != d) |
112 | 0 | { |
113 | 0 | result += ", "; |
114 | 0 | } |
115 | 0 | } |
116 | 0 | return result; |
117 | 0 | } |
118 | | /** |
119 | | * doesn't save coefficients: |
120 | | */ |
121 | | void polyn_gf2m::realloc(uint32_t new_size) |
122 | 0 | { |
123 | 0 | this->coeff = secure_vector<gf2m>(new_size); |
124 | 0 | } |
125 | | |
126 | | polyn_gf2m::polyn_gf2m(const uint8_t* mem, uint32_t mem_len, std::shared_ptr<GF2m_Field> sp_field) : |
127 | | m_deg(-1), m_sp_field(sp_field) |
128 | 0 | { |
129 | 0 | if(mem_len % sizeof(gf2m)) |
130 | 0 | { |
131 | 0 | throw Botan::Decoding_Error("illegal length of memory to decode "); |
132 | 0 | } |
133 | 0 | |
134 | 0 | uint32_t size = (mem_len / sizeof(this->coeff[0])) ; |
135 | 0 | this->coeff = secure_vector<gf2m>(size); |
136 | 0 | this->m_deg = -1; |
137 | 0 | for(uint32_t i = 0; i < size; i++) |
138 | 0 | { |
139 | 0 | this->coeff[i] = decode_gf2m(mem); |
140 | 0 | mem += sizeof(this->coeff[0]); |
141 | 0 | } |
142 | 0 | for(uint32_t i = 0; i < size; i++) |
143 | 0 | { |
144 | 0 | if(this->coeff[i] >= (1 << sp_field->get_extension_degree())) |
145 | 0 | { |
146 | 0 | throw Botan::Decoding_Error("error decoding polynomial"); |
147 | 0 | } |
148 | 0 | } |
149 | 0 | this->get_degree(); |
150 | 0 | } |
151 | | |
152 | | |
153 | | polyn_gf2m::polyn_gf2m( std::shared_ptr<GF2m_Field> sp_field) : |
154 | | m_deg(-1), coeff(1), m_sp_field(sp_field) |
155 | 0 | {} |
156 | | |
157 | | polyn_gf2m::polyn_gf2m(int degree, const unsigned char* mem, uint32_t mem_byte_len, std::shared_ptr<GF2m_Field> sp_field) |
158 | | :m_sp_field(sp_field) |
159 | 0 | { |
160 | 0 | uint32_t j, k, l; |
161 | 0 | gf2m a; |
162 | 0 | uint32_t polyn_size; |
163 | 0 | polyn_size = degree + 1; |
164 | 0 | if(polyn_size * sp_field->get_extension_degree() > 8 * mem_byte_len) |
165 | 0 | { |
166 | 0 | throw Botan::Decoding_Error("memory vector for polynomial has wrong size"); |
167 | 0 | } |
168 | 0 | this->coeff = secure_vector<gf2m>(degree+1); |
169 | 0 | gf2m ext_deg = this->m_sp_field->get_extension_degree(); |
170 | 0 | for (l = 0; l < polyn_size; l++) |
171 | 0 | { |
172 | 0 | k = (l * ext_deg) / 8; |
173 | 0 |
|
174 | 0 | j = (l * ext_deg) % 8; |
175 | 0 | a = mem[k] >> j; |
176 | 0 | if (j + ext_deg > 8) |
177 | 0 | { |
178 | 0 | a ^= mem[k + 1] << (8- j); |
179 | 0 | } |
180 | 0 | if(j + ext_deg > 16) |
181 | 0 | { |
182 | 0 | a ^= mem[k + 2] << (16- j); |
183 | 0 | } |
184 | 0 | a &= ((1 << ext_deg) - 1); |
185 | 0 | (*this).set_coef( l, a); |
186 | 0 | } |
187 | 0 |
|
188 | 0 | this->get_degree(); |
189 | 0 | } |
190 | | |
191 | | #if 0 |
192 | | void polyn_gf2m::encode(uint32_t min_numo_coeffs, uint8_t* mem, uint32_t mem_len) const |
193 | | { |
194 | | uint32_t i; |
195 | | uint32_t numo_coeffs, needed_size; |
196 | | this->get_degree(); |
197 | | numo_coeffs = (min_numo_coeffs > static_cast<uint32_t>(this->m_deg+1)) ? min_numo_coeffs : this->m_deg+1; |
198 | | needed_size = sizeof(this->coeff[0]) * numo_coeffs; |
199 | | if(mem_len < needed_size) |
200 | | { |
201 | | Invalid_Argument("provided memory too small to encode polynomial"); |
202 | | } |
203 | | |
204 | | for(i = 0; i < numo_coeffs; i++) |
205 | | { |
206 | | gf2m to_enc; |
207 | | if(i >= static_cast<uint32_t>(this->m_deg+1)) |
208 | | { |
209 | | /* encode a zero */ |
210 | | to_enc = 0; |
211 | | } |
212 | | else |
213 | | { |
214 | | to_enc = this->coeff[i]; |
215 | | } |
216 | | mem += encode_gf2m(to_enc, mem); |
217 | | } |
218 | | } |
219 | | #endif |
220 | | |
221 | | |
222 | | void polyn_gf2m::set_to_zero() |
223 | 0 | { |
224 | 0 | clear_mem(&this->coeff[0], this->coeff.size()); |
225 | 0 | this->m_deg = -1; |
226 | 0 | } |
227 | | |
228 | | int polyn_gf2m::get_degree() const |
229 | 0 | { |
230 | 0 | int d = this->coeff.size() - 1; |
231 | 0 | while ((d >= 0) && (this->coeff[d] == 0)) |
232 | 0 | --d; |
233 | 0 | const_cast<polyn_gf2m*>(this)->m_deg = d; |
234 | 0 | return d; |
235 | 0 | } |
236 | | |
237 | | |
238 | | static gf2m eval_aux(const gf2m * /*restrict*/ coeff, gf2m a, int d, std::shared_ptr<GF2m_Field> sp_field) |
239 | 0 | { |
240 | 0 | gf2m b; |
241 | 0 | b = coeff[d--]; |
242 | 0 | for (; d >= 0; --d) |
243 | 0 | if (b != 0) |
244 | 0 | { |
245 | 0 | b = sp_field->gf_mul(b, a) ^ coeff[d]; |
246 | 0 | } |
247 | 0 | else |
248 | 0 | { |
249 | 0 | b = coeff[d]; |
250 | 0 | } |
251 | 0 | return b; |
252 | 0 | } |
253 | | |
254 | | gf2m polyn_gf2m::eval(gf2m a) |
255 | 0 | { |
256 | 0 | return eval_aux(&this->coeff[0], a, this->m_deg, this->m_sp_field); |
257 | 0 | } |
258 | | |
259 | | |
260 | | // p will contain it's remainder modulo g |
261 | | void polyn_gf2m::remainder(polyn_gf2m &p, const polyn_gf2m & g) |
262 | 0 | { |
263 | 0 | int i, j, d; |
264 | 0 | std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field; |
265 | 0 | d = p.get_degree() - g.get_degree(); |
266 | 0 | if (d >= 0) { |
267 | 0 | gf2m la = m_sp_field->gf_inv_rn(g.get_lead_coef()); |
268 | 0 |
|
269 | 0 | const int p_degree = p.get_degree(); |
270 | 0 |
|
271 | 0 | BOTAN_ASSERT(p_degree > 0, "Valid polynomial"); |
272 | 0 |
|
273 | 0 | for (i = p_degree; d >= 0; --i, --d) { |
274 | 0 | if (p[i] != 0) { |
275 | 0 | gf2m lb = m_sp_field->gf_mul_rrn(la, p[i]); |
276 | 0 | for (j = 0; j < g.get_degree(); ++j) |
277 | 0 | { |
278 | 0 | p[j+d] ^= m_sp_field->gf_mul_zrz(lb, g[j]); |
279 | 0 | } |
280 | 0 | (*&p).set_coef( i, 0); |
281 | 0 | } |
282 | 0 | } |
283 | 0 | p.set_degree( g.get_degree() - 1); |
284 | 0 | while ((p.get_degree() >= 0) && (p[p.get_degree()] == 0)) |
285 | 0 | p.set_degree( p.get_degree() - 1); |
286 | 0 | } |
287 | 0 | } |
288 | | |
289 | | std::vector<polyn_gf2m> polyn_gf2m::sqmod_init(const polyn_gf2m & g) |
290 | 0 | { |
291 | 0 | std::vector<polyn_gf2m> sq; |
292 | 0 | const int signed_deg = g.get_degree(); |
293 | 0 | if(signed_deg <= 0) |
294 | 0 | throw Invalid_Argument("cannot compute sqmod for such low degree"); |
295 | 0 | |
296 | 0 | const uint32_t d = static_cast<uint32_t>(signed_deg); |
297 | 0 | uint32_t t = g.m_deg; |
298 | 0 | // create t zero polynomials |
299 | 0 | uint32_t i; |
300 | 0 | for (i = 0; i < t; ++i) |
301 | 0 | { |
302 | 0 | sq.push_back(polyn_gf2m(t+1, g.get_sp_field())); |
303 | 0 | } |
304 | 0 | for (i = 0; i < d / 2; ++i) |
305 | 0 | { |
306 | 0 | sq[i].set_degree( 2 * i); |
307 | 0 | (*&sq[i]).set_coef( 2 * i, 1); |
308 | 0 | } |
309 | 0 |
|
310 | 0 | for (; i < d; ++i) |
311 | 0 | { |
312 | 0 | clear_mem(&sq[i].coeff[0], 2); |
313 | 0 | copy_mem(&sq[i].coeff[0] + 2, &sq[i - 1].coeff[0], d); |
314 | 0 | sq[i].set_degree( sq[i - 1].get_degree() + 2); |
315 | 0 | polyn_gf2m::remainder(sq[i], g); |
316 | 0 | } |
317 | 0 | return sq; |
318 | 0 | } |
319 | | |
320 | | /*Modulo p square of a certain polynomial g, sq[] contains the square |
321 | | Modulo g of the base canonical polynomials of degree < d, where d is |
322 | | the degree of G. The table sq[] will be calculated by polyn_gf2m_sqmod_init*/ |
323 | | polyn_gf2m polyn_gf2m::sqmod( const std::vector<polyn_gf2m> & sq, int d) |
324 | 0 | { |
325 | 0 | int i, j; |
326 | 0 | gf2m la; |
327 | 0 | std::shared_ptr<GF2m_Field> sp_field = this->m_sp_field; |
328 | 0 |
|
329 | 0 | polyn_gf2m result(d - 1, sp_field); |
330 | 0 | // terms of low degree |
331 | 0 | for (i = 0; i < d / 2; ++i) |
332 | 0 | { |
333 | 0 | (*&result).set_coef( i * 2, sp_field->gf_square((*this)[i])); |
334 | 0 | } |
335 | 0 |
|
336 | 0 | // terms of high degree |
337 | 0 | for (; i < d; ++i) |
338 | 0 | { |
339 | 0 | gf2m lpi = (*this)[i]; |
340 | 0 | if (lpi != 0) |
341 | 0 | { |
342 | 0 | lpi = sp_field->gf_log(lpi); |
343 | 0 | la = sp_field->gf_mul_rrr(lpi, lpi); |
344 | 0 | for (j = 0; j < d; ++j) |
345 | 0 | { |
346 | 0 | result[j] ^= sp_field->gf_mul_zrz(la, sq[i][j]); |
347 | 0 | } |
348 | 0 | } |
349 | 0 | } |
350 | 0 |
|
351 | 0 | // Update degre |
352 | 0 | result.set_degree( d - 1); |
353 | 0 | while ((result.get_degree() >= 0) && (result[result.get_degree()] == 0)) |
354 | 0 | result.set_degree( result.get_degree() - 1); |
355 | 0 | return result; |
356 | 0 | } |
357 | | |
358 | | |
359 | | // destructive |
360 | | polyn_gf2m polyn_gf2m::gcd_aux(polyn_gf2m& p1, polyn_gf2m& p2) |
361 | 0 | { |
362 | 0 | if (p2.get_degree() == -1) |
363 | 0 | return p1; |
364 | 0 | else { |
365 | 0 | polyn_gf2m::remainder(p1, p2); |
366 | 0 | return polyn_gf2m::gcd_aux(p2, p1); |
367 | 0 | } |
368 | 0 | } |
369 | | |
370 | | |
371 | | polyn_gf2m polyn_gf2m::gcd(polyn_gf2m const& p1, polyn_gf2m const& p2) |
372 | 0 | { |
373 | 0 | polyn_gf2m a(p1); |
374 | 0 | polyn_gf2m b(p2); |
375 | 0 | if (a.get_degree() < b.get_degree()) |
376 | 0 | { |
377 | 0 | return polyn_gf2m(polyn_gf2m::gcd_aux(b, a)); |
378 | 0 | } |
379 | 0 | else |
380 | 0 | { |
381 | 0 | return polyn_gf2m(polyn_gf2m::gcd_aux(a, b)); |
382 | 0 | } |
383 | 0 | } |
384 | | |
385 | | |
386 | | |
387 | | |
388 | | |
389 | | // Returns the degree of the smallest factor |
390 | | void polyn_gf2m::degppf(const polyn_gf2m & g, int* p_result) |
391 | 0 | { |
392 | 0 | polyn_gf2m s(g.get_sp_field()); |
393 | 0 |
|
394 | 0 | const size_t ext_deg = g.m_sp_field->get_extension_degree(); |
395 | 0 | const int d = g.get_degree(); |
396 | 0 | std::vector<polyn_gf2m> u = polyn_gf2m::sqmod_init(g); |
397 | 0 |
|
398 | 0 | polyn_gf2m p(d - 1, g.m_sp_field); |
399 | 0 |
|
400 | 0 | p.set_degree(1); |
401 | 0 | (*&p).set_coef(1, 1); |
402 | 0 | (*p_result) = d; |
403 | 0 | for(size_t i = 1; i <= (d / 2) * ext_deg; ++i) |
404 | 0 | { |
405 | 0 | polyn_gf2m r = p.sqmod(u, d); |
406 | 0 | if ((i % ext_deg) == 0) |
407 | 0 | { |
408 | 0 | r[1] ^= 1; |
409 | 0 | r.get_degree(); // The degree may change |
410 | 0 | s = polyn_gf2m::gcd( g, r); |
411 | 0 |
|
412 | 0 | if(s.get_degree() > 0) |
413 | 0 | { |
414 | 0 | (*p_result) = i / ext_deg; |
415 | 0 | break; |
416 | 0 | } |
417 | 0 | r[1] ^= 1; |
418 | 0 | r.get_degree(); // The degree may change |
419 | 0 | } |
420 | 0 | // No need for the exchange s |
421 | 0 | s = p; |
422 | 0 | p = r; |
423 | 0 | r = s; |
424 | 0 | } |
425 | 0 |
|
426 | 0 |
|
427 | 0 | } |
428 | | |
429 | | void polyn_gf2m::patchup_deg_secure( uint32_t trgt_deg, volatile gf2m patch_elem) |
430 | 0 | { |
431 | 0 | uint32_t i; |
432 | 0 | if(this->coeff.size() < trgt_deg) |
433 | 0 | { |
434 | 0 | return; |
435 | 0 | } |
436 | 0 | for(i = 0; i < this->coeff.size(); i++) |
437 | 0 | { |
438 | 0 | uint32_t equal, equal_mask; |
439 | 0 | this->coeff[i] |= patch_elem; |
440 | 0 | equal = (i == trgt_deg); |
441 | 0 | equal_mask = expand_mask_16bit(equal); |
442 | 0 | patch_elem &= ~equal_mask; |
443 | 0 | } |
444 | 0 | this->calc_degree_secure(); |
445 | 0 | } |
446 | | // We suppose m_deg(g) >= m_deg(p) |
447 | | // v is the problem |
448 | | std::pair<polyn_gf2m, polyn_gf2m> polyn_gf2m::eea_with_coefficients( const polyn_gf2m & p, const polyn_gf2m & g, int break_deg) |
449 | 0 | { |
450 | 0 |
|
451 | 0 | std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field; |
452 | 0 | int i, j, dr, du, delta; |
453 | 0 | gf2m a; |
454 | 0 | polyn_gf2m aux; |
455 | 0 |
|
456 | 0 | // initialisation of the local variables |
457 | 0 | // r0 <- g, r1 <- p, u0 <- 0, u1 <- 1 |
458 | 0 | dr = g.get_degree(); |
459 | 0 |
|
460 | 0 | BOTAN_ASSERT(dr > 3, "Valid polynomial"); |
461 | 0 |
|
462 | 0 | polyn_gf2m r0(dr, g.m_sp_field); |
463 | 0 | polyn_gf2m r1(dr - 1, g.m_sp_field); |
464 | 0 | polyn_gf2m u0(dr - 1, g.m_sp_field); |
465 | 0 | polyn_gf2m u1(dr - 1, g.m_sp_field); |
466 | 0 |
|
467 | 0 | r0 = g; |
468 | 0 | r1 = p; |
469 | 0 | u0.set_to_zero(); |
470 | 0 | u1.set_to_zero(); |
471 | 0 | (*&u1).set_coef( 0, 1); |
472 | 0 | u1.set_degree( 0); |
473 | 0 |
|
474 | 0 |
|
475 | 0 | // invariants: |
476 | 0 | // r1 = u1 * p + v1 * g |
477 | 0 | // r0 = u0 * p + v0 * g |
478 | 0 | // and m_deg(u1) = m_deg(g) - m_deg(r0) |
479 | 0 | // It stops when m_deg (r1) <t (m_deg (r0)> = t) |
480 | 0 | // And therefore m_deg (u1) = m_deg (g) - m_deg (r0) <m_deg (g) - break_deg |
481 | 0 | du = 0; |
482 | 0 | dr = r1.get_degree(); |
483 | 0 | delta = r0.get_degree() - dr; |
484 | 0 |
|
485 | 0 |
|
486 | 0 | while (dr >= break_deg) |
487 | 0 | { |
488 | 0 |
|
489 | 0 | for (j = delta; j >= 0; --j) |
490 | 0 | { |
491 | 0 | a = m_sp_field->gf_div(r0[dr + j], r1[dr]); |
492 | 0 | if (a != 0) |
493 | 0 | { |
494 | 0 | gf2m la = m_sp_field->gf_log(a); |
495 | 0 | // u0(z) <- u0(z) + a * u1(z) * z^j |
496 | 0 | for (i = 0; i <= du; ++i) |
497 | 0 | { |
498 | 0 | u0[i + j] ^= m_sp_field->gf_mul_zrz(la, u1[i]); |
499 | 0 | } |
500 | 0 | // r0(z) <- r0(z) + a * r1(z) * z^j |
501 | 0 | for (i = 0; i <= dr; ++i) |
502 | 0 | { |
503 | 0 | r0[i + j] ^= m_sp_field->gf_mul_zrz(la, r1[i]); |
504 | 0 | } |
505 | 0 | } |
506 | 0 | } // end loop over j |
507 | 0 |
|
508 | 0 | if(break_deg != 1) /* key eq. solving */ |
509 | 0 | { |
510 | 0 | /* [ssms_icisc09] Countermeasure |
511 | 0 | * d_break from paper equals break_deg - 1 |
512 | 0 | * */ |
513 | 0 |
|
514 | 0 | volatile gf2m fake_elem = 0x01; |
515 | 0 | volatile gf2m cond1, cond2; |
516 | 0 | int trgt_deg = r1.get_degree() - 1; |
517 | 0 | r0.calc_degree_secure(); |
518 | 0 | u0.calc_degree_secure(); |
519 | 0 | if(!(g.get_degree() % 2)) |
520 | 0 | { |
521 | 0 | /* t even */ |
522 | 0 | cond1 = r0.get_degree() < break_deg - 1; |
523 | 0 | } |
524 | 0 | else |
525 | 0 | { |
526 | 0 | /* t odd */ |
527 | 0 | cond1 = r0.get_degree() < break_deg; |
528 | 0 | cond2 = u0.get_degree() < break_deg - 1; |
529 | 0 | cond1 &= cond2; |
530 | 0 | } |
531 | 0 | /* expand cond1 to a full mask */ |
532 | 0 | gf2m mask = generate_gf2m_mask(cond1); |
533 | 0 | fake_elem &= mask; |
534 | 0 | r0.patchup_deg_secure(trgt_deg, fake_elem); |
535 | 0 | } |
536 | 0 | if(break_deg == 1) /* syndrome inversion */ |
537 | 0 | { |
538 | 0 | volatile gf2m fake_elem = 0x00; |
539 | 0 | volatile uint32_t trgt_deg = 0; |
540 | 0 | r0.calc_degree_secure(); |
541 | 0 | u0.calc_degree_secure(); |
542 | 0 | /** |
543 | 0 | * countermeasure against the low weight attacks for w=4, w=6 and w=8. |
544 | 0 | * Higher values are not covered since for w=8 we already have a |
545 | 0 | * probability for a positive of 1/n^3 from random ciphertexts with the |
546 | 0 | * given weight. For w = 10 it would be 1/n^4 and so on. Thus attacks |
547 | 0 | * based on such high values of w are considered impractical. |
548 | 0 | * |
549 | 0 | * The outer test for the degree of u ( Omega in the paper ) needs not to |
550 | 0 | * be disguised. Each of the three is performed at most once per EEA |
551 | 0 | * (syndrome inversion) execution, the attacker knows this already when |
552 | 0 | * preparing the ciphertext with the given weight. Inside these three |
553 | 0 | * cases however, we must use timing neutral (branch free) operations to |
554 | 0 | * implement the condition detection and the counteractions. |
555 | 0 | * |
556 | 0 | */ |
557 | 0 | if(u0.get_degree() == 4) |
558 | 0 | { |
559 | 0 | uint32_t mask = 0; |
560 | 0 | /** |
561 | 0 | * Condition that the EEA would break now |
562 | 0 | */ |
563 | 0 | int cond_r = r0.get_degree() == 0; |
564 | 0 | /** |
565 | 0 | * Now come the conditions for all odd coefficients of this sigma |
566 | 0 | * candiate. If they are all fulfilled, then we know that we have a low |
567 | 0 | * weight error vector, since the key-equation solving EEA is skipped if |
568 | 0 | * the degree of tau^2 is low (=m_deg(u0)) and all its odd cofficients are |
569 | 0 | * zero (they would cause "full-length" contributions from the square |
570 | 0 | * root computation). |
571 | 0 | */ |
572 | 0 | // Condition for the coefficient to Y to be cancelled out by the |
573 | 0 | // addition of Y before the square root computation: |
574 | 0 | int cond_u1 = m_sp_field->gf_mul(u0.coeff[1], m_sp_field->gf_inv(r0.coeff[0])) == 1; |
575 | 0 |
|
576 | 0 | // Condition sigma_3 = 0: |
577 | 0 | int cond_u3 = u0.coeff[3] == 0; |
578 | 0 | // combine the conditions: |
579 | 0 | cond_r &= (cond_u1 & cond_u3); |
580 | 0 | // mask generation: |
581 | 0 | mask = expand_mask_16bit(cond_r); |
582 | 0 | trgt_deg = 2 & mask; |
583 | 0 | fake_elem = 1 & mask; |
584 | 0 | } |
585 | 0 | else if(u0.get_degree() == 6) |
586 | 0 | { |
587 | 0 | uint32_t mask = 0; |
588 | 0 | int cond_r= r0.get_degree() == 0; |
589 | 0 | int cond_u1 = m_sp_field->gf_mul(u0.coeff[1], m_sp_field->gf_inv(r0.coeff[0])) == 1; |
590 | 0 | int cond_u3 = u0.coeff[3] == 0; |
591 | 0 |
|
592 | 0 | int cond_u5 = u0.coeff[5] == 0; |
593 | 0 |
|
594 | 0 | cond_r &= (cond_u1 & cond_u3 & cond_u5); |
595 | 0 | mask = expand_mask_16bit(cond_r); |
596 | 0 | trgt_deg = 4 & mask; |
597 | 0 | fake_elem = 1 & mask; |
598 | 0 | } |
599 | 0 | else if(u0.get_degree() == 8) |
600 | 0 | { |
601 | 0 | uint32_t mask = 0; |
602 | 0 | int cond_r= r0.get_degree() == 0; |
603 | 0 | int cond_u1 = m_sp_field->gf_mul(u0[1], m_sp_field->gf_inv(r0[0])) == 1; |
604 | 0 | int cond_u3 = u0.coeff[3] == 0; |
605 | 0 |
|
606 | 0 | int cond_u5 = u0.coeff[5] == 0; |
607 | 0 |
|
608 | 0 | int cond_u7 = u0.coeff[7] == 0; |
609 | 0 |
|
610 | 0 | cond_r &= (cond_u1 & cond_u3 & cond_u5 & cond_u7); |
611 | 0 | mask = expand_mask_16bit(cond_r); |
612 | 0 | trgt_deg = 6 & mask; |
613 | 0 | fake_elem = 1 & mask; |
614 | 0 | } |
615 | 0 | r0.patchup_deg_secure(trgt_deg, fake_elem); |
616 | 0 | } |
617 | 0 | // exchange |
618 | 0 | aux = r0; r0 = r1; r1 = aux; |
619 | 0 | aux = u0; u0 = u1; u1 = aux; |
620 | 0 |
|
621 | 0 | du = du + delta; |
622 | 0 | delta = 1; |
623 | 0 | while (r1[dr - delta] == 0) |
624 | 0 | { |
625 | 0 | delta++; |
626 | 0 | } |
627 | 0 |
|
628 | 0 |
|
629 | 0 | dr -= delta; |
630 | 0 | } /* end while loop (dr >= break_deg) */ |
631 | 0 |
|
632 | 0 |
|
633 | 0 | u1.set_degree( du); |
634 | 0 | r1.set_degree( dr); |
635 | 0 | //return u1 and r1; |
636 | 0 | return std::make_pair(u1,r1); // coefficients u,v |
637 | 0 | } |
638 | | |
639 | | polyn_gf2m::polyn_gf2m(int t, Botan::RandomNumberGenerator& rng, std::shared_ptr<GF2m_Field> sp_field) |
640 | | :m_deg(t), |
641 | | coeff(t+1), |
642 | | m_sp_field(sp_field) |
643 | 0 | { |
644 | 0 | (*this).set_coef( t, 1); |
645 | 0 | int degree = 0; |
646 | 0 | do |
647 | 0 | { |
648 | 0 | for (int i = 0; i < t; ++i) |
649 | 0 | { |
650 | 0 | (*this).set_coef( i, random_code_element(sp_field->get_cardinality(), rng)); |
651 | 0 | } |
652 | 0 | polyn_gf2m::degppf(*this, °ree); |
653 | 0 | } |
654 | 0 | while (degree < t); |
655 | 0 | } |
656 | | |
657 | | |
658 | | void polyn_gf2m::poly_shiftmod( const polyn_gf2m & g) |
659 | 0 | { |
660 | 0 | if(g.get_degree() <= 1) |
661 | 0 | { |
662 | 0 | throw Invalid_Argument("shiftmod cannot be called on polynomials of degree 1 or less"); |
663 | 0 | } |
664 | 0 | std::shared_ptr<GF2m_Field> field = g.m_sp_field; |
665 | 0 |
|
666 | 0 | int t = g.get_degree(); |
667 | 0 | gf2m a = field->gf_div(this->coeff[t-1], g.coeff[t]); |
668 | 0 | for (int i = t - 1; i > 0; --i) |
669 | 0 | { |
670 | 0 | this->coeff[i] = this->coeff[i - 1] ^ this->m_sp_field->gf_mul(a, g.coeff[i]); |
671 | 0 | } |
672 | 0 | this->coeff[0] = field->gf_mul(a, g.coeff[0]); |
673 | 0 | } |
674 | | |
675 | | std::vector<polyn_gf2m> polyn_gf2m::sqrt_mod_init(const polyn_gf2m & g) |
676 | 0 | { |
677 | 0 | uint32_t i, t; |
678 | 0 | uint32_t nb_polyn_sqrt_mat; |
679 | 0 | std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field; |
680 | 0 | std::vector<polyn_gf2m> result; |
681 | 0 | t = g.get_degree(); |
682 | 0 | nb_polyn_sqrt_mat = t/2; |
683 | 0 |
|
684 | 0 | std::vector<polyn_gf2m> sq_aux = polyn_gf2m::sqmod_init(g); |
685 | 0 |
|
686 | 0 |
|
687 | 0 | polyn_gf2m p( t - 1, g.get_sp_field()); |
688 | 0 | p.set_degree( 1); |
689 | 0 |
|
690 | 0 | (*&p).set_coef( 1, 1); |
691 | 0 | // q(z) = 0, p(z) = z |
692 | 0 | for (i = 0; i < t * m_sp_field->get_extension_degree() - 1; ++i) |
693 | 0 | { |
694 | 0 | // q(z) <- p(z)^2 mod g(z) |
695 | 0 | polyn_gf2m q = p.sqmod(sq_aux, t); |
696 | 0 | // q(z) <-> p(z) |
697 | 0 | polyn_gf2m aux = q; |
698 | 0 | q = p; |
699 | 0 | p = aux; |
700 | 0 | } |
701 | 0 | // p(z) = z^(2^(tm-1)) mod g(z) = sqrt(z) mod g(z) |
702 | 0 |
|
703 | 0 | for (i = 0; i < nb_polyn_sqrt_mat; ++i) |
704 | 0 | { |
705 | 0 | result.push_back(polyn_gf2m(t - 1, g.get_sp_field())); |
706 | 0 | } |
707 | 0 |
|
708 | 0 | result[0] = p; |
709 | 0 | result[0].get_degree(); |
710 | 0 | for(i = 1; i < nb_polyn_sqrt_mat; i++) |
711 | 0 | { |
712 | 0 | result[i] = result[i - 1]; |
713 | 0 | result[i].poly_shiftmod(g), |
714 | 0 | result[i].get_degree(); |
715 | 0 | } |
716 | 0 |
|
717 | 0 | return result; |
718 | 0 | } |
719 | | |
720 | | std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<gf2m> const& support, int n) |
721 | 0 | { |
722 | 0 | int i,j,t; |
723 | 0 | gf2m a; |
724 | 0 |
|
725 | 0 |
|
726 | 0 | std::shared_ptr<GF2m_Field> m_sp_field = generator.m_sp_field; |
727 | 0 |
|
728 | 0 | std::vector<polyn_gf2m> result; |
729 | 0 | t = generator.get_degree(); |
730 | 0 |
|
731 | 0 | //g(z)=g_t+g_(t-1).z^(t-1)+......+g_1.z+g_0 |
732 | 0 | //f(z)=f_(t-1).z^(t-1)+......+f_1.z+f_0 |
733 | 0 |
|
734 | 0 | for(j=0;j<n;j++) |
735 | 0 | { |
736 | 0 | result.push_back(polyn_gf2m( t-1, m_sp_field)); |
737 | 0 |
|
738 | 0 | (*&result[j]).set_coef(t-1,1); |
739 | 0 | for(i=t-2;i>=0;i--) |
740 | 0 | { |
741 | 0 | (*&result[j]).set_coef(i, (generator)[i+1] ^ |
742 | 0 | m_sp_field->gf_mul(lex_to_gray(support[j]),result[j][i+1])); |
743 | 0 | } |
744 | 0 | a = ((generator)[0] ^ m_sp_field->gf_mul(lex_to_gray(support[j]),result[j][0])); |
745 | 0 | for(i=0;i<t;i++) |
746 | 0 | { |
747 | 0 | (*&result[j]).set_coef(i, m_sp_field->gf_div(result[j][i],a)); |
748 | 0 | } |
749 | 0 | } |
750 | 0 | return result; |
751 | 0 | } |
752 | | |
753 | | polyn_gf2m::polyn_gf2m(const secure_vector<uint8_t>& encoded, std::shared_ptr<GF2m_Field> sp_field ) |
754 | | :m_sp_field(sp_field) |
755 | 0 | { |
756 | 0 | if(encoded.size() % 2) |
757 | 0 | { |
758 | 0 | throw Decoding_Error("encoded polynomial has odd length"); |
759 | 0 | } |
760 | 0 | for(uint32_t i = 0; i < encoded.size(); i += 2) |
761 | 0 | { |
762 | 0 | gf2m el = (encoded[i] << 8) | encoded[i + 1]; |
763 | 0 | coeff.push_back(el); |
764 | 0 | } |
765 | 0 | get_degree(); |
766 | 0 |
|
767 | 0 | } |
768 | | secure_vector<uint8_t> polyn_gf2m::encode() const |
769 | 0 | { |
770 | 0 | secure_vector<uint8_t> result; |
771 | 0 |
|
772 | 0 | if(m_deg < 1) |
773 | 0 | { |
774 | 0 | result.push_back(0); |
775 | 0 | result.push_back(0); |
776 | 0 | return result; |
777 | 0 | } |
778 | 0 | |
779 | 0 | uint32_t len = m_deg+1; |
780 | 0 | for(unsigned i = 0; i < len; i++) |
781 | 0 | { |
782 | 0 | // "big endian" encoding of the GF(2^m) elements |
783 | 0 | result.push_back(get_byte(0, coeff[i])); |
784 | 0 | result.push_back(get_byte(1, coeff[i])); |
785 | 0 | } |
786 | 0 | return result; |
787 | 0 | } |
788 | | |
789 | | void polyn_gf2m::swap(polyn_gf2m& other) |
790 | 0 | { |
791 | 0 | std::swap(this->m_deg, other.m_deg); |
792 | 0 | std::swap(this->m_sp_field, other.m_sp_field); |
793 | 0 | std::swap(this->coeff, other.coeff); |
794 | 0 | } |
795 | | |
796 | | bool polyn_gf2m::operator==(const polyn_gf2m & other) const |
797 | 0 | { |
798 | 0 | if(m_deg != other.m_deg || coeff != other.coeff) |
799 | 0 | { |
800 | 0 | return false; |
801 | 0 | } |
802 | 0 | return true; |
803 | 0 | } |
804 | | |
805 | | } |