Botan  2.4.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 (uint32_t i, gf2m v)
 
int calc_degree_secure () const
 
void degppf (const polyn_gf2m &g, int *p_result)
 
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 (uint32_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 (polyn_gf2m &&other)
 
 polyn_gf2m (int d, std::shared_ptr< GF2m_Field > sp_field)
 
 polyn_gf2m (polyn_gf2m const &other)
 
 polyn_gf2m (int 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 unsigned char *mem, uint32_t mem_byte_len, std::shared_ptr< GF2m_Field > sp_field)
 
void set_coef (uint32_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_Fieldmsp_field
 

Detailed Description

Definition at line 23 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.

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

◆ polyn_gf2m() [2/9]

Botan::polyn_gf2m::polyn_gf2m ( )
inline

Definition at line 31 of file polyn_gf2m.h.

References operator=(), and operator==().

Referenced by add_to_coef(), operator=(), sqmod(), sqmod_init(), sqrt_mod_init(), and Botan::syndrome_init().

32  :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 755 of file polyn_gf2m.cpp.

References get_degree().

756  :msp_field(sp_field)
757  {
758  if(encoded.size() % 2)
759  {
760  throw Decoding_Error("encoded polynomial has odd length");
761  }
762  for(uint32_t i = 0; i < encoded.size(); i += 2)
763  {
764  gf2m el = (encoded[i] << 8) | encoded[i + 1];
765  coeff.push_back(el);
766  }
767  get_degree();
768 
769  }
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:155
int get_degree() const
Definition: polyn_gf2m.cpp:230
uint16_t gf2m
Definition: gf2m_small_m.h:20
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ polyn_gf2m() [4/9]

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

Definition at line 42 of file polyn_gf2m.h.

References swap().

43  {
44  this->swap(other);
45  }
void swap(polyn_gf2m &other)
Definition: polyn_gf2m.cpp:791

◆ polyn_gf2m() [5/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  msp_field(sp_field)
101  {
102  }
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:155
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ polyn_gf2m() [6/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  msp_field(other.msp_field)
95  { }
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:155
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ polyn_gf2m() [7/9]

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

create zero polynomial with allocated size determined by specified degree d: random irreducible polynomial of degree t

Definition at line 641 of file polyn_gf2m.cpp.

References coeff, degppf(), get_degree(), msp_field, and Botan::random_code_element().

642  :m_deg(t),
643  coeff(t+1),
644  msp_field(sp_field)
645  {
646  (*this).set_coef( t, 1);
647  int degree = 0;
648  do
649  {
650  for (int i = 0; i < t; ++i)
651  {
652  (*this).set_coef( i, random_code_element(sp_field->get_cardinality(), rng));
653  }
654  polyn_gf2m::degppf(*this, &degree);
655  }
656  while (degree < t);
657  }
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:155
void degppf(const polyn_gf2m &g, int *p_result)
Definition: polyn_gf2m.cpp:392
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152
gf2m random_code_element(unsigned code_length, RandomNumberGenerator &rng)
Definition: polyn_gf2m.cpp:71

◆ polyn_gf2m() [8/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.

127  :msp_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  }
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:155
int get_degree() const
Definition: polyn_gf2m.cpp:230
gf2m decode_gf2m(const uint8_t *mem)
uint16_t gf2m
Definition: gf2m_small_m.h:20
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ polyn_gf2m() [9/9]

Botan::polyn_gf2m::polyn_gf2m ( int  degree,
const unsigned char *  mem,
uint32_t  mem_byte_len,
std::shared_ptr< GF2m_Field sp_field 
)

create a polynomial from memory area (encoded)

Definition at line 159 of file polyn_gf2m.cpp.

References coeff, encode(), Botan::encode_gf2m(), get_degree(), m_deg, and msp_field.

160  :msp_field(sp_field)
161  {
162  uint32_t j, k, l;
163  gf2m a;
164  uint32_t polyn_size;
165  polyn_size = degree + 1;
166  if(polyn_size * sp_field->get_extension_degree() > 8 * mem_byte_len)
167  {
168  throw Botan::Decoding_Error("memory vector for polynomial has wrong size");
169  }
170  this->coeff = secure_vector<gf2m>(degree+1);
171  gf2m ext_deg = this->msp_field->get_extension_degree();
172  for (l = 0; l < polyn_size; l++)
173  {
174  k = (l * ext_deg) / 8;
175 
176  j = (l * ext_deg) % 8;
177  a = mem[k] >> j;
178  if (j + ext_deg > 8)
179  {
180  a ^= mem[k + 1] << (8- j);
181  }
182  if(j + ext_deg > 16)
183  {
184  a ^= mem[k + 2] << (16- j);
185  }
186  a &= ((1 << ext_deg) - 1);
187  (*this).set_coef( l, a);
188  }
189 
190  this->get_degree();
191  }
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:155
int get_degree() const
Definition: polyn_gf2m.cpp:230
uint16_t gf2m
Definition: gf2m_small_m.h:20
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

Member Function Documentation

◆ add_to_coef()

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

◆ 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 add_to_coef(), eea_with_coefficients(), and patchup_deg_secure().

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

◆ degppf()

void Botan::polyn_gf2m::degppf ( const polyn_gf2m g,
int *  p_result 
)

Definition at line 392 of file polyn_gf2m.cpp.

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

Referenced by add_to_coef(), and polyn_gf2m().

393  {
394  int i, d;
395  polyn_gf2m s(g.get_sp_field());
396 
397  d = g.get_degree();
398  std::vector<polyn_gf2m> u = polyn_gf2m::sqmod_init(g);
399 
400  polyn_gf2m p( d - 1, g.msp_field);
401 
402  p.set_degree( 1);
403  (*&p).set_coef( 1, 1);
404  (*p_result) = d;
405  for (i = 1; i <= (d / 2) * g.msp_field->get_extension_degree(); ++i)
406  {
407  polyn_gf2m r = p.sqmod(u, d);
408  if ((i % g.msp_field->get_extension_degree()) == 0)
409  {
410  r[1] ^= 1;
411  r.get_degree(); // The degree may change
412  s = polyn_gf2m::gcd( g, r);
413 
414  if (s.get_degree() > 0)
415  {
416  (*p_result) = i / g.msp_field->get_extension_degree();
417  break;
418  }
419  r[1] ^= 1;
420  r.get_degree(); // The degree may change
421  }
422  // No need for the exchange s
423  s = p;
424  p = r;
425  r = s;
426  }
427 
428 
429  }
void set_coef(uint32_t i, gf2m v)
Definition: polyn_gf2m.h:85
static std::vector< polyn_gf2m > sqmod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:291

◆ 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 450 of file polyn_gf2m.cpp.

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

Referenced by add_to_coef().

451  {
452 
453  std::shared_ptr<GF2m_Field> msp_field = g.msp_field;
454  int i, j, dr, du, delta;
455  gf2m a;
456  polyn_gf2m aux;
457 
458  // initialisation of the local variables
459  // r0 <- g, r1 <- p, u0 <- 0, u1 <- 1
460  dr = g.get_degree();
461 
462  BOTAN_ASSERT(dr > 3, "Valid polynomial");
463 
464  polyn_gf2m r0(dr, g.msp_field);
465  polyn_gf2m r1(dr - 1, g.msp_field);
466  polyn_gf2m u0(dr - 1, g.msp_field);
467  polyn_gf2m u1(dr - 1, g.msp_field);
468 
469  r0 = g;
470  r1 = p;
471  u0.set_to_zero();
472  u1.set_to_zero();
473  (*&u1).set_coef( 0, 1);
474  u1.set_degree( 0);
475 
476 
477  // invariants:
478  // r1 = u1 * p + v1 * g
479  // r0 = u0 * p + v0 * g
480  // and m_deg(u1) = m_deg(g) - m_deg(r0)
481  // It stops when m_deg (r1) <t (m_deg (r0)> = t)
482  // And therefore m_deg (u1) = m_deg (g) - m_deg (r0) <m_deg (g) - break_deg
483  du = 0;
484  dr = r1.get_degree();
485  delta = r0.get_degree() - dr;
486 
487 
488  while (dr >= break_deg)
489  {
490 
491  for (j = delta; j >= 0; --j)
492  {
493  a = msp_field->gf_div(r0[dr + j], r1[dr]);
494  if (a != 0)
495  {
496  gf2m la = msp_field->gf_log(a);
497  // u0(z) <- u0(z) + a * u1(z) * z^j
498  for (i = 0; i <= du; ++i)
499  {
500  u0[i + j] ^= msp_field->gf_mul_zrz(la, u1[i]);
501  }
502  // r0(z) <- r0(z) + a * r1(z) * z^j
503  for (i = 0; i <= dr; ++i)
504  {
505  r0[i + j] ^= msp_field->gf_mul_zrz(la, r1[i]);
506  }
507  }
508  } // end loop over j
509 
510  if(break_deg != 1) /* key eq. solving */
511  {
512  /* [ssms_icisc09] Countermeasure
513  * d_break from paper equals break_deg - 1
514  * */
515 
516  volatile gf2m fake_elem = 0x01;
517  volatile gf2m cond1, cond2;
518  int trgt_deg = r1.get_degree() - 1;
519  r0.calc_degree_secure();
520  u0.calc_degree_secure();
521  if(!(g.get_degree() % 2))
522  {
523  /* t even */
524  cond1 = r0.get_degree() < break_deg - 1;
525  }
526  else
527  {
528  /* t odd */
529  cond1 = r0.get_degree() < break_deg;
530  cond2 = u0.get_degree() < break_deg - 1;
531  cond1 &= cond2;
532  }
533  /* expand cond1 to a full mask */
534  gf2m mask = generate_gf2m_mask(cond1);
535  fake_elem &= mask;
536  r0.patchup_deg_secure(trgt_deg, fake_elem);
537  }
538  if(break_deg == 1) /* syndrome inversion */
539  {
540  volatile gf2m fake_elem = 0x00;
541  volatile uint32_t trgt_deg = 0;
542  r0.calc_degree_secure();
543  u0.calc_degree_secure();
544  /**
545  * countermeasure against the low weight attacks for w=4, w=6 and w=8.
546  * Higher values are not covered since for w=8 we already have a
547  * probability for a positive of 1/n^3 from random ciphertexts with the
548  * given weight. For w = 10 it would be 1/n^4 and so on. Thus attacks
549  * based on such high values of w are considered impractical.
550  *
551  * The outer test for the degree of u ( Omega in the paper ) needs not to
552  * be disguised. Each of the three is performed at most once per EEA
553  * (syndrome inversion) execution, the attacker knows this already when
554  * preparing the ciphertext with the given weight. Inside these three
555  * cases however, we must use timing neutral (branch free) operations to
556  * implement the condition detection and the counteractions.
557  *
558  */
559  if(u0.get_degree() == 4)
560  {
561  uint32_t mask = 0;
562  /**
563  * Condition that the EEA would break now
564  */
565  int cond_r = r0.get_degree() == 0;
566  /**
567  * Now come the conditions for all odd coefficients of this sigma
568  * candiate. If they are all fulfilled, then we know that we have a low
569  * weight error vector, since the key-equation solving EEA is skipped if
570  * the degree of tau^2 is low (=m_deg(u0)) and all its odd cofficients are
571  * zero (they would cause "full-length" contributions from the square
572  * root computation).
573  */
574  // Condition for the coefficient to Y to be cancelled out by the
575  // addition of Y before the square root computation:
576  int cond_u1 = msp_field->gf_mul(u0.coeff[1], msp_field->gf_inv(r0.coeff[0])) == 1;
577 
578  // Condition sigma_3 = 0:
579  int cond_u3 = u0.coeff[3] == 0;
580  // combine the conditions:
581  cond_r &= (cond_u1 & cond_u3);
582  // mask generation:
583  mask = expand_mask_16bit(cond_r);
584  trgt_deg = 2 & mask;
585  fake_elem = 1 & mask;
586  }
587  else if(u0.get_degree() == 6)
588  {
589  uint32_t mask = 0;
590  int cond_r= r0.get_degree() == 0;
591  int cond_u1 = msp_field->gf_mul(u0.coeff[1], msp_field->gf_inv(r0.coeff[0])) == 1;
592  int cond_u3 = u0.coeff[3] == 0;
593 
594  int cond_u5 = u0.coeff[5] == 0;
595 
596  cond_r &= (cond_u1 & cond_u3 & cond_u5);
597  mask = expand_mask_16bit(cond_r);
598  trgt_deg = 4 & mask;
599  fake_elem = 1 & mask;
600  }
601  else if(u0.get_degree() == 8)
602  {
603  uint32_t mask = 0;
604  int cond_r= r0.get_degree() == 0;
605  int cond_u1 = msp_field->gf_mul(u0[1], msp_field->gf_inv(r0[0])) == 1;
606  int cond_u3 = u0.coeff[3] == 0;
607 
608  int cond_u5 = u0.coeff[5] == 0;
609 
610  int cond_u7 = u0.coeff[7] == 0;
611 
612  cond_r &= (cond_u1 & cond_u3 & cond_u5 & cond_u7);
613  mask = expand_mask_16bit(cond_r);
614  trgt_deg = 6 & mask;
615  fake_elem = 1 & mask;
616  }
617  r0.patchup_deg_secure(trgt_deg, fake_elem);
618  }
619  // exchange
620  aux = r0; r0 = r1; r1 = aux;
621  aux = u0; u0 = u1; u1 = aux;
622 
623  du = du + delta;
624  delta = 1;
625  while (r1[dr - delta] == 0)
626  {
627  delta++;
628  }
629 
630 
631  dr -= delta;
632  } /* end while loop (dr >= break_deg) */
633 
634 
635  u1.set_degree( du);
636  r1.set_degree( dr);
637  //return u1 and r1;
638  return std::make_pair(u1,r1); // coefficients u,v
639  }
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:155
void set_coef(uint32_t i, gf2m v)
Definition: polyn_gf2m.h:85
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:29
uint16_t expand_mask_16bit(T tst)
uint16_t gf2m
Definition: gf2m_small_m.h:20

◆ encode() [1/2]

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

Definition at line 770 of file polyn_gf2m.cpp.

References m_deg.

Referenced by add_to_coef(), operator=(), polyn_gf2m(), and Botan::McEliece_PrivateKey::private_key_bits().

771  {
772  secure_vector<uint8_t> result;
773 
774  if(m_deg < 1)
775  {
776  result.push_back(0);
777  result.push_back(0);
778  return result;
779  }
780 
781  uint32_t len = m_deg+1;
782  for(unsigned i = 0; i < len; i++)
783  {
784  // "big endian" encoding of the GF(2^m) elements
785  result.push_back(coeff[i] >> 8);
786  result.push_back(coeff[i]);
787  }
788  return result;
789  }
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 256 of file polyn_gf2m.cpp.

References BOTAN_ASSERT, get_degree(), get_lead_coef(), m_deg, msp_field, and set_coef().

Referenced by add_to_coef().

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

◆ get_coef()

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

Definition at line 83 of file polyn_gf2m.h.

References coeff.

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

◆ get_degree()

int Botan::polyn_gf2m::get_degree ( ) const

Definition at line 230 of file polyn_gf2m.cpp.

References coeff, and m_deg.

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

231  {
232  int d = this->coeff.size() - 1;
233  while ((d >= 0) && (this->coeff[d] == 0))
234  --d;
235  const_cast<polyn_gf2m*>(this)->m_deg = d;
236  return d;
237  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ get_lead_coef()

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

Definition at line 81 of file polyn_gf2m.h.

References coeff, and m_deg.

Referenced by eval().

81 { 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 74 of file polyn_gf2m.h.

References msp_field.

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

75  { return msp_field; }
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:155

◆ operator!=()

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

Definition at line 40 of file polyn_gf2m.h.

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

◆ operator=() [1/2]

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

Referenced by polyn_gf2m().

◆ operator=() [2/2]

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

Definition at line 47 of file polyn_gf2m.h.

References encode(), polyn_gf2m(), and swap().

48  {
49  if(this != &other)
50  {
51  this->swap(other);
52  }
53  return *this;
54  }
void swap(polyn_gf2m &other)
Definition: polyn_gf2m.cpp:791

◆ operator==()

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

Definition at line 798 of file polyn_gf2m.cpp.

References coeff, and m_deg.

Referenced by polyn_gf2m().

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

◆ operator[]() [1/2]

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

Definition at line 77 of file polyn_gf2m.h.

References coeff.

77 { 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 79 of file polyn_gf2m.h.

References coeff.

79 { 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 431 of file polyn_gf2m.cpp.

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

Referenced by add_to_coef(), and eea_with_coefficients().

432  {
433  uint32_t i;
434  if(this->coeff.size() < trgt_deg)
435  {
436  return;
437  }
438  for(i = 0; i < this->coeff.size(); i++)
439  {
440  uint32_t equal, equal_mask;
441  this->coeff[i] |= patch_elem;
442  equal = (i == trgt_deg);
443  equal_mask = expand_mask_16bit(equal);
444  patch_elem &= ~equal_mask;
445  }
446  this->calc_degree_secure();
447  }
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 ( uint32_t  i,
gf2m  v 
)
inline

Definition at line 85 of file polyn_gf2m.h.

References coeff.

Referenced by degppf(), eea_with_coefficients(), eval(), sqmod(), sqmod_init(), sqrt_mod_init(), and Botan::syndrome_init().

86  {
87  coeff[i] = v;
88  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ set_to_zero()

void Botan::polyn_gf2m::set_to_zero ( )

Definition at line 224 of file polyn_gf2m.cpp.

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

Referenced by add_to_coef(), and eea_with_coefficients().

225  {
226  clear_mem(&this->coeff[0], this->coeff.size());
227  this->m_deg = -1;
228  }
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:86
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 325 of file polyn_gf2m.cpp.

References get_degree(), msp_field, polyn_gf2m(), and set_coef().

Referenced by add_to_coef(), degppf(), and sqrt_mod_init().

326  {
327  int i, j;
328  gf2m la;
329  std::shared_ptr<GF2m_Field> sp_field = this->msp_field;
330 
331  polyn_gf2m result(d - 1, sp_field);
332  // terms of low degree
333  for (i = 0; i < d / 2; ++i)
334  {
335  (*&result).set_coef( i * 2, sp_field->gf_square((*this)[i]));
336  }
337 
338  // terms of high degree
339  for (; i < d; ++i)
340  {
341  gf2m lpi = (*this)[i];
342  if (lpi != 0)
343  {
344  lpi = sp_field->gf_log(lpi);
345  la = sp_field->gf_mul_rrr(lpi, lpi);
346  for (j = 0; j < d; ++j)
347  {
348  result[j] ^= sp_field->gf_mul_zrz(la, sq[i][j]);
349  }
350  }
351  }
352 
353  // Update degre
354  result.set_degree( d - 1);
355  while ((result.get_degree() >= 0) && (result[result.get_degree()] == 0))
356  result.set_degree( result.get_degree() - 1);
357  return result;
358  }
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:155
void set_coef(uint32_t i, gf2m v)
Definition: polyn_gf2m.h:85
uint16_t gf2m
Definition: gf2m_small_m.h:20

◆ sqmod_init()

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

Definition at line 291 of file polyn_gf2m.cpp.

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

Referenced by add_to_coef(), degppf(), and sqrt_mod_init().

292  {
293  std::vector<polyn_gf2m> sq;
294  const int signed_deg = g.get_degree();
295  if(signed_deg <= 0)
296  throw Invalid_Argument("cannot compute sqmod for such low degree");
297 
298  const uint32_t d = static_cast<uint32_t>(signed_deg);
299  uint32_t t = g.m_deg;
300  // create t zero polynomials
301  uint32_t i;
302  for (i = 0; i < t; ++i)
303  {
304  sq.push_back(polyn_gf2m(t+1, g.get_sp_field()));
305  }
306  for (i = 0; i < d / 2; ++i)
307  {
308  sq[i].set_degree( 2 * i);
309  (*&sq[i]).set_coef( 2 * i, 1);
310  }
311 
312  for (; i < d; ++i)
313  {
314  clear_mem(&sq[i].coeff[0], 2);
315  copy_mem(&sq[i].coeff[0] + 2, &sq[i - 1].coeff[0], d);
316  sq[i].set_degree( sq[i - 1].get_degree() + 2);
317  polyn_gf2m::remainder(sq[i], g);
318  }
319  return sq;
320  }
int get_degree() const
Definition: polyn_gf2m.cpp:230
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:86
void set_coef(uint32_t i, gf2m v)
Definition: polyn_gf2m.h:85
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:97
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ sqrt_mod_init()

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

Definition at line 677 of file polyn_gf2m.cpp.

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

Referenced by add_to_coef(), and Botan::generate_mceliece_key().

678  {
679  uint32_t i, t;
680  uint32_t nb_polyn_sqrt_mat;
681  std::shared_ptr<GF2m_Field> msp_field = g.msp_field;
682  std::vector<polyn_gf2m> result;
683  t = g.get_degree();
684  nb_polyn_sqrt_mat = t/2;
685 
686  std::vector<polyn_gf2m> sq_aux = polyn_gf2m::sqmod_init(g);
687 
688 
689  polyn_gf2m p( t - 1, g.get_sp_field());
690  p.set_degree( 1);
691 
692  (*&p).set_coef( 1, 1);
693  // q(z) = 0, p(z) = z
694  for (i = 0; i < t * msp_field->get_extension_degree() - 1; ++i)
695  {
696  // q(z) <- p(z)^2 mod g(z)
697  polyn_gf2m q = p.sqmod(sq_aux, t);
698  // q(z) <-> p(z)
699  polyn_gf2m aux = q;
700  q = p;
701  p = aux;
702  }
703  // p(z) = z^(2^(tm-1)) mod g(z) = sqrt(z) mod g(z)
704 
705  for (i = 0; i < nb_polyn_sqrt_mat; ++i)
706  {
707  result.push_back(polyn_gf2m(t - 1, g.get_sp_field()));
708  }
709 
710  result[0] = p;
711  result[0].get_degree();
712  for(i = 1; i < nb_polyn_sqrt_mat; i++)
713  {
714  result[i] = result[i - 1];
715  result[i].poly_shiftmod(g),
716  result[i].get_degree();
717  }
718 
719  return result;
720  }
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:155
void set_coef(uint32_t i, gf2m v)
Definition: polyn_gf2m.h:85
static std::vector< polyn_gf2m > sqmod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:291

◆ swap()

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

Definition at line 791 of file polyn_gf2m.cpp.

References coeff, m_deg, and msp_field.

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

792  {
793  std::swap(this->m_deg, other.m_deg);
794  std::swap(this->msp_field, other.msp_field);
795  std::swap(this->coeff, other.coeff);
796  }
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:155
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:152

◆ 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().

Referenced by add_to_coef().

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:230
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:108
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

◆ msp_field

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

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