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, volatile gf2m patch_elem)
	polyn_gf2m (std::shared_ptr< GF2m_Field > sp_field)
	polyn_gf2m ()
	polyn_gf2m (const secure_vector< uint8_t > &encoded, std::shared_ptr< GF2m_Field > sp_field)
	polyn_gf2m (int d, std::shared_ptr< GF2m_Field > sp_field)
	polyn_gf2m (polyn_gf2m const &other)
	polyn_gf2m (size_t t, RandomNumberGenerator &rng, std::shared_ptr< GF2m_Field > sp_field)
	polyn_gf2m (const uint8_t *mem, uint32_t mem_len, std::shared_ptr< GF2m_Field > sp_field)
	polyn_gf2m (int degree, const uint8_t *mem, size_t mem_byte_len, std::shared_ptr< GF2m_Field > sp_field)
	polyn_gf2m (polyn_gf2m &&other)
void	set_coef (size_t i, gf2m v)
void	set_to_zero ()
polyn_gf2m	sqmod (const std::vector< polyn_gf2m > &sq, int d)
void	swap (polyn_gf2m &other)
std::string	to_string () const

Static Public Member Functions
static std::pair< polyn_gf2m, polyn_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 26 of file polyn_gf2m.h.

Constructor & Destructor Documentation

polyn_gf2m() [1/9]

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

explicit

create a zero polynomial:

Definition at line 153 of file polyn_gf2m.cpp.

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

polyn_gf2m() [2/9]

Botan::polyn_gf2m::polyn_gf2m ( )

inline

Definition at line 34 of file polyn_gf2m.h.

Referenced by sqmod_init(), and sqrt_mod_init().

: m_deg(-1) {}

polyn_gf2m() [3/9]

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

Definition at line 754 of file polyn_gf2m.cpp.

References coeff, and get_degree().

   :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();

   }

polyn_gf2m() [4/9]

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

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

Definition at line 97 of file polyn_gf2m.cpp.

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

random irreducible polynomial of degree t

Definition at line 639 of file polyn_gf2m.cpp.

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

   :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;
      }
   }

polyn_gf2m() [7/9]

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

decode a polynomial from memory:

Definition at line 126 of file polyn_gf2m.cpp.

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

                                                                                               :
   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();
   }

polyn_gf2m() [8/9]

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

create a polynomial from memory area (encoded)

Definition at line 157 of file polyn_gf2m.cpp.

References coeff, get_degree(), and m_sp_field.

   :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();
   }

polyn_gf2m() [9/9]

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

inline

Definition at line 64 of file polyn_gf2m.h.

References swap().

         {
         this->swap(other);
         }

Member Function Documentation

add_to_coef()

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

inline

Definition at line 98 of file polyn_gf2m.h.

References coeff.

         {
         coeff[i] ^= 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.

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

Referenced by eea_with_coefficients(), and patchup_deg_secure().

   {
   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;
   }

degppf()

size_t Botan::polyn_gf2m::degppf

(

const polyn_gf2m &

g

)

Definition at line 390 of file polyn_gf2m.cpp.

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

Referenced by polyn_gf2m().

   {
   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;
   }

eea_with_coefficients()

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

static

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

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

Condition that the EEA would break now

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

Definition at line 448 of file polyn_gf2m.cpp.

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

   {

   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 &= cond2;
            }
         /* expand cond1 to a full mask */
         gf2m mask = generate_gf2m_mask(cond1);
         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
   }

encode() [1/2]

secure_vector< uint8_t > Botan::polyn_gf2m::encode

(

)

const

Definition at line 769 of file polyn_gf2m.cpp.

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

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

   {
   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;
   }

encode() [2/2]

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

eval()

gf2m Botan::polyn_gf2m::eval

(

gf2m

a

)

Definition at line 254 of file polyn_gf2m.cpp.

References m_deg, and m_sp_field.

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

get_coef()

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

inline

Definition at line 91 of file polyn_gf2m.h.

References coeff.

{ return coeff[i]; }

get_degree()

int Botan::polyn_gf2m::get_degree

(

)

const

Definition at line 228 of file polyn_gf2m.cpp.

References coeff, and m_deg.

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

   {
   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;
   }

get_lead_coef()

gf2m Botan::polyn_gf2m::get_lead_coef ( ) const

inline

Definition at line 89 of file polyn_gf2m.h.

References coeff, and m_deg.

{ return coeff[m_deg]; }

get_sp_field()

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

inline

Definition at line 82 of file polyn_gf2m.h.

References m_sp_field.

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

         { return m_sp_field; }

operator!=()

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

inline

Definition at line 62 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 69 of file polyn_gf2m.h.

References swap().

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

operator==()

bool Botan::polyn_gf2m::operator==

(

const polyn_gf2m &

other

)

const

Definition at line 797 of file polyn_gf2m.cpp.

References coeff, and m_deg.

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

operator[]() [1/2]

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

inline

Definition at line 85 of file polyn_gf2m.h.

References coeff.

{ return coeff[i]; }

operator[]() [2/2]

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

inline

Definition at line 87 of file polyn_gf2m.h.

References coeff.

{ return coeff[i]; }

patchup_deg_secure()

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

Definition at line 429 of file polyn_gf2m.cpp.

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

Referenced by eea_with_coefficients().

   {
   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();
   }

set_coef()

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

inline

Definition at line 93 of file polyn_gf2m.h.

References coeff.

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

         {
         coeff[i] = v;
         }

set_to_zero()

void Botan::polyn_gf2m::set_to_zero

(

)

Definition at line 222 of file polyn_gf2m.cpp.

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

Referenced by eea_with_coefficients().

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

sqmod()

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

Definition at line 323 of file polyn_gf2m.cpp.

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

Referenced by degppf(), and sqrt_mod_init().

   {
   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;
   }

sqmod_init()

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

static

Definition at line 289 of file polyn_gf2m.cpp.

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

Referenced by degppf(), and sqrt_mod_init().

   {
   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;
   }

sqrt_mod_init()

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

static

Definition at line 676 of file polyn_gf2m.cpp.

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

Referenced by Botan::generate_mceliece_key().

   {
   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;
   }

swap()

void Botan::polyn_gf2m::swap

(

polyn_gf2m &

other

)

Definition at line 790 of file polyn_gf2m.cpp.

References coeff, m_deg, and m_sp_field.

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

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

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

   {
   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;
   }

Member Data Documentation

coeff

secure_vector<gf2m> Botan::polyn_gf2m::coeff

Definition at line 152 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 149 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 155 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