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_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 (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_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 >	msp_field

Detailed Description

Definition at line 23 of file polyn_gf2m.h.

Constructor & Destructor Documentation

polyn_gf2m() [1/9]

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

explicit

create a zero polynomial:

Definition at line 153 of file polyn_gf2m.cpp.

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

polyn_gf2m() [2/9]

Botan::polyn_gf2m::polyn_gf2m ( )

inline

Definition at line 31 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 755 of file polyn_gf2m.cpp.

References coeff, and get_degree().

   :msp_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 ( polyn_gf2m &&  other )

inline

Definition at line 42 of file polyn_gf2m.h.

References swap().

         {
         this->swap(other);
         }

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.

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

polyn_gf2m() [6/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),
    msp_field(other.msp_field)
   { }

polyn_gf2m() [7/9]

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

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

Definition at line 641 of file polyn_gf2m.cpp.

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

   :m_deg(t),
    coeff(t+1),
    msp_field(sp_field)
   {
   (*this).set_coef( t, 1);
   int degree = 0;
   do
      {
      for (int i = 0; i < t; ++i)
         {
         (*this).set_coef( i, random_code_element(sp_field->get_cardinality(), rng));
         }
      polyn_gf2m::degppf(*this, &degree);
      }
   while (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.

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

   :msp_field(sp_field)
   {
   if(mem_len % sizeof(gf2m))
      {
      throw Botan::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 Botan::Decoding_Error("error decoding polynomial");
         }
      }
   this->get_degree();
   }

polyn_gf2m() [9/9]

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

create a polynomial from memory area (encoded)

Definition at line 159 of file polyn_gf2m.cpp.

References coeff, get_degree(), and msp_field.

   :msp_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 Botan::Decoding_Error("memory vector for polynomial has wrong size");
      }
   this->coeff = secure_vector<gf2m>(degree+1);
   gf2m ext_deg = this->msp_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();
   }

Member Function Documentation

add_to_coef()

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

inline

Definition at line 90 of file polyn_gf2m.h.

References coeff.

         {
         coeff[i] = 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 = 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()

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

   {
   int i, d;
   polyn_gf2m s(g.get_sp_field());

   d = g.get_degree();
   std::vector<polyn_gf2m> u = polyn_gf2m::sqmod_init(g);

   polyn_gf2m p( d - 1, g.msp_field);

   p.set_degree( 1);
   (*&p).set_coef( 1, 1);
   (*p_result) = d;
   for (i = 1; i <= (d / 2) * g.msp_field->get_extension_degree(); ++i)
      {
      polyn_gf2m r = p.sqmod(u, d);
      if ((i % g.msp_field->get_extension_degree()) == 0)
         {
         r[1] ^= 1;
         r.get_degree(); // The degree may change
         s = polyn_gf2m::gcd( g, r);

         if (s.get_degree() > 0)
            {
            (*p_result) = i / g.msp_field->get_extension_degree();
            break;
            }
         r[1] ^= 1;
         r.get_degree(); // The degree may change
         }
      // No need for the exchange s
      s = p;
      p = r;
      r = s;
      }


   }

eea_with_coefficients()

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

static

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

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

Condition that the EEA would break now

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

Definition at line 450 of file polyn_gf2m.cpp.

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

   {

   std::shared_ptr<GF2m_Field> msp_field = g.msp_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.msp_field);
   polyn_gf2m r1(dr - 1, g.msp_field);
   polyn_gf2m u0(dr - 1, g.msp_field);
   polyn_gf2m u1(dr - 1, g.msp_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 = msp_field->gf_div(r0[dr + j], r1[dr]);
         if (a != 0)
            {
            gf2m la = msp_field->gf_log(a);
            // u0(z) <- u0(z) + a * u1(z) * z^j
            for (i = 0; i <= du; ++i)
               {
               u0[i + j] ^= msp_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] ^= msp_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 = msp_field->gf_mul(u0.coeff[1], msp_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 = msp_field->gf_mul(u0.coeff[1], msp_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 = msp_field->gf_mul(u0[1], msp_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 770 of file polyn_gf2m.cpp.

References coeff, 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(coeff[i] >> 8);
      result.push_back(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 256 of file polyn_gf2m.cpp.

References m_deg, and msp_field.

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

get_coef()

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

inline

Definition at line 83 of file polyn_gf2m.h.

References coeff.

{ return coeff[i]; }

get_degree()

int Botan::polyn_gf2m::get_degree

(

)

const

Definition at line 230 of file polyn_gf2m.cpp.

References coeff, and m_deg.

Referenced by 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 = 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 81 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 74 of file polyn_gf2m.h.

References msp_field.

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

         { return msp_field; }

operator!=()

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

inline

Definition at line 40 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 47 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 798 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 77 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 79 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 431 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 ( uint32_t  i, gf2m  v  )

inline

Definition at line 85 of file polyn_gf2m.h.

References coeff.

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

         {
         coeff[i] = v;
         }

set_to_zero()

void Botan::polyn_gf2m::set_to_zero

(

)

Definition at line 224 of file polyn_gf2m.cpp.

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

Referenced by 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 325 of file polyn_gf2m.cpp.

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

Referenced by degppf(), and sqrt_mod_init().

   {
   int i, j;
   gf2m la;
   std::shared_ptr<GF2m_Field> sp_field = this->msp_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 291 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 677 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().

   {
   uint32_t i, t;
   uint32_t nb_polyn_sqrt_mat;
   std::shared_ptr<GF2m_Field> msp_field = g.msp_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 * msp_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 791 of file polyn_gf2m.cpp.

References coeff, m_deg, and msp_field.

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

   {
   std::swap(this->m_deg, other.m_deg);
   std::swap(this->msp_field, other.msp_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().

msp_field

std::shared_ptr<GF2m_Field> Botan::polyn_gf2m::msp_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