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_Field >	get_sp_field () const
bool	operator!= (const polyn_gf2m &other) const
polyn_gf2m &	operator= (const polyn_gf2m &)=default
polyn_gf2m &	operator= (polyn_gf2m &&other)
bool	operator== (const polyn_gf2m &other) const
gf2m &	operator[] (size_t i)
gf2m	operator[] (size_t i) const
void	patchup_deg_secure (uint32_t trgt_deg, gf2m patch_elem)
	polyn_gf2m ()
	polyn_gf2m (const secure_vector< uint8_t > &encoded, const std::shared_ptr< GF2m_Field > &sp_field)
	polyn_gf2m (const std::shared_ptr< GF2m_Field > &sp_field)
	polyn_gf2m (const uint8_t *mem, uint32_t mem_len, const std::shared_ptr< GF2m_Field > &sp_field)
	polyn_gf2m (int d, const std::shared_ptr< GF2m_Field > &sp_field)
	polyn_gf2m (int degree, const uint8_t *mem, size_t mem_byte_len, const std::shared_ptr< GF2m_Field > &sp_field)
	polyn_gf2m (polyn_gf2m &&other)
	polyn_gf2m (polyn_gf2m const &other)
	polyn_gf2m (size_t t, RandomNumberGenerator &rng, const std::shared_ptr< GF2m_Field > &sp_field)
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_gf2m >	eea_with_coefficients (const polyn_gf2m &p, const polyn_gf2m &g, int break_deg)
static std::vector< polyn_gf2m >	sqmod_init (const polyn_gf2m &g)
static std::vector< polyn_gf2m >	sqrt_mod_init (const polyn_gf2m &g)

Public Attributes
secure_vector< gf2m >	coeff
int	m_deg
std::shared_ptr< GF2m_Field >	m_sp_field

Detailed Description

Definition at line 27 of file polyn_gf2m.h.

Constructor & Destructor Documentation

polyn_gf2m() [1/9]

Botan::polyn_gf2m::polyn_gf2m ( const std::shared_ptr< GF2m_Field > &  sp_field )

explicit

create a zero polynomial:

Definition at line 153 of file polyn_gf2m.cpp.

                                                                :
   m_deg(-1), coeff(1), m_sp_field(sp_field)
   {}

polyn_gf2m() [2/9]

Botan::polyn_gf2m::polyn_gf2m ( )

inline

Definition at line 35 of file polyn_gf2m.h.

: 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,
		const std::shared_ptr< GF2m_Field > &	sp_field
	)

Definition at line 754 of file polyn_gf2m.cpp.

                                                                  :
   m_sp_field(sp_field)
   {
   if(encoded.size() % 2)
      {
      throw Decoding_Error("encoded polynomial has odd length");
      }
   for(uint32_t i = 0; i < encoded.size(); i += 2)
      {
      gf2m el = (encoded[i] << 8) | encoded[i + 1];
      coeff.push_back(el);
      }
   get_degree();
 
   }

References coeff, and get_degree().

polyn_gf2m() [4/9]

