Botan  1.11.15
Public Member Functions | Static Public Member Functions | Public Attributes
Botan::polyn_gf2m Struct Reference

#include <polyn_gf2m.h>

List of all members.

Public Member Functions

void add_to_coef (u32bit i, gf2m v)
int calc_degree_secure () const
void degppf (const polyn_gf2m &g, int *p_result)
secure_vector< byteencode () const
void encode (u32bit min_numo_coeffs, byte *mem, u32bit mem_len) const
gf2m eval (gf2m a)
gf2m get_coef (u32bit i) const
int get_degree () const
gf2m get_lead_coef () const
std::shared_ptr
< gf2m_small_m::Gf2m_Field
get_sp_field () const
bool operator!= (const polyn_gf2m &other) const
polyn_gf2moperator= (const polyn_gf2m &)
polyn_gf2moperator= (polyn_gf2m &&other)
bool operator== (const polyn_gf2m &other) const
gf2moperator[] (size_t i)
gf2m operator[] (size_t i) const
void patchup_deg_secure (u32bit trgt_deg, volatile gf2m patch_elem)
 polyn_gf2m (std::shared_ptr< gf2m_small_m::Gf2m_Field > sp_field)
 polyn_gf2m ()
 polyn_gf2m (const secure_vector< byte > &encoded, std::shared_ptr< gf2m_small_m::Gf2m_Field > sp_field)
 polyn_gf2m (polyn_gf2m &&other)
 polyn_gf2m (int d, std::shared_ptr< gf2m_small_m::Gf2m_Field > sp_field)
 polyn_gf2m (polyn_gf2m const &other)
 polyn_gf2m (int t, RandomNumberGenerator &rng, std::shared_ptr< gf2m_small_m::Gf2m_Field > sp_field)
 polyn_gf2m (const byte *mem, u32bit mem_len, std::shared_ptr< gf2m_small_m::Gf2m_Field > sp_field)
 polyn_gf2m (int degree, const unsigned char *mem, u32bit mem_byte_len, std::shared_ptr< gf2m_small_m::Gf2m_Field > sp_field)
void set_coef (u32bit 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_gf2msqmod_init (const polyn_gf2m &g)
static std::vector< polyn_gf2msqrt_mod_init (const polyn_gf2m &g)

Public Attributes

secure_vector< gf2mcoeff
int m_deg
std::shared_ptr
< gf2m_small_m::Gf2m_Field
msp_field

Detailed Description

Definition at line 24 of file polyn_gf2m.h.


Constructor & Destructor Documentation

Botan::polyn_gf2m::polyn_gf2m ( std::shared_ptr< gf2m_small_m::Gf2m_Field sp_field)

create a zero polynomial:

Definition at line 145 of file polyn_gf2m.cpp.

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

Definition at line 32 of file polyn_gf2m.h.

Referenced by sqmod_init(), and sqrt_mod_init().

         :m_deg(-1)
         {};
Botan::polyn_gf2m::polyn_gf2m ( const secure_vector< byte > &  encoded,
std::shared_ptr< gf2m_small_m::Gf2m_Field sp_field 
)

Definition at line 747 of file polyn_gf2m.cpp.

References get_degree().

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

   }
Botan::polyn_gf2m::polyn_gf2m ( polyn_gf2m &&  other) [inline]

Definition at line 44 of file polyn_gf2m.h.

         {
         this->swap(other);
         };
Botan::polyn_gf2m::polyn_gf2m ( int  d,
std::shared_ptr< gf2m_small_m::Gf2m_Field sp_field 
)

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

Definition at line 89 of file polyn_gf2m.cpp.

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

Definition at line 83 of file polyn_gf2m.cpp.

   :m_deg(other.m_deg),
    coeff(other.coeff),
    msp_field(other.msp_field)
   { }
Botan::polyn_gf2m::polyn_gf2m ( int  t,
Botan::RandomNumberGenerator rng,
std::shared_ptr< gf2m_small_m::Gf2m_Field sp_field 
)

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

Definition at line 628 of file polyn_gf2m.cpp.

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

   :m_deg(t),
    coeff(t+1),
    msp_field(sp_field)
   {
   int i;
   (*this).set_coef( t, 1);
   i = 0;
   int m_deg;
   do
      {
      for (i = 0; i < t; ++i)
         {
         (*this).set_coef( i, random_code_element(sp_field->get_cardinality(), rng));
         }
      polyn_gf2m::degppf(*this, &m_deg);
      }
   while (m_deg < t);
   }
Botan::polyn_gf2m::polyn_gf2m ( const byte mem,
u32bit  mem_len,
std::shared_ptr< gf2m_small_m::Gf2m_Field sp_field 
)

decode a polynomial from memory:

Definition at line 118 of file polyn_gf2m.cpp.

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

   :msp_field(sp_field)
   {
   if(mem_len % sizeof(gf2m))
      {
      throw new Botan::Decoding_Error("illegal length of memory to decode ");
      }

   u32bit size = (mem_len / sizeof(this->coeff[0])) ;
   this->coeff = secure_vector<gf2m>(size);
   this->m_deg = -1;
   for(u32bit i = 0; i < size; i++)
      {
      this->coeff[i] = gf2m_small_m::decode_gf2m(mem);
      mem += sizeof(this->coeff[0]);
      }
   for(u32bit 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();
   }
Botan::polyn_gf2m::polyn_gf2m ( int  degree,
const unsigned char *  mem,
u32bit  mem_byte_len,
std::shared_ptr< gf2m_small_m::Gf2m_Field sp_field 
)

create a polynomial from memory area (encoded)

Definition at line 151 of file polyn_gf2m.cpp.

References coeff, get_degree(), and msp_field.

   :msp_field(sp_field)
   {
   u32bit j, k, l;
   gf2m a;
   u32bit 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

void Botan::polyn_gf2m::add_to_coef ( u32bit  i,
gf2m  v 
) [inline]

Definition at line 92 of file polyn_gf2m.h.

         {
         coeff[i] = coeff[i] ^ v;
         }

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

References Botan::expand_mask_16bit().

Referenced by eea_with_coefficients(), and patchup_deg_secure().

   {
   int i = this->coeff.size() - 1;
   int result = 0;
   u32bit found_mask = 0;
   u32bit 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;
   }
void Botan::polyn_gf2m::degppf ( const polyn_gf2m g,
int *  p_result 
)

Definition at line 380 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;
      }


   }
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-lenght" contributions from the square root computation).

