Botan  2.15.0
Crypto and TLS for C++11
Public Member Functions | Static Public Member Functions | Public Attributes | List of all members
Botan::polyn_gf2m Class Reference

#include <polyn_gf2m.h>

Public Member Functions

void add_to_coef (size_t i, gf2m v)
 
int calc_degree_secure () const
 
size_t degppf (const polyn_gf2m &g)
 
secure_vector< uint8_t > encode () const
 
void encode (uint32_t min_numo_coeffs, uint8_t *mem, uint32_t mem_len) const
 
gf2m eval (gf2m a)
 
gf2m get_coef (size_t i) const
 
int get_degree () const
 
gf2m get_lead_coef () const
 
std::shared_ptr< GF2m_Fieldget_sp_field () const
 
bool operator!= (const polyn_gf2m &other) const
 
polyn_gf2moperator= (const polyn_gf2m &)=default
 
polyn_gf2moperator= (polyn_gf2m &&other)
 
bool operator== (const polyn_gf2m &other) const
 
gf2moperator[] (size_t i)
 
gf2m operator[] (size_t i) const
 
void patchup_deg_secure (uint32_t trgt_deg, volatile gf2m patch_elem)
 
 polyn_gf2m (std::shared_ptr< GF2m_Field > sp_field)
 
 polyn_gf2m ()
 
 polyn_gf2m (const secure_vector< uint8_t > &encoded, std::shared_ptr< GF2m_Field > sp_field)
 
 polyn_gf2m (int d, std::shared_ptr< GF2m_Field > sp_field)
 
 polyn_gf2m (polyn_gf2m const &other)
 
 polyn_gf2m (size_t t, RandomNumberGenerator &rng, std::shared_ptr< GF2m_Field > sp_field)
 
 polyn_gf2m (const uint8_t *mem, uint32_t mem_len, std::shared_ptr< GF2m_Field > sp_field)
 
 polyn_gf2m (int degree, const uint8_t *mem, size_t mem_byte_len, std::shared_ptr< GF2m_Field > sp_field)
 
 polyn_gf2m (polyn_gf2m &&other)
 
void set_coef (size_t i, gf2m v)
 
void set_to_zero ()
 
polyn_gf2m sqmod (const std::vector< polyn_gf2m > &sq, int d)
 
void swap (polyn_gf2m &other)
 
std::string to_string () const
 

Static Public Member Functions

static std::pair< polyn_gf2m, polyn_gf2meea_with_coefficients (const polyn_gf2m &p, const polyn_gf2m &g, int break_deg)
 
static std::vector< polyn_gf2msqmod_init (const polyn_gf2m &g)
 
static std::vector< polyn_gf2msqrt_mod_init (const polyn_gf2m &g)
 

Public Attributes

secure_vector< gf2mcoeff
 
int m_deg
 
std::shared_ptr< GF2m_Fieldm_sp_field
 

Detailed Description

Definition at line 26 of file polyn_gf2m.h.

Constructor & Destructor Documentation

◆ polyn_gf2m() [1/9]

Botan::polyn_gf2m::polyn_gf2m ( std::shared_ptr< GF2m_Field sp_field)
explicit

create a zero polynomial:

Definition at line 153 of file polyn_gf2m.cpp.

153  :
154  m_deg(-1), coeff(1), m_sp_field(sp_field)
155  {}
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

◆ polyn_gf2m() [2/9]

Botan::polyn_gf2m::polyn_gf2m ( )
inline

Definition at line 34 of file polyn_gf2m.h.

Referenced by sqmod_init(), and sqrt_mod_init().

34 : m_deg(-1) {}

◆ polyn_gf2m() [3/9]

Botan::polyn_gf2m::polyn_gf2m ( const secure_vector< uint8_t > &  encoded,
std::shared_ptr< GF2m_Field sp_field 
)

Definition at line 754 of file polyn_gf2m.cpp.

References coeff, and get_degree().

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  }
int get_degree() const
Definition: polyn_gf2m.cpp:228
uint16_t gf2m
Definition: gf2m_small_m.h:23
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

◆ polyn_gf2m() [4/9]

Botan::polyn_gf2m::polyn_gf2m ( int  d,
std::shared_ptr< GF2m_Field sp_field 
)

create zero polynomial with reservation of space for a degree d polynomial

Definition at line 97 of file polyn_gf2m.cpp.

98  :m_deg(-1),
99  coeff(d+1),
100  m_sp_field(sp_field)
101  {
102  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

◆ polyn_gf2m() [5/9]

Botan::polyn_gf2m::polyn_gf2m ( polyn_gf2m const &  other)

Definition at line 91 of file polyn_gf2m.cpp.

92  :m_deg(other.m_deg),
93  coeff(other.coeff),
94  m_sp_field(other.m_sp_field)
95  { }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

◆ polyn_gf2m() [6/9]

Botan::polyn_gf2m::polyn_gf2m ( size_t  t,
RandomNumberGenerator rng,
std::shared_ptr< GF2m_Field sp_field 
)

random irreducible polynomial of degree t

Definition at line 639 of file polyn_gf2m.cpp.

References degppf(), Botan::random_code_element(), and set_coef().

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  }
size_t degppf(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:390
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
gf2m random_code_element(uint16_t code_length, RandomNumberGenerator &rng)
Definition: polyn_gf2m.cpp:71
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155
void set_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:93

◆ polyn_gf2m() [7/9]

Botan::polyn_gf2m::polyn_gf2m ( const uint8_t *  mem,
uint32_t  mem_len,
std::shared_ptr< GF2m_Field sp_field 
)

decode a polynomial from memory:

Definition at line 126 of file polyn_gf2m.cpp.

References coeff, Botan::decode_gf2m(), get_degree(), and m_deg.

126  :
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  }
int get_degree() const
Definition: polyn_gf2m.cpp:228
gf2m decode_gf2m(const uint8_t *mem)
uint16_t gf2m
Definition: gf2m_small_m.h:23
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

◆ polyn_gf2m() [8/9]

Botan::polyn_gf2m::polyn_gf2m ( int  degree,
const uint8_t *  mem,
size_t  mem_byte_len,
std::shared_ptr< GF2m_Field sp_field 
)

create a polynomial from memory area (encoded)

Definition at line 157 of file polyn_gf2m.cpp.

References coeff, get_degree(), and m_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  }
int get_degree() const
Definition: polyn_gf2m.cpp:228
uint16_t gf2m
Definition: gf2m_small_m.h:23
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

◆ polyn_gf2m() [9/9]

Botan::polyn_gf2m::polyn_gf2m ( polyn_gf2m &&  other)
inline

Definition at line 64 of file polyn_gf2m.h.

References swap().

65  {
66  this->swap(other);
67  }
void swap(polyn_gf2m &other)
Definition: polyn_gf2m.cpp:790

Member Function Documentation

◆ add_to_coef()

void Botan::polyn_gf2m::add_to_coef ( size_t  i,
gf2m  v 
)
inline

Definition at line 98 of file polyn_gf2m.h.

References coeff.

99  {
100  coeff[i] ^= v;
101  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ calc_degree_secure()

int Botan::polyn_gf2m::calc_degree_secure ( ) const

determine the degree in a timing secure manner. the timing of this function only depends on the number of allocated coefficients, not on the actual degree

Definition at line 46 of file polyn_gf2m.cpp.

References coeff, Botan::expand_mask_16bit(), and m_deg.

Referenced by eea_with_coefficients(), and patchup_deg_secure().

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  }
uint16_t expand_mask_16bit(T tst)
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ degppf()

size_t Botan::polyn_gf2m::degppf ( const polyn_gf2m g)

Definition at line 390 of file polyn_gf2m.cpp.

References get_degree(), get_sp_field(), m_sp_field, set_coef(), sqmod(), and sqmod_init().

Referenced by polyn_gf2m().

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  }
static std::vector< polyn_gf2m > sqmod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:289
void set_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:93

◆ eea_with_coefficients()

std::pair< polyn_gf2m, polyn_gf2m > Botan::polyn_gf2m::eea_with_coefficients ( const polyn_gf2m p,
const polyn_gf2m g,
int  break_deg 
)
static

countermeasure against the low weight attacks for w=4, w=6 and w=8. Higher values are not covered since for w=8 we already have a probability for a positive of 1/n^3 from random ciphertexts with the given weight. For w = 10 it would be 1/n^4 and so on. Thus attacks based on such high values of w are considered impractical.

The outer test for the degree of u ( Omega in the paper ) needs not to be disguised. Each of the three is performed at most once per EEA (syndrome inversion) execution, the attacker knows this already when preparing the ciphertext with the given weight. Inside these three cases however, we must use timing neutral (branch free) operations to implement the condition detection and the counteractions.

Condition that the EEA would break now

Now come the conditions for all odd coefficients of this sigma candiate. If they are all fulfilled, then we know that we have a low weight error vector, since the key-equation solving EEA is skipped if the degree of tau^2 is low (=m_deg(u0)) and all its odd cofficients are zero (they would cause "full-length" contributions from the square root computation).

Definition at line 448 of file polyn_gf2m.cpp.

References BOTAN_ASSERT, calc_degree_secure(), coeff, Botan::expand_mask_16bit(), get_degree(), m_sp_field, patchup_deg_secure(), set_coef(), and set_to_zero().

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  }
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
uint16_t expand_mask_16bit(T tst)
uint16_t gf2m
Definition: gf2m_small_m.h:23
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155
void set_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:93

◆ encode() [1/2]

secure_vector< uint8_t > Botan::polyn_gf2m::encode ( ) const

Definition at line 769 of file polyn_gf2m.cpp.

References coeff, Botan::get_byte(), and m_deg.

Referenced by Botan::McEliece_PrivateKey::private_key_bits().

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  }
constexpr uint8_t get_byte(size_t byte_num, T input)
Definition: loadstor.h:41
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ encode() [2/2]

void Botan::polyn_gf2m::encode ( uint32_t  min_numo_coeffs,
uint8_t *  mem,
uint32_t  mem_len 
) const

◆ eval()

gf2m Botan::polyn_gf2m::eval ( gf2m  a)

Definition at line 254 of file polyn_gf2m.cpp.

References m_deg, and m_sp_field.