Botan::polyn_gf2m::polyn_gf2m	(	int	d,
		const 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.

   :m_deg(-1),
    coeff(d+1),
    m_sp_field(sp_field)
   {
   }

polyn_gf2m() [5/9]

Botan::polyn_gf2m::polyn_gf2m

(

polyn_gf2m const &

other

)

Definition at line 91 of file polyn_gf2m.cpp.

   :m_deg(other.m_deg),
    coeff(other.coeff),
    m_sp_field(other.m_sp_field)
   { }

polyn_gf2m() [6/9]

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

random irreducible polynomial of degree t

Definition at line 639 of file polyn_gf2m.cpp.

   :m_deg(static_cast<int>(t)),
    coeff(t+1),
    m_sp_field(sp_field)
   {
   this->set_coef(t, 1);
   for(;;)
      {
      for(size_t i = 0; i < t; ++i)
         {
         this->set_coef(i, random_code_element(sp_field->get_cardinality(), rng));
         }
 
      const size_t degree = polyn_gf2m::degppf(*this);
 
      if(degree >= t)
         break;
      }
   }

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

polyn_gf2m() [7/9]

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

decode a polynomial from memory:

Definition at line 126 of file polyn_gf2m.cpp.

                                                                                                      :
   m_deg(-1), m_sp_field(sp_field)
   {
   if(mem_len % sizeof(gf2m))
      {
      throw Decoding_Error("illegal length of memory to decode ");
      }
 
   uint32_t size = (mem_len / sizeof(this->coeff[0])) ;
   this->coeff = secure_vector<gf2m>(size);
   this->m_deg = -1;
   for(uint32_t i = 0; i < size; i++)
      {
      this->coeff[i] = decode_gf2m(mem);
      mem += sizeof(this->coeff[0]);
      }
   for(uint32_t i = 0; i < size; i++)
      {
      if(this->coeff[i] >= (1 << sp_field->get_extension_degree()))
         {
         throw Decoding_Error("error decoding polynomial");
         }
      }
   this->get_degree();
   }

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

polyn_gf2m() [8/9]

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

create a polynomial from memory area (encoded)

Definition at line 157 of file polyn_gf2m.cpp.

   :m_sp_field(sp_field)
   {
   uint32_t j, k, l;
   gf2m a;
   uint32_t polyn_size;
   polyn_size = degree + 1;
   if(polyn_size * sp_field->get_extension_degree() > 8 * mem_byte_len)
      {
      throw Decoding_Error("memory vector for polynomial has wrong size");
      }
   this->coeff = secure_vector<gf2m>(degree+1);
   gf2m ext_deg = static_cast<gf2m>(this->m_sp_field->get_extension_degree());
   for (l = 0; l < polyn_size; l++)
      {
      k = (l * ext_deg) / 8;
 
      j = (l * ext_deg) % 8;
      a = mem[k] >> j;
      if (j + ext_deg > 8)
         {
         a ^= mem[k + 1] << (8- j);
         }
      if(j + ext_deg > 16)
         {
         a ^= mem[k + 2] << (16- j);
         }
      a &= ((1 << ext_deg) - 1);
      (*this).set_coef( l, a);
      }
 
   this->get_degree();
   }

References coeff, get_degree(), and m_sp_field.

polyn_gf2m() [9/9]

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

inline

Definition at line 68 of file polyn_gf2m.h.

         {
         this->swap(other);
         }

References swap().

Member Function Documentation

add_to_coef()

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

inline

Definition at line 102 of file polyn_gf2m.h.

         {
         coeff[i] ^= v;
         }

References coeff, and v.

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.

   {
   int i = static_cast<int>(this->coeff.size()) - 1;
   int result = 0;
   uint32_t found_mask = 0;
   uint32_t tracker_mask = 0xffff;
   for( ; i >= 0; i--)
      {
      found_mask = expand_mask_16bit(this->coeff[i]);
      result |= i & found_mask & tracker_mask;
      // tracker mask shall become zero once found mask is set
      // it shall remain zero from then on
      tracker_mask = tracker_mask & ~found_mask;
      }
   const_cast<polyn_gf2m*>(this)->m_deg = result;
   return result;
   }

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

Referenced by eea_with_coefficients(), and patchup_deg_secure().

degppf()

size_t Botan::polyn_gf2m::degppf

(

const polyn_gf2m &

g

)

Definition at line 390 of file polyn_gf2m.cpp.

   {
   polyn_gf2m s(g.get_sp_field());
 
   const size_t ext_deg = g.m_sp_field->get_extension_degree();
   const int d = g.get_degree();
   std::vector<polyn_gf2m> u = polyn_gf2m::sqmod_init(g);
 
   polyn_gf2m p(d - 1, g.m_sp_field);
 
   p.set_degree(1);
   (*&p).set_coef(1, 1);
   size_t result = static_cast<size_t>(d);
   for(size_t i = 1; i <= (d / 2) * ext_deg; ++i)
      {
      polyn_gf2m r = p.sqmod(u, d);
      if ((i % ext_deg) == 0)
         {
         r[1] ^= 1;
         r.get_degree(); // The degree may change
         s = polyn_gf2m::gcd( g, r);
 
         if(s.get_degree() > 0)
            {
            result = i / ext_deg;
            break;
            }
         r[1] ^= 1;
         r.get_degree(); // The degree may change
         }
      // No need for the exchange s
      s = p;
      p = r;
      r = s;
      }
 
   return result;
   }

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

Referenced by polyn_gf2m().

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.

   {
 
   std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field;
   int i, j, dr, du, delta;
   gf2m a;
   polyn_gf2m aux;
 
   // initialisation of the local variables
   // r0 <- g, r1 <- p, u0 <- 0, u1 <- 1
   dr = g.get_degree();
 
   BOTAN_ASSERT(dr > 3, "Valid polynomial");
 
   polyn_gf2m r0(dr, g.m_sp_field);
   polyn_gf2m r1(dr - 1, g.m_sp_field);
   polyn_gf2m u0(dr - 1, g.m_sp_field);
   polyn_gf2m u1(dr - 1, g.m_sp_field);
 
   r0 = g;
   r1 = p;
   u0.set_to_zero();
   u1.set_to_zero();
   (*&u1).set_coef( 0, 1);
   u1.set_degree( 0);
 
 
   // invariants:
   // r1 = u1 * p + v1 * g
   // r0 = u0 * p + v0 * g
   // and m_deg(u1) = m_deg(g) - m_deg(r0)
   // It stops when m_deg (r1) <t (m_deg (r0)> = t)
   // And therefore m_deg (u1) = m_deg (g) - m_deg (r0) <m_deg (g) - break_deg
   du = 0;
   dr = r1.get_degree();
   delta = r0.get_degree() - dr;
 
 
   while (dr >= break_deg)
      {
 
      for (j = delta; j >= 0; --j)
         {
         a = m_sp_field->gf_div(r0[dr + j], r1[dr]);
         if (a != 0)
            {
            gf2m la = m_sp_field->gf_log(a);
            // u0(z) <- u0(z) + a * u1(z) * z^j
            for (i = 0; i <= du; ++i)
               {
               u0[i + j] ^= m_sp_field->gf_mul_zrz(la, u1[i]);
               }
            // r0(z) <- r0(z) + a * r1(z) * z^j
            for (i = 0; i <= dr; ++i)
               {
               r0[i + j] ^= m_sp_field->gf_mul_zrz(la, r1[i]);
               }
            }
         } // end loop over j
 
      if(break_deg != 1) /* key eq. solving */
         {
         /* [ssms_icisc09] Countermeasure
         * d_break from paper equals break_deg - 1
         * */
 
         volatile gf2m fake_elem = 0x01;
         volatile gf2m cond1, cond2;
         int trgt_deg = r1.get_degree() - 1;
         r0.calc_degree_secure();
         u0.calc_degree_secure();
         if(!(g.get_degree() % 2))
            {
            /* t even */
            cond1 = r0.get_degree() < break_deg - 1;
            }
         else
            {
            /* t odd */
            cond1 =  r0.get_degree() < break_deg;
            cond2 =  u0.get_degree() < break_deg - 1;
            cond1 = cond1 & cond2;
            }
         /* expand cond1 to a full mask */
         gf2m mask = generate_gf2m_mask(cond1);
         fake_elem = fake_elem & mask;
         r0.patchup_deg_secure(trgt_deg, fake_elem);
         }
      if(break_deg == 1) /* syndrome inversion */
         {
         volatile gf2m fake_elem = 0x00;
         volatile uint32_t trgt_deg = 0;
         r0.calc_degree_secure();
         u0.calc_degree_secure();
         /**
         * 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.
         *
         */
         if(u0.get_degree() == 4)
            {
            uint32_t mask = 0;
            /**
            * Condition that the EEA would break now
            */
            int cond_r = r0.get_degree() == 0;
            /**
            * 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).
            */
            // Condition for the coefficient to Y to be cancelled out by the
            // addition of Y before the square root computation:
            int cond_u1 = m_sp_field->gf_mul(u0.coeff[1], m_sp_field->gf_inv(r0.coeff[0])) == 1;
 
            // Condition sigma_3 = 0:
            int cond_u3 = u0.coeff[3] == 0;
            // combine the conditions:
            cond_r &= (cond_u1 & cond_u3);
            // mask generation:
            mask = expand_mask_16bit(cond_r);
            trgt_deg = 2 & mask;
            fake_elem = 1 & mask;
            }
         else if(u0.get_degree() == 6)
            {
            uint32_t mask = 0;
            int cond_r= r0.get_degree() == 0;
            int cond_u1 = m_sp_field->gf_mul(u0.coeff[1], m_sp_field->gf_inv(r0.coeff[0])) == 1;
            int cond_u3 = u0.coeff[3] == 0;
 
            int cond_u5 = u0.coeff[5] == 0;
 
            cond_r &= (cond_u1 & cond_u3 & cond_u5);
            mask = expand_mask_16bit(cond_r);
            trgt_deg = 4 & mask;
            fake_elem = 1 & mask;
            }
         else if(u0.get_degree() == 8)
            {
            uint32_t mask = 0;
            int cond_r= r0.get_degree() == 0;
            int cond_u1 = m_sp_field->gf_mul(u0[1], m_sp_field->gf_inv(r0[0])) == 1;
            int cond_u3 = u0.coeff[3] == 0;
 
            int cond_u5 = u0.coeff[5] == 0;
 
            int cond_u7 = u0.coeff[7] == 0;
 
            cond_r &= (cond_u1 & cond_u3 & cond_u5 & cond_u7);
            mask = expand_mask_16bit(cond_r);
            trgt_deg = 6 & mask;
            fake_elem = 1 & mask;
            }
         r0.patchup_deg_secure(trgt_deg, fake_elem);
         }
      // exchange
      aux = r0; r0 = r1; r1 = aux;
      aux = u0; u0 = u1; u1 = aux;
 
      du = du + delta;
      delta = 1;
      while (r1[dr - delta] == 0)
         {
         delta++;
         }
 
 
      dr -= delta;
      } /* end  while loop (dr >= break_deg) */
 
 
   u1.set_degree( du);
   r1.set_degree( dr);
   //return u1 and r1;
   return std::make_pair(u1,r1); // coefficients u,v
   }

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

encode() [1/2]

secure_vector< uint8_t > Botan::polyn_gf2m::encode

(

)

const

Definition at line 770 of file polyn_gf2m.cpp.

   {
   secure_vector<uint8_t> result;
 
   if(m_deg < 1)
      {
      result.push_back(0);
      result.push_back(0);
      return result;
      }
 
   uint32_t len = m_deg+1;
   for(unsigned i = 0; i < len; i++)
      {
      // "big endian" encoding of the GF(2^m) elements
      result.push_back(get_byte<0>(coeff[i]));
      result.push_back(get_byte<1>(coeff[i]));
      }
   return result;
   }

References coeff, 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.

   {
   return eval_aux(&this->coeff[0], a, this->m_deg, this->m_sp_field);
   }

References m_deg, and m_sp_field.

get_coef()

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

inline

Definition at line 95 of file polyn_gf2m.h.

{ return coeff[i]; }

References coeff.

get_degree()

int Botan::polyn_gf2m::get_degree

(

)

const

Definition at line 228 of file polyn_gf2m.cpp.

   {
   int d = static_cast<int>(this->coeff.size()) - 1;
   while ((d >= 0) && (this->coeff[d] == 0))
      --d;
   const_cast<polyn_gf2m*>(this)->m_deg = d;
   return d;
   }

References coeff, and m_deg.

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

get_lead_coef()

gf2m Botan::polyn_gf2m::get_lead_coef ( ) const

inline

Definition at line 93 of file polyn_gf2m.h.

{ return coeff[m_deg]; }

References coeff, and m_deg.

get_sp_field()

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

inline

Definition at line 86 of file polyn_gf2m.h.

         { return m_sp_field; }

References m_sp_field.

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

operator!=()

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

inline

Definition at line 66 of file polyn_gf2m.h.

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

         {
         if(this != &other)
            {
            this->swap(other);
            }
         return *this;
         }

References swap().

operator==()

bool Botan::polyn_gf2m::operator==

(

const polyn_gf2m &

other

)

const

Definition at line 798 of file polyn_gf2m.cpp.

   {
   if(m_deg != other.m_deg || coeff != other.coeff)
      {
      return false;
      }
   return true;
   }

References coeff, and m_deg.

operator[]() [1/2]

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

inline

Definition at line 89 of file polyn_gf2m.h.

{ return coeff[i]; }

References coeff.

operator[]() [2/2]

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

inline

Definition at line 91 of file polyn_gf2m.h.

{ return coeff[i]; }

References coeff.

patchup_deg_secure()

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

Definition at line 429 of file polyn_gf2m.cpp.

   {
   uint32_t i;
   if(this->coeff.size() < trgt_deg)
      {
      return;
      }
   for(i = 0; i < this->coeff.size(); i++)
      {
      uint32_t equal, equal_mask;
      this->coeff[i] |= patch_elem;
      equal = (i == trgt_deg);
      equal_mask = expand_mask_16bit(equal);
      patch_elem &= ~equal_mask;
      }
   this->calc_degree_secure();
   }

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

Referenced by eea_with_coefficients().

set_coef()

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

inline

Definition at line 97 of file polyn_gf2m.h.

         {
         coeff[i] = v;
         }

References coeff, and v.

Referenced by degppf(), eea_with_coefficients(), polyn_gf2m(), 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.

   {
   clear_mem(&this->coeff[0], this->coeff.size());
   this->m_deg = -1;
   }

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.

   {
   int i, j;
   gf2m la;
   std::shared_ptr<GF2m_Field> sp_field = this->m_sp_field;
 
   polyn_gf2m result(d - 1, sp_field);
   // terms of low degree
   for (i = 0; i < d / 2; ++i)
      {
      (*&result).set_coef( i * 2, sp_field->gf_square((*this)[i]));
      }
 
   // terms of high degree
   for (; i < d; ++i)
      {
      gf2m lpi = (*this)[i];
      if (lpi != 0)
         {
         lpi = sp_field->gf_log(lpi);
         la = sp_field->gf_mul_rrr(lpi, lpi);
         for (j = 0; j < d; ++j)
            {
            result[j] ^= sp_field->gf_mul_zrz(la, sq[i][j]);
            }
         }
      }
 
   // Update degre
   result.set_degree( d - 1);
   while ((result.get_degree() >= 0) && (result[result.get_degree()] == 0))
      result.set_degree( result.get_degree() - 1);
   return result;
   }

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

Referenced by degppf(), and sqrt_mod_init().

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.

   {
   std::vector<polyn_gf2m> sq;
   const int signed_deg = g.get_degree();
   if(signed_deg <= 0)
      throw Invalid_Argument("cannot compute sqmod for such low degree");
 
   const uint32_t d = static_cast<uint32_t>(signed_deg);
   uint32_t t = g.m_deg;
   // create t zero polynomials
   uint32_t i;
   for (i = 0; i < t; ++i)
      {
      sq.push_back(polyn_gf2m(t+1, g.get_sp_field()));
      }
   for (i = 0; i < d / 2; ++i)
      {
      sq[i].set_degree( 2 * i);
      (*&sq[i]).set_coef( 2 * i, 1);
      }
 
   for (; i < d; ++i)
      {
      clear_mem(&sq[i].coeff[0], 2);
      copy_mem(&sq[i].coeff[0] + 2, &sq[i - 1].coeff[0], d);
      sq[i].set_degree( sq[i - 1].get_degree() + 2);
      polyn_gf2m::remainder(sq[i], g);
      }
   return sq;
   }

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

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.

   {
   uint32_t i, t;
   uint32_t nb_polyn_sqrt_mat;
   std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field;
   std::vector<polyn_gf2m> result;
   t = g.get_degree();
   nb_polyn_sqrt_mat = t/2;
 
   std::vector<polyn_gf2m> sq_aux = polyn_gf2m::sqmod_init(g);
 
 
   polyn_gf2m p( t - 1, g.get_sp_field());
   p.set_degree( 1);
 
   (*&p).set_coef( 1, 1);
   // q(z) = 0, p(z) = z
   for (i = 0; i < t * m_sp_field->get_extension_degree() - 1; ++i)
      {
      // q(z) <- p(z)^2 mod g(z)
      polyn_gf2m q = p.sqmod(sq_aux, t);
      // q(z) <-> p(z)
      polyn_gf2m aux = q;
      q = p;
      p = aux;
      }
   // p(z) = z^(2^(tm-1)) mod g(z) = sqrt(z) mod g(z)
 
   for (i = 0; i < nb_polyn_sqrt_mat; ++i)
      {
      result.push_back(polyn_gf2m(t - 1, g.get_sp_field()));
      }
 
   result[0] = p;
   result[0].get_degree();
   for(i = 1; i < nb_polyn_sqrt_mat; i++)
      {
      result[i] = result[i - 1];
      result[i].poly_shiftmod(g);
      result[i].get_degree();
      }
 
   return result;
   }

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

Referenced by Botan::generate_mceliece_key().

swap()

void Botan::polyn_gf2m::swap

(

polyn_gf2m &

other

)

Definition at line 791 of file polyn_gf2m.cpp.

   {
   std::swap(this->m_deg, other.m_deg);
   std::swap(this->m_sp_field, other.m_sp_field);
   std::swap(this->coeff, other.coeff);
   }

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.

   {
   int d = get_degree();
   std::string result;
   for(int i = 0; i <= d; i ++)
      {
      result += std::to_string(this->coeff[i]);
      if(i != d)
         {
         result += ", ";
         }
      }
   return result;
   }

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

Member Data Documentation

coeff

secure_vector<gf2m> Botan::polyn_gf2m::coeff

Definition at line 156 of file polyn_gf2m.h.

Referenced by add_to_coef(), calc_degree_secure(), eea_with_coefficients(), encode(), get_coef(), get_degree(), get_lead_coef(), operator==(), operator[](), polyn_gf2m(), set_coef(), set_to_zero(), sqmod_init(), swap(), and to_string().

m_deg

int Botan::polyn_gf2m::m_deg

Definition at line 153 of file polyn_gf2m.h.

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

m_sp_field

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

Definition at line 159 of file polyn_gf2m.h.

Referenced by degppf(), eea_with_coefficients(), eval(), get_sp_field(), polyn_gf2m(), sqmod(), sqrt_mod_init(), swap(), and Botan::syndrome_init().

---

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

• src/lib/pubkey/mce/polyn_gf2m.h
• src/lib/pubkey/mce/polyn_gf2m.cpp