Botan  2.11.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_Field > get_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_Field > m_sp_field
 

Detailed Description

Definition at line 24 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:153
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:156

◆ polyn_gf2m() [2/9]

Botan::polyn_gf2m::polyn_gf2m ( )
inline

Definition at line 32 of file polyn_gf2m.h.

33  :m_deg(-1) {}

Referenced by sqmod_init(), and sqrt_mod_init().

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

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

References coeff, and get_degree().

◆ polyn_gf2m() [4/9]

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

Definition at line 43 of file polyn_gf2m.h.

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

References swap().

◆ 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  m_sp_field(sp_field)
101  {
102  }
BigInt const BigInt & d
Definition: bigint.h:1093
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:156

◆ 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  m_sp_field(other.m_sp_field)
95  { }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:156

◆ polyn_gf2m() [7/9]

Botan::polyn_gf2m::polyn_gf2m ( int  t,
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

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

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

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

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

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  }
int get_degree() const
Definition: polyn_gf2m.cpp:228
size_t const BigInt & a
Definition: numthry.h:111
uint16_t gf2m
Definition: gf2m_small_m.h:20
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:156

References Botan::a, coeff, get_degree(), and m_sp_field.

Member Function Documentation

◆ add_to_coef()

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

Definition at line 91 of file polyn_gf2m.h.

92  {
93  coeff[i] = coeff[i] ^ v;
94  }
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153

References coeff.

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

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:153

References coeff, and Botan::expand_mask_16bit().

Referenced by eea_with_coefficients(), and patchup_deg_secure().

◆ degppf()

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

Definition at line 390 of file polyn_gf2m.cpp.

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  }
BigInt const BigInt & p
Definition: numthry.h:150
void set_coef(uint32_t i, gf2m v)
Definition: polyn_gf2m.h:86
void const BigInt BigInt BigInt & r
Definition: divide.h:23
BigInt const BigInt & d
Definition: bigint.h:1093
static std::vector< polyn_gf2m > sqmod_init(const polyn_gf2m &g)
Definition: polyn_gf2m.cpp:289
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

References Botan::d, Botan::g, Botan::p, Botan::r, set_coef(), and sqmod_init().

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

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  }
BigInt const BigInt & p
Definition: numthry.h:150
void set_coef(uint32_t i, gf2m v)
Definition: polyn_gf2m.h:86
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
size_t const BigInt & a
Definition: numthry.h:111
uint16_t expand_mask_16bit(T tst)
uint16_t gf2m
Definition: gf2m_small_m.h:20
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::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:156

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

◆ encode() [1/2]

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

Definition at line 768 of file polyn_gf2m.cpp.

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  }
std::string size_t len
Definition: pk_keys.h:305
constexpr uint8_t get_byte(size_t byte_num, T input)
Definition: loadstor.h:39
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153

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

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

255  {
256  return eval_aux(&this->coeff[0], a, this->m_deg, this->m_sp_field);
257  }
size_t const BigInt & a
Definition: numthry.h:111
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:156

References Botan::a, m_deg, and m_sp_field.

◆ get_coef()

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

Definition at line 84 of file polyn_gf2m.h.

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

References coeff.

◆ get_degree()

int Botan::polyn_gf2m::get_degree ( ) const

Definition at line 228 of file polyn_gf2m.cpp.

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  }
BigInt const BigInt & d
Definition: bigint.h:1093
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153

References coeff, and Botan::d.

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

◆ get_lead_coef()

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

Definition at line 82 of file polyn_gf2m.h.

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

References coeff, and m_deg.

◆ get_sp_field()

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

Definition at line 75 of file polyn_gf2m.h.

76  { return m_sp_field; }
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:156

References m_sp_field.

◆ operator!=()

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

Definition at line 41 of file polyn_gf2m.h.

41 { 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 48 of file polyn_gf2m.h.

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

References swap().

◆ operator==()

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

Definition at line 796 of file polyn_gf2m.cpp.

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

References coeff, and m_deg.

◆ operator[]() [1/2]

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

Definition at line 78 of file polyn_gf2m.h.

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

References coeff.

◆ operator[]() [2/2]

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

Definition at line 80 of file polyn_gf2m.h.

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

References coeff.

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

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:153

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

Referenced by eea_with_coefficients().

◆ set_coef()

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

Definition at line 86 of file polyn_gf2m.h.

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

References coeff.

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

◆ set_to_zero()

void Botan::polyn_gf2m::set_to_zero ( )

Definition at line 222 of file polyn_gf2m.cpp.

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

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

Referenced by eea_with_coefficients().

◆ sqmod()

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

Definition at line 323 of file polyn_gf2m.cpp.

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  }
void set_coef(uint32_t i, gf2m v)
Definition: polyn_gf2m.h:86
BigInt const BigInt & d
Definition: bigint.h:1093
uint16_t gf2m
Definition: gf2m_small_m.h:20
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:156

References Botan::d, get_degree(), m_sp_field, and set_coef().

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

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:111
void set_coef(uint32_t i, gf2m v)
Definition: polyn_gf2m.h:86
BigInt const BigInt & d
Definition: bigint.h:1093
void copy_mem(T *out, const T *in, size_t n)
Definition: mem_ops.h:122
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153
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
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

References Botan::clear_mem(), coeff, Botan::copy_mem(), Botan::d, Botan::g, get_degree(), polyn_gf2m(), set_coef(), and Botan::t.

Referenced by degppf(), and sqrt_mod_init().

◆ sqrt_mod_init()

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

Definition at line 675 of file polyn_gf2m.cpp.

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  }
BigInt const BigInt & p
Definition: numthry.h:150
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:289
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
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
std::shared_ptr< GF2m_Field > m_sp_field
Definition: polyn_gf2m.h:156

References Botan::g, m_sp_field, Botan::p, polyn_gf2m(), Botan::q, set_coef(), sqmod_init(), and Botan::t.

Referenced by Botan::generate_mceliece_key().

◆ swap()

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

Definition at line 789 of file polyn_gf2m.cpp.

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

References coeff, m_deg, and m_sp_field.

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

◆ to_string()

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

Definition at line 104 of file polyn_gf2m.cpp.

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
BigInt const BigInt & d
Definition: bigint.h:1093
secure_vector< gf2m > coeff
Definition: polyn_gf2m.h:153

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

Member Data Documentation

◆ coeff

secure_vector<gf2m> Botan::polyn_gf2m::coeff

◆ m_deg

int Botan::polyn_gf2m::m_deg

Definition at line 150 of file polyn_gf2m.h.

Referenced by encode(), eval(), get_lead_coef(), operator==(), polyn_gf2m(), set_to_zero(), and swap().

◆ 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: