Botan  2.1.0
Crypto and TLS for C++11
Public Member Functions | Static Public Member Functions | Public Attributes | List of all members
Botan::polyn_gf2m Struct 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 24 of file polyn_gf2m.h.

Constructor & Destructor Documentation

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  {}
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156
Botan::polyn_gf2m::polyn_gf2m ( )
inline

Definition at line 32 of file polyn_gf2m.h.

Referenced by sqmod_init(), and sqrt_mod_init().

33  :m_deg(-1) {}
Botan::polyn_gf2m::polyn_gf2m ( const secure_vector< uint8_t > &  encoded,
std::shared_ptr< GF2m_Field sp_field 
)

Definition at line 756 of file polyn_gf2m.cpp.

References get_degree().

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

Definition at line 43 of file polyn_gf2m.h.

References swap().

44  {
45  this->swap(other);
46  }
void swap(polyn_gf2m &other)
Definition: polyn_gf2m.cpp:792
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  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156
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  { }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156
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 642 of file polyn_gf2m.cpp.

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

643  :m_deg(t),
644  coeff(t+1),
645  msp_field(sp_field)
646  {
647  (*this).set_coef( t, 1);
648  int degree = 0;
649  do
650  {
651  for (int i = 0; i < t; ++i)
652  {
653  (*this).set_coef( i, random_code_element(sp_field->get_cardinality(), rng));
654  }
655  polyn_gf2m::degppf(*this, &degree);
656  }
657  while (degree < t);
658  }
void degppf(const polyn_gf2m &g, int *p_result)
Definition: polyn_gf2m.cpp:392
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
gf2m random_code_element(unsigned code_length, RandomNumberGenerator &rng)
Definition: polyn_gf2m.cpp:71
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156
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 new 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  }
int get_degree() const
Definition: polyn_gf2m.cpp:230
gf2m decode_gf2m(const uint8_t *mem)
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
uint16_t gf2m
Definition: gf2m_small_m.h:20
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156
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, get_degree(), 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  }
int get_degree() const
Definition: polyn_gf2m.cpp:230
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
uint16_t gf2m
Definition: gf2m_small_m.h:20
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156

Member Function Documentation

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

Definition at line 91 of file polyn_gf2m.h.

References coeff.

92  {
93  coeff[i] = coeff[i] ^ v;
94  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
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 = 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  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
uint16_t expand_mask_16bit(T tst)
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 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:86
static std::vector< polyn_gf2m > sqmod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:291
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().

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  //CSEC_MASK__GEN_MASK_16B(cond1, mask);
535  gf2m mask = generate_gf2m_mask(cond1);
536  fake_elem &= mask;
537  r0.patchup_deg_secure(trgt_deg, fake_elem);
538  }
539  if(break_deg == 1) /* syndrome inversion */
540  {
541  volatile gf2m fake_elem = 0x00;
542  volatile uint32_t trgt_deg = 0;
543  r0.calc_degree_secure();
544  u0.calc_degree_secure();
545  /**
546  * countermeasure against the low weight attacks for w=4, w=6 and w=8.
547  * Higher values are not covered since for w=8 we already have a
548  * probability for a positive of 1/n^3 from random ciphertexts with the
549  * given weight. For w = 10 it would be 1/n^4 and so on. Thus attacks
550  * based on such high values of w are considered impractical.
551  *
552  * The outer test for the degree of u ( Omega in the paper ) needs not to
553  * be disguised. Each of the three is performed at most once per EEA
554  * (syndrome inversion) execution, the attacker knows this already when
555  * preparing the ciphertext with the given weight. Inside these three
556  * cases however, we must use timing neutral (branch free) operations to
557  * implement the condition detection and the counteractions.
558  *
559  */
560  if(u0.get_degree() == 4)
561  {
562  uint32_t mask = 0;
563  /**
564  * Condition that the EEA would break now
565  */
566  int cond_r = r0.get_degree() == 0;
567  /**
568  * Now come the conditions for all odd coefficients of this sigma
569  * candiate. If they are all fulfilled, then we know that we have a low
570  * weight error vector, since the key-equation solving EEA is skipped if
571  * the degree of tau^2 is low (=m_deg(u0)) and all its odd cofficients are
572  * zero (they would cause "full-length" contributions from the square
573  * root computation).
574  */
575  // Condition for the coefficient to Y to be cancelled out by the
576  // addition of Y before the square root computation:
577  int cond_u1 = msp_field->gf_mul(u0.coeff[1], msp_field->gf_inv(r0.coeff[0])) == 1;
578 
579  // Condition sigma_3 = 0:
580  int cond_u3 = u0.coeff[3] == 0;
581  // combine the conditions:
582  cond_r &= (cond_u1 & cond_u3);
583  // mask generation:
584  mask = expand_mask_16bit(cond_r);
585  trgt_deg = 2 & mask;
586  fake_elem = 1 & mask;
587  }
588  else if(u0.get_degree() == 6)
589  {
590  uint32_t mask = 0;
591  int cond_r= r0.get_degree() == 0;
592  int cond_u1 = msp_field->gf_mul(u0.coeff[1], msp_field->gf_inv(r0.coeff[0])) == 1;
593  int cond_u3 = u0.coeff[3] == 0;
594 
595  int cond_u5 = u0.coeff[5] == 0;
596 
597  cond_r &= (cond_u1 & cond_u3 & cond_u5);
598  mask = expand_mask_16bit(cond_r);
599  trgt_deg = 4 & mask;
600  fake_elem = 1 & mask;
601  }
602  else if(u0.get_degree() == 8)
603  {
604  uint32_t mask = 0;
605  int cond_r= r0.get_degree() == 0;
606  int cond_u1 = msp_field->gf_mul(u0[1], msp_field->gf_inv(r0[0])) == 1;
607  int cond_u3 = u0.coeff[3] == 0;
608 
609  int cond_u5 = u0.coeff[5] == 0;
610 
611  int cond_u7 = u0.coeff[7] == 0;
612 
613  cond_r &= (cond_u1 & cond_u3 & cond_u5 & cond_u7);
614  mask = expand_mask_16bit(cond_r);
615  trgt_deg = 6 & mask;
616  fake_elem = 1 & mask;
617  }
618  r0.patchup_deg_secure(trgt_deg, fake_elem);
619  }
620  // exchange
621  aux = r0; r0 = r1; r1 = aux;
622  aux = u0; u0 = u1; u1 = aux;
623 
624  du = du + delta;
625  delta = 1;
626  while (r1[dr - delta] == 0)
627  {
628  delta++;
629  }
630 
631 
632  dr -= delta;
633  } /* end while loop (dr >= break_deg) */
634 
635 
636  u1.set_degree( du);
637  r1.set_degree( dr);
638  //return u1 and r1;
639  return std::make_pair(u1,r1); // coefficients u,v
640  }
void set_coef(uint32_t i, gf2m v)
Definition: polyn_gf2m.h:86
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:27
uint16_t expand_mask_16bit(T tst)
uint16_t gf2m
Definition: gf2m_small_m.h:20
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156
secure_vector< uint8_t > Botan::polyn_gf2m::encode ( ) const

Definition at line 771 of file polyn_gf2m.cpp.

References m_deg.

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