Definition at line 438 of file polyn_gf2m.cpp.

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

   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 - 1;
            cond2 =  u0.get_degree() < break_deg - 1;
            cond1 &= cond2;
            }
         /* expand cond1 to a full mask */
         //CSEC_MASK__GEN_MASK_16B(cond1, 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 u32bit 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)
            {
            u32bit 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-lenght" 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)
            {
            u32bit 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)
            {
            u32bit 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
   }
secure_vector< byte > Botan::polyn_gf2m::encode ( ) const

Definition at line 762 of file polyn_gf2m.cpp.

References m_deg.

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

   {
   secure_vector<byte> result;

   if(m_deg < 1)
      {
      result.push_back(0);
      result.push_back(0);
      return result;
      }

   u32bit 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;
   }
void Botan::polyn_gf2m::encode ( u32bit  min_numo_coeffs,
byte mem,
u32bit  mem_len 
) const

Definition at line 248 of file polyn_gf2m.cpp.

References m_deg, and msp_field.

   {
   return eval_aux(&this->coeff[0], a, this->m_deg, this->msp_field);
   }
gf2m Botan::polyn_gf2m::get_coef ( u32bit  i) const [inline]

Definition at line 85 of file polyn_gf2m.h.

{ return coeff[i]; }

Definition at line 222 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;
   }

Definition at line 83 of file polyn_gf2m.h.

{ return coeff[m_deg]; }
std::shared_ptr<gf2m_small_m::Gf2m_Field> Botan::polyn_gf2m::get_sp_field ( ) const [inline]

Definition at line 76 of file polyn_gf2m.h.

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

         { return msp_field; };
bool Botan::polyn_gf2m::operator!= ( const polyn_gf2m other) const [inline]

Definition at line 42 of file polyn_gf2m.h.

{ return !(*this == other); };
polyn_gf2m& Botan::polyn_gf2m::operator= ( const polyn_gf2m )
polyn_gf2m& Botan::polyn_gf2m::operator= ( polyn_gf2m &&  other) [inline]

Definition at line 49 of file polyn_gf2m.h.

         {
         if(this != &other)
            {
            this->swap(other);
            }
         return *this;
         }
bool Botan::polyn_gf2m::operator== ( const polyn_gf2m other) const

Definition at line 790 of file polyn_gf2m.cpp.

References coeff, and m_deg.

   {
   if(m_deg != other.m_deg || coeff != other.coeff)
      {
      return false;
      }
   return true;
   }
gf2m& Botan::polyn_gf2m::operator[] ( size_t  i) [inline]

Definition at line 79 of file polyn_gf2m.h.

{ return coeff[i]; };
gf2m Botan::polyn_gf2m::operator[] ( size_t  i) const [inline]

Definition at line 81 of file polyn_gf2m.h.

{ return coeff[i]; }
void Botan::polyn_gf2m::patchup_deg_secure ( u32bit  trgt_deg,
volatile gf2m  patch_elem 
)

Definition at line 419 of file polyn_gf2m.cpp.

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

Referenced by eea_with_coefficients().

   {
   u32bit i;
   if(this->coeff.size() < trgt_deg)
      {
      return;
      }
   for(i = 0; i < this->coeff.size(); i++)
      {
      u32bit 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();
   }
void Botan::polyn_gf2m::set_coef ( u32bit  i,
gf2m  v 
) [inline]

Definition at line 87 of file polyn_gf2m.h.

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

         {
         coeff[i] = v;
         };

Definition at line 216 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;
   }
polyn_gf2m Botan::polyn_gf2m::sqmod ( const std::vector< polyn_gf2m > &  sq,
int  d 
)

Definition at line 313 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_small_m::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;
   }
std::vector< polyn_gf2m > Botan::polyn_gf2m::sqmod_init ( const polyn_gf2m g) [static]

Definition at line 279 of file polyn_gf2m.cpp.

References Botan::clear_mem(), 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 u32bit d = static_cast<u32bit>(signed_deg);
   u32bit t = g.m_deg;
   // create t zero polynomials
   u32bit 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;
   }
std::vector< polyn_gf2m > Botan::polyn_gf2m::sqrt_mod_init ( const polyn_gf2m g) [static]

Definition at line 669 of file polyn_gf2m.cpp.

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

Referenced by Botan::generate_mceliece_key().

   {
   u32bit i, t;
   u32bit nb_polyn_sqrt_mat;
   std::shared_ptr<gf2m_small_m::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;
   }

Definition at line 783 of file polyn_gf2m.cpp.

References coeff, m_deg, and msp_field.

   {
   std::swap(this->m_deg, other.m_deg);
   std::swap(this->msp_field, other.msp_field);
   std::swap(this->coeff, other.coeff);
   }
std::string Botan::polyn_gf2m::to_string ( ) const

Definition at line 96 of file polyn_gf2m.cpp.

References coeff, and get_degree().

   {
   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

Definition at line 150 of file polyn_gf2m.h.

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


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