Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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