772  {
773  secure_vector<uint8_t> result;
774 
775  if(m_deg < 1)
776  {
777  result.push_back(0);
778  result.push_back(0);
779  return result;
780  }
781 
782  uint32_t len = m_deg+1;
783  for(unsigned i = 0; i < len; i++)
784  {
785  // "big endian" encoding of the GF(2^m) elements
786  result.push_back(coeff[i] >> 8);
787  result.push_back(coeff[i]);
788  }
789  return result;
790  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
void Botan::polyn_gf2m::encode ( uint32_t  min_numo_coeffs,
uint8_t *  mem,
uint32_t  mem_len 
) const
gf2m Botan::polyn_gf2m::eval ( gf2m  a)

Definition at line 256 of file polyn_gf2m.cpp.

References m_deg, and msp_field.

257  {
258  return eval_aux(&this->coeff[0], a, this->m_deg, this->msp_field);
259  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156
gf2m Botan::polyn_gf2m::get_coef ( uint32_t  i) const
inline

Definition at line 84 of file polyn_gf2m.h.

References coeff.

84 { return coeff[i]; }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
int Botan::polyn_gf2m::get_degree ( ) const

Definition at line 230 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().

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:153
gf2m Botan::polyn_gf2m::get_lead_coef ( ) const
inline

Definition at line 82 of file polyn_gf2m.h.

References coeff, and m_deg.

82 { return coeff[m_deg]; }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
std::shared_ptr<GF2m_Field> Botan::polyn_gf2m::get_sp_field ( ) const
inline

Definition at line 75 of file polyn_gf2m.h.

References msp_field.

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

76  { return msp_field; }
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156
bool Botan::polyn_gf2m::operator!= ( const polyn_gf2m other) const
inline

Definition at line 41 of file polyn_gf2m.h.

41 { return !(*this == other); }
polyn_gf2m& Botan::polyn_gf2m::operator= ( const polyn_gf2m )
default
polyn_gf2m& Botan::polyn_gf2m::operator= ( polyn_gf2m &&  other)
inline

Definition at line 48 of file polyn_gf2m.h.

References swap().

49  {
50  if(this != &other)
51  {
52  this->swap(other);
53  }
54  return *this;
55  }
void swap(polyn_gf2m &other)
Definition: polyn_gf2m.cpp:792
bool Botan::polyn_gf2m::operator== ( const polyn_gf2m other) const

Definition at line 799 of file polyn_gf2m.cpp.

References coeff, and m_deg.

800  {
801  if(m_deg != other.m_deg || coeff != other.coeff)
802  {
803  return false;
804  }
805  return true;
806  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
gf2m& Botan::polyn_gf2m::operator[] ( size_t  i)
inline

Definition at line 78 of file polyn_gf2m.h.

References coeff.

78 { return coeff[i]; }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
gf2m Botan::polyn_gf2m::operator[] ( size_t  i) const
inline

Definition at line 80 of file polyn_gf2m.h.

References coeff.

80 { return coeff[i]; }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
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 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
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
uint16_t expand_mask_16bit(T tst)
void Botan::polyn_gf2m::set_coef ( uint32_t  i,
gf2m  v 
)
inline

Definition at line 86 of file polyn_gf2m.h.

References coeff.

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

87  {
88  coeff[i] = v;
89  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
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 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:57
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
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, and set_coef().

Referenced by 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  }
void set_coef(uint32_t i, gf2m v)
Definition: polyn_gf2m.h:86
uint16_t gf2m
Definition: gf2m_small_m.h:20
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156
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 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 set_coef(uint32_t i, gf2m v)
Definition: polyn_gf2m.h:86
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:57
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:68
std::vector< polyn_gf2m > Botan::polyn_gf2m::sqrt_mod_init ( const polyn_gf2m g)
static

Definition at line 678 of file polyn_gf2m.cpp.

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

Referenced by Botan::generate_mceliece_key().

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

Definition at line 792 of file polyn_gf2m.cpp.

References coeff, m_deg, and msp_field.

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

793  {
794  std::swap(this->m_deg, other.m_deg);
795  std::swap(this->msp_field, other.msp_field);
796  std::swap(this->coeff, other.coeff);
797  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
std::shared_ptr< GF2m_Field > msp_field
Definition: polyn_gf2m.h:156
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:230
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:47
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153

Member Data Documentation

secure_vector<gf2m> Botan::polyn_gf2m::coeff
int Botan::polyn_gf2m::m_deg
std::shared_ptr<GF2m_Field> Botan::polyn_gf2m::msp_field

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