Botan  2.11.0
Crypto and TLS for C++11
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 
47  {
48  int i = 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(unsigned 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 
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 Botan::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 Botan::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 unsigned char* mem, uint32_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 Botan::Decoding_Error("memory vector for polynomial has wrong size");
167  }
168  this->coeff = secure_vector<gf2m>(degree+1);
169  gf2m ext_deg = 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 
223  {
224  clear_mem(&this->coeff[0], this->coeff.size());
225  this->m_deg = -1;
226  }
227 
229  {
230  int d = 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 
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 void polyn_gf2m::degppf(const polyn_gf2m & g, int* p_result)
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  (*p_result) = 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  (*p_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 
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(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  {
644  (*this).set_coef( t, 1);
645  int degree = 0;
646  do
647  {
648  for (int i = 0; i < t; ++i)
649  {
650  (*this).set_coef( i, random_code_element(sp_field->get_cardinality(), rng));
651  }
652  polyn_gf2m::degppf(*this, &degree);
653  }
654  while (degree < t);
655  }
656 
657 
658 void polyn_gf2m::poly_shiftmod( const polyn_gf2m & g)
659  {
660  if(g.get_degree() <= 1)
661  {
662  throw Invalid_Argument("shiftmod cannot be called on polynomials of degree 1 or less");
663  }
664  std::shared_ptr<GF2m_Field> field = g.m_sp_field;
665 
666  int t = g.get_degree();
667  gf2m a = field->gf_div(this->coeff[t-1], g.coeff[t]);
668  for (int i = t - 1; i > 0; --i)
669  {
670  this->coeff[i] = this->coeff[i - 1] ^ this->m_sp_field->gf_mul(a, g.coeff[i]);
671  }
672  this->coeff[0] = field->gf_mul(a, g.coeff[0]);
673  }
674 
675 std::vector<polyn_gf2m> polyn_gf2m::sqrt_mod_init(const polyn_gf2m & g)
676  {
677  uint32_t i, t;
678  uint32_t nb_polyn_sqrt_mat;
679  std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field;
680  std::vector<polyn_gf2m> result;
681  t = g.get_degree();
682  nb_polyn_sqrt_mat = t/2;
683 
684  std::vector<polyn_gf2m> sq_aux = polyn_gf2m::sqmod_init(g);
685 
686 
687  polyn_gf2m p( t - 1, g.get_sp_field());
688  p.set_degree( 1);
689 
690  (*&p).set_coef( 1, 1);
691  // q(z) = 0, p(z) = z
692  for (i = 0; i < t * m_sp_field->get_extension_degree() - 1; ++i)
693  {
694  // q(z) <- p(z)^2 mod g(z)
695  polyn_gf2m q = p.sqmod(sq_aux, t);
696  // q(z) <-> p(z)
697  polyn_gf2m aux = q;
698  q = p;
699  p = aux;
700  }
701  // p(z) = z^(2^(tm-1)) mod g(z) = sqrt(z) mod g(z)
702 
703  for (i = 0; i < nb_polyn_sqrt_mat; ++i)
704  {
705  result.push_back(polyn_gf2m(t - 1, g.get_sp_field()));
706  }
707 
708  result[0] = p;
709  result[0].get_degree();
710  for(i = 1; i < nb_polyn_sqrt_mat; i++)
711  {
712  result[i] = result[i - 1];
713  result[i].poly_shiftmod(g),
714  result[i].get_degree();
715  }
716 
717  return result;
718  }
719 
720 std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<gf2m> const& support, int n)
721  {
722  int i,j,t;
723  gf2m a;
724 
725 
726  std::shared_ptr<GF2m_Field> m_sp_field = generator.m_sp_field;
727 
728  std::vector<polyn_gf2m> result;
729  t = generator.get_degree();
730 
731  //g(z)=g_t+g_(t-1).z^(t-1)+......+g_1.z+g_0
732  //f(z)=f_(t-1).z^(t-1)+......+f_1.z+f_0
733 
734  for(j=0;j<n;j++)
735  {
736  result.push_back(polyn_gf2m( t-1, m_sp_field));
737 
738  (*&result[j]).set_coef(t-1,1);
739  for(i=t-2;i>=0;i--)
740  {
741  (*&result[j]).set_coef(i, (generator)[i+1] ^
742  m_sp_field->gf_mul(lex_to_gray(support[j]),result[j][i+1]));
743  }
744  a = ((generator)[0] ^ m_sp_field->gf_mul(lex_to_gray(support[j]),result[j][0]));
745  for(i=0;i<t;i++)
746  {
747  (*&result[j]).set_coef(i, m_sp_field->gf_div(result[j][i],a));
748  }
749  }
750  return result;
751  }
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  {
756  if(encoded.size() % 2)
757  {
758  throw Decoding_Error("encoded polynomial has odd length");
759  }
760  for(uint32_t i = 0; i < encoded.size(); i += 2)
761  {
762  gf2m el = (encoded[i] << 8) | encoded[i + 1];
763  coeff.push_back(el);
764  }
765  get_degree();
766 
767  }
769  {
770  secure_vector<uint8_t> result;
771 
772  if(m_deg < 1)
773  {
774  result.push_back(0);
775  result.push_back(0);
776  return result;
777  }
778 
779  uint32_t len = m_deg+1;
780  for(unsigned i = 0; i < len; i++)
781  {
782  // "big endian" encoding of the GF(2^m) elements
783  result.push_back(get_byte(0, coeff[i]));
784  result.push_back(get_byte(1, coeff[i]));
785  }
786  return result;
787  }
788 
790  {
791  std::swap(this->m_deg, other.m_deg);
792  std::swap(this->m_sp_field, other.m_sp_field);
793  std::swap(this->coeff, other.coeff);
794  }
795 
796 bool polyn_gf2m::operator==(const polyn_gf2m & other) const
797  {
798  if(m_deg != other.m_deg || coeff != other.coeff)
799  {
800  return false;
801  }
802  return true;
803  }
804 
805 }
BigInt const BigInt & x
Definition: numthry.h:139
std::string size_t len
Definition: pk_keys.h:305
bool RandomNumberGenerator & rng
Definition: numthry.h:176
int get_degree() const
Definition: polyn_gf2m.cpp:228
BigInt size_t n
Definition: bigint.h:1096
bool const OID & b
Definition: asn1_oid.h:109
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:111
gf2m decode_gf2m(const uint8_t *mem)
int calc_degree_secure() const
Definition: polyn_gf2m.cpp:46
BigInt const BigInt & p
Definition: numthry.h:150
constexpr uint8_t get_byte(size_t byte_num, T input)
Definition: loadstor.h:39
bool operator==(const polyn_gf2m &other) const
Definition: polyn_gf2m.cpp:796
void set_coef(uint32_t i, gf2m v)
Definition: polyn_gf2m.h:86
void const BigInt BigInt BigInt & r
Definition: divide.h:23
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:213
polyn_gf2m sqmod(const std::vector< polyn_gf2m > &sq, int d)
Definition: polyn_gf2m.cpp:323
void degppf(const polyn_gf2m &g, int *p_result)
Definition: polyn_gf2m.cpp:390
static std::vector< polyn_gf2m > sqrt_mod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:675
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
void patchup_deg_secure(uint32_t trgt_deg, volatile gf2m patch_elem)
Definition: polyn_gf2m.cpp:429
size_t const BigInt & a
Definition: numthry.h:111
gf2m lex_to_gray(gf2m lex)
uint16_t expand_mask_16bit(T tst)
BigInt const BigInt & d
Definition: bigint.h:1093
uint16_t gf2m
Definition: gf2m_small_m.h:20
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:122
Definition: alg_id.cpp:13
static std::vector< polyn_gf2m > sqmod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:289
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
gf2m random_code_element(unsigned code_length, RandomNumberGenerator &rng)
Definition: polyn_gf2m.cpp:71
uint32_t encode_gf2m(gf2m to_enc, uint8_t *mem)
uint32_t code_length
std::vector< polyn_gf2m > syndrome_init(polyn_gf2m const &generator, std::vector< gf2m > const &support, int n)
Definition: polyn_gf2m.cpp:720
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
void const BigInt BigInt & q
Definition: divide.h:23
std::pair< BigInt, SymmetricKey > BOTAN_PUBLIC_API(2, 0) srp6_client_agree(const std std::pair< BigInt, SymmetricKey > BOTAN_PUBLIC_API(2, 11) srp6_client_agree(const std BigInt BOTAN_PUBLIC_API(2, 0) generate_srp6_verifier(const std BigInt BOTAN_PUBLIC_API(2, 11) generate_srp6_verifier(const std std::string const BigInt & g
Definition: srp6.h:102
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
const BigInt const PointGFp & p2
Definition: point_gfp.h:350
class BOTAN_PUBLIC_API(2, 11) Argon2 final class BOTAN_PUBLIC_API(2, 11) Argon2_Family final void size_t const char size_t const uint8_t size_t const uint8_t size_t const uint8_t size_t uint8_t size_t size_t size_t t
Definition: argon2.h:87
constexpr uint16_t make_uint16(uint8_t i0, uint8_t i1)
Definition: loadstor.h:52
secure_vector< uint8_t > encode() const
Definition: polyn_gf2m.cpp:768
gf2m random_gf2m(RandomNumberGenerator &rng)
Definition: polyn_gf2m.cpp:64
std::string to_string() const
Definition: polyn_gf2m.cpp:104
void swap(polyn_gf2m &other)
Definition: polyn_gf2m.cpp:789
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:156
gf2m eval(gf2m a)
Definition: polyn_gf2m.cpp:254