255  {
256  return eval_aux(&this->coeff[0], a, this->m_deg, this->m_sp_field);
257  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

◆ get_coef()

gf2m Botan::polyn_gf2m::get_coef ( size_t  i) const
inline

Definition at line 91 of file polyn_gf2m.h.

References coeff.

91 { return coeff[i]; }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ get_degree()

int Botan::polyn_gf2m::get_degree ( ) const

Definition at line 228 of file polyn_gf2m.cpp.

References coeff, and m_deg.

Referenced by degppf(), eea_with_coefficients(), Botan::mceliece_decrypt(), Botan::McEliece_PrivateKey::McEliece_PrivateKey(), polyn_gf2m(), sqmod(), sqmod_init(), sqrt_mod_init(), Botan::syndrome_init(), and to_string().

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  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ get_lead_coef()

gf2m Botan::polyn_gf2m::get_lead_coef ( ) const
inline

Definition at line 89 of file polyn_gf2m.h.

References coeff, and m_deg.

89 { return coeff[m_deg]; }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ get_sp_field()

std::shared_ptr<GF2m_Field> Botan::polyn_gf2m::get_sp_field ( ) const
inline

Definition at line 82 of file polyn_gf2m.h.

References m_sp_field.

Referenced by degppf(), Botan::mceliece_decrypt(), sqmod_init(), and sqrt_mod_init().

83  { return m_sp_field; }
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

◆ operator!=()

bool Botan::polyn_gf2m::operator!= ( const polyn_gf2m other) const
inline

Definition at line 62 of file polyn_gf2m.h.

62 { return !(*this == other); }

◆ operator=() [1/2]

polyn_gf2m& Botan::polyn_gf2m::operator= ( const polyn_gf2m )
default

◆ operator=() [2/2]

polyn_gf2m& Botan::polyn_gf2m::operator= ( polyn_gf2m &&  other)
inline

Definition at line 69 of file polyn_gf2m.h.

References swap().

70  {
71  if(this != &other)
72  {
73  this->swap(other);
74  }
75  return *this;
76  }
void swap(polyn_gf2m &other)
Definition: polyn_gf2m.cpp:790

◆ operator==()

bool Botan::polyn_gf2m::operator== ( const polyn_gf2m other) const

Definition at line 797 of file polyn_gf2m.cpp.

References coeff, and m_deg.

798  {
799  if(m_deg != other.m_deg || coeff != other.coeff)
800  {
801  return false;
802  }
803  return true;
804  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ operator[]() [1/2]

gf2m& Botan::polyn_gf2m::operator[] ( size_t  i)
inline

Definition at line 85 of file polyn_gf2m.h.

References coeff.

85 { return coeff[i]; }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ operator[]() [2/2]

gf2m Botan::polyn_gf2m::operator[] ( size_t  i) const
inline

Definition at line 87 of file polyn_gf2m.h.

References coeff.

87 { return coeff[i]; }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ patchup_deg_secure()

void Botan::polyn_gf2m::patchup_deg_secure ( uint32_t  trgt_deg,
volatile gf2m  patch_elem 
)

Definition at line 429 of file polyn_gf2m.cpp.

References calc_degree_secure(), and Botan::expand_mask_16bit().

Referenced by eea_with_coefficients().

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  }
int calc_degree_secure() const
Definition: polyn_gf2m.cpp:46
uint16_t expand_mask_16bit(T tst)
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ set_coef()

void Botan::polyn_gf2m::set_coef ( size_t  i,
gf2m  v 
)
inline

Definition at line 93 of file polyn_gf2m.h.

References coeff.

Referenced by degppf(), eea_with_coefficients(), polyn_gf2m(), sqmod(), sqmod_init(), and sqrt_mod_init().

94  {
95  coeff[i] = v;
96  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ set_to_zero()

void Botan::polyn_gf2m::set_to_zero ( )

Definition at line 222 of file polyn_gf2m.cpp.

References Botan::clear_mem(), coeff, and m_deg.

Referenced by eea_with_coefficients().

223  {
224  clear_mem(&this->coeff[0], this->coeff.size());
225  this->m_deg = -1;
226  }
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ sqmod()

polyn_gf2m Botan::polyn_gf2m::sqmod ( const std::vector< polyn_gf2m > &  sq,
int  d 
)

Definition at line 323 of file polyn_gf2m.cpp.

References get_degree(), m_sp_field, and set_coef().

Referenced by degppf(), and sqrt_mod_init().

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  }
uint16_t gf2m
Definition: gf2m_small_m.h:23
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155
void set_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:93

◆ sqmod_init()

std::vector< polyn_gf2m > Botan::polyn_gf2m::sqmod_init ( const polyn_gf2m g)
static

Definition at line 289 of file polyn_gf2m.cpp.

References Botan::clear_mem(), coeff, Botan::copy_mem(), get_degree(), get_sp_field(), m_deg, polyn_gf2m(), and set_coef().

Referenced by degppf(), and sqrt_mod_init().

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  }
int get_degree() const
Definition: polyn_gf2m.cpp:228
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:133
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
void set_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:93

◆ sqrt_mod_init()

std::vector< polyn_gf2m > Botan::polyn_gf2m::sqrt_mod_init ( const polyn_gf2m g)
static

Definition at line 676 of file polyn_gf2m.cpp.

References get_degree(), get_sp_field(), m_sp_field, polyn_gf2m(), set_coef(), sqmod(), and sqmod_init().

Referenced by Botan::generate_mceliece_key().

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  }
static std::vector< polyn_gf2m > sqmod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:289
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155
void set_coef(size_t i, gf2m v)
Definition: polyn_gf2m.h:93

◆ swap()

void Botan::polyn_gf2m::swap ( polyn_gf2m other)

Definition at line 790 of file polyn_gf2m.cpp.

References coeff, m_deg, and m_sp_field.

Referenced by operator=(), and polyn_gf2m().

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  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:155

◆ to_string()

std::string Botan::polyn_gf2m::to_string ( ) const

Definition at line 104 of file polyn_gf2m.cpp.

References coeff, get_degree(), and Botan::ASN1::to_string().

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  }
int get_degree() const
Definition: polyn_gf2m.cpp:228
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:213
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

Member Data Documentation

◆ coeff

secure_vector<gf2m> Botan::polyn_gf2m::coeff

◆ m_deg

int Botan::polyn_gf2m::m_deg

◆ m_sp_field

std::shared_ptr<GF2m_Field> Botan::polyn_gf2m::m_sp_field

The documentation for this class was generated from the following files: