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
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) noexcept
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 polyn_gf2m &other)
	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) noexcept
	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) noexcept
	~polyn_gf2m ()=default

Static Public Member Functions
static size_t	degppf (const polyn_gf2m &g)
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)

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

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

Referenced by calc_degree_secure(), degppf(), eea_with_coefficients(), encode(), get_degree(), operator!=(), operator=(), operator=(), operator==(), polyn_gf2m(), polyn_gf2m(), polyn_gf2m(), sqmod(), sqmod_init(), sqrt_mod_init(), and swap().

polyn_gf2m() [2/9]

Botan::polyn_gf2m::polyn_gf2m ( )

inline

Definition at line 34 of file polyn_gf2m.h.

: m_deg(-1) {}

Referenced by 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 635 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];
      m_coeff.push_back(el);
   }
   get_degree();
}

References get_degree().

~polyn_gf2m()

Botan::polyn_gf2m::~polyn_gf2m ( )

default

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

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

polyn_gf2m() [5/9]

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

default

References polyn_gf2m().

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

                                                                                                      :
      m_deg(static_cast<int>(t)), m_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(), polyn_gf2m(), 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 111 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->m_coeff[0]));
   this->m_coeff = secure_vector<gf2m>(size);
   this->m_deg = -1;
   for(uint32_t i = 0; i < size; i++) {
      this->m_coeff[i] = decode_gf2m(mem);
      mem += sizeof(this->m_coeff[0]);
   }
   for(uint32_t i = 0; i < size; i++) {
      if(this->m_coeff[i] >= (1 << sp_field->get_extension_degree())) {
         throw Decoding_Error("error decoding polynomial");
      }
   }
   this->get_degree();
}

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

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

                                                                  :
      m_sp_field(sp_field) {
   const uint32_t 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->m_coeff = secure_vector<gf2m>(degree + 1);
   const gf2m ext_deg = static_cast<gf2m>(this->m_sp_field->get_extension_degree());
   for(uint32_t l = 0; l < polyn_size; l++) {
      uint32_t k = (l * ext_deg) / 8;
 
      uint32_t j = (l * ext_deg) % 8;
      gf2m 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 )

inlinenoexcept

Definition at line 66 of file polyn_gf2m.h.

{ this->swap(other); }

References polyn_gf2m(), and swap().

Member Function Documentation

add_to_coef()

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

inline

Definition at line 91 of file polyn_gf2m.h.

{ m_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 60 of file polyn_gf2m.cpp.

                                         {
   int i = static_cast<int>(this->m_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->m_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 Botan::expand_mask_16bit(), and polyn_gf2m().

Referenced by eea_with_coefficients(), and patchup_deg_secure().

degppf()

size_t Botan::polyn_gf2m::degppf ( const polyn_gf2m & g )

static

Definition at line 308 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 degppf(), get_degree(), get_sp_field(), polyn_gf2m(), set_coef(), sqmod(), and sqmod_init().

Referenced by degppf(), and 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 358 of file polyn_gf2m.cpp.

                                                                                   {
   std::shared_ptr<GF2m_Field> m_sp_field = g.m_sp_field;
   polyn_gf2m aux;
 
   // initialisation of the local variables
   // r0 <- g, r1 <- p, u0 <- 0, u1 <- 1
   int 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
   int du = 0;
   dr = r1.get_degree();
   int delta = r0.get_degree() - dr;
 
   int i = 0;
   int j = 0;
   while(dr >= break_deg) {
      for(j = delta; j >= 0; --j) {
         gf2m 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 = 0;
         volatile gf2m cond2 = 0;
         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.m_coeff[1], m_sp_field->gf_inv(r0.m_coeff[0])) == 1;
 
            // Condition sigma_3 = 0:
            int cond_u3 = u0.m_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.m_coeff[1], m_sp_field->gf_inv(r0.m_coeff[0])) == 1;
            int cond_u3 = u0.m_coeff[3] == 0;
 
            int cond_u5 = u0.m_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.m_coeff[3] == 0;
 
            int cond_u5 = u0.m_coeff[5] == 0;
 
            int cond_u7 = u0.m_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(), eea_with_coefficients(), Botan::expand_mask_16bit(), get_degree(), patchup_deg_secure(), polyn_gf2m(), set_coef(), and set_to_zero().

Referenced by eea_with_coefficients().

encode() [1/2]

secure_vector< uint8_t > Botan::polyn_gf2m::encode

(

)

const

Definition at line 647 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>(m_coeff[i]));
      result.push_back(get_byte<1>(m_coeff[i]));
   }
   return result;
}

References Botan::get_byte().

encode() [2/2]

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

References polyn_gf2m().

eval()

gf2m Botan::polyn_gf2m::eval

(

gf2m

a

)

Definition at line 193 of file polyn_gf2m.cpp.

                            {
   return eval_aux(this->m_coeff.data(), a, this->m_deg, this->m_sp_field);
}

References eval().

Referenced by eval().

get_coef()

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

inline

Definition at line 87 of file polyn_gf2m.h.

{ return m_coeff[i]; }

get_degree()

int Botan::polyn_gf2m::get_degree

(

)

const

Definition at line 168 of file polyn_gf2m.cpp.

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

References get_degree(), and polyn_gf2m().

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

get_lead_coef()

gf2m Botan::polyn_gf2m::get_lead_coef ( ) const

inline

Definition at line 85 of file polyn_gf2m.h.

{ return m_coeff[m_deg]; }

get_sp_field()

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

inline

Definition at line 79 of file polyn_gf2m.h.

{ return m_sp_field; }

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

operator!=()

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

inline

Definition at line 64 of file polyn_gf2m.h.

{ return !(*this == other); }

References polyn_gf2m().

operator=() [1/2]

polyn_gf2m & Botan::polyn_gf2m::operator= ( const polyn_gf2m & )

default

References polyn_gf2m().

operator=() [2/2]

polyn_gf2m & Botan::polyn_gf2m::operator= ( polyn_gf2m && other )

inlinenoexcept

Definition at line 68 of file polyn_gf2m.h.

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

References polyn_gf2m(), and swap().

operator==()

bool Botan::polyn_gf2m::operator==

(

const polyn_gf2m &

other

)

const

Definition at line 671 of file polyn_gf2m.cpp.

                                                         {
   return m_deg == other.m_deg && m_coeff == other.m_coeff;
}

References polyn_gf2m().

operator[]() [1/2]

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

inline

Definition at line 81 of file polyn_gf2m.h.

{ return m_coeff[i]; }

operator[]() [2/2]

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

inline

Definition at line 83 of file polyn_gf2m.h.

{ return m_coeff[i]; }

patchup_deg_secure()

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

Definition at line 343 of file polyn_gf2m.cpp.

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

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

Referenced by eea_with_coefficients(), and patchup_deg_secure().

set_coef()

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

inline

Definition at line 89 of file polyn_gf2m.h.

{ m_coeff[i] = 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 163 of file polyn_gf2m.cpp.

                             {
   clear_mem(this->m_coeff.data(), this->m_coeff.size());
   this->m_deg = -1;
}

References Botan::clear_mem(), and set_to_zero().

Referenced by eea_with_coefficients(), and set_to_zero().

sqmod()

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

Definition at line 257 of file polyn_gf2m.cpp.

                                                                   {
   int i = 0;
   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);
         gf2m la = sp_field->gf_mul_rrr(lpi, lpi);
         for(int 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(), polyn_gf2m(), set_coef(), and sqmod().

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

sqmod_init()

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

static

Definition at line 226 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 = 0;
   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].m_coeff.data(), 2);
      copy_mem(sq[i].m_coeff.data() + 2, sq[i - 1].m_coeff.data(), d);
      sq[i].set_degree(sq[i - 1].get_degree() + 2);
      polyn_gf2m::remainder(sq[i], g);
   }
   return sq;
}

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

Referenced by degppf(), sqmod_init(), 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 565 of file polyn_gf2m.cpp.

                                                                   {
   uint32_t i = 0;
   uint32_t t = 0;
   uint32_t nb_polyn_sqrt_mat = 0;
   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(), polyn_gf2m(), polyn_gf2m(), set_coef(), sqmod(), and sqmod_init().

Referenced by Botan::generate_mceliece_key().

swap()

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

noexcept

Definition at line 665 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->m_coeff, other.m_coeff);
}

References polyn_gf2m().

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

---

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