Botan  1.11.15
src/lib/pubkey/mce/polyn_gf2m.cpp
Go to the documentation of this file.
00001 /**
00002  * (C) Copyright Projet SECRET, INRIA, Rocquencourt
00003  * (C) Bhaskar Biswas and  Nicolas Sendrier
00004  *
00005  * (C) 2014 cryptosource GmbH
00006  * (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
00007  *
00008  * Botan is released under the Simplified BSD License (see license.txt)
00009  *
00010  */
00011 
00012 #include <botan/polyn_gf2m.h>
00013 #include <botan/gf2m_rootfind_dcmp.h>
00014 #include <botan/code_based_util.h>
00015 #include <botan/gf2m_small_m.h>
00016 #include <botan/internal/bit_ops.h>
00017 
00018 namespace Botan {
00019 
00020 using namespace Botan::gf2m_small_m;
00021 
00022 namespace {
00023 
00024 gf2m generate_gf2m_mask(gf2m a)
00025    {
00026    gf2m result =  (a != 0);
00027    return ~(result - 1);
00028    }
00029 
00030 unsigned nlz_16bit(u16bit x)
00031    {
00032    unsigned n;
00033    if(x == 0) return 16;
00034    n = 0;
00035    if(x <= 0x00FF) {n = n + 8; x = x << 8;}
00036    if(x <= 0x0FFF) {n = n + 4; x = x << 4;}
00037    if(x <= 0x3FFF) {n = n + 2; x = x << 2;}
00038    if(x <= 0x7FFF) {n = n + 1;}
00039    return n;
00040    }
00041 }
00042 
00043 using namespace Botan::gf2m_small_m;
00044 
00045 int polyn_gf2m::calc_degree_secure() const
00046    {
00047    int i = this->coeff.size() - 1;
00048    int result = 0;
00049    u32bit found_mask = 0;
00050    u32bit tracker_mask = 0xffff;
00051    for( ; i >= 0; i--)
00052       {
00053       found_mask = expand_mask_16bit(this->coeff[i]);
00054       result |= i & found_mask & tracker_mask;
00055       // tracker mask shall become zero once found mask is set
00056       // it shall remain zero from then on
00057       tracker_mask = tracker_mask & ~found_mask;
00058       }
00059    const_cast<polyn_gf2m*>(this)->m_deg = result;
00060    return result;
00061    }
00062 /**
00063 * number of leading zeros
00064 */
00065 
00066 gf2m random_code_element(unsigned code_length, Botan::RandomNumberGenerator& rng)
00067    {
00068    if(code_length == 0)
00069       {
00070       throw Invalid_Argument("random_code_element() was supplied a code length of zero");
00071       }
00072    unsigned nlz = nlz_16bit(code_length-1);
00073    gf2m mask = (1 << (16-nlz)) -1;
00074    gf2m result;
00075    do
00076       {
00077       rng.randomize(reinterpret_cast<byte*>(&result), sizeof(result));
00078       result &= mask;
00079       } while(result >= code_length); // rejection sampling
00080    return result;
00081    }
00082 
00083 polyn_gf2m::polyn_gf2m(polyn_gf2m const& other)
00084    :m_deg(other.m_deg),
00085     coeff(other.coeff),
00086     msp_field(other.msp_field)
00087    { }
00088 
00089 polyn_gf2m::polyn_gf2m(   int d, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field)
00090    :m_deg(-1),
00091     coeff(d+1),
00092     msp_field(sp_field)
00093    {
00094    }
00095 
00096 std::string polyn_gf2m::to_string() const
00097    {
00098    int d = get_degree();
00099    std::string result;
00100    for(int i = 0; i <= d; i ++)
00101       {
00102       result += std::to_string(this->coeff[i]);
00103       if(i != d)
00104          {
00105          result += ", ";
00106          }
00107       }
00108    return result;
00109    }
00110 /**
00111 * doesn't save coefficients:
00112 */
00113 void polyn_gf2m::realloc(u32bit new_size)
00114    {
00115    this->coeff = secure_vector<gf2m>(new_size);
00116    }
00117 
00118 polyn_gf2m::polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field)
00119    :msp_field(sp_field)
00120    {
00121    if(mem_len % sizeof(gf2m))
00122       {
00123       throw new Botan::Decoding_Error("illegal length of memory to decode ");
00124       }
00125 
00126    u32bit size = (mem_len / sizeof(this->coeff[0])) ;
00127    this->coeff = secure_vector<gf2m>(size);
00128    this->m_deg = -1;
00129    for(u32bit i = 0; i < size; i++)
00130       {
00131       this->coeff[i] = gf2m_small_m::decode_gf2m(mem);
00132       mem += sizeof(this->coeff[0]);
00133       }
00134    for(u32bit i = 0; i < size; i++)
00135       {
00136       if(this->coeff[i] >= (1 << sp_field->get_extension_degree()))
00137          {
00138          throw Botan::Decoding_Error("error decoding polynomial");
00139          }
00140       }
00141    this->get_degree();
00142    }
00143 
00144 
00145 polyn_gf2m::polyn_gf2m( std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field )
00146    : m_deg(-1),
00147      coeff(1),
00148      msp_field(sp_field)
00149    {};
00150 
00151 polyn_gf2m::polyn_gf2m(int degree, const unsigned  char* mem, u32bit mem_byte_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field)
00152    :msp_field(sp_field)
00153    {
00154    u32bit j, k, l;
00155    gf2m a;
00156    u32bit polyn_size;
00157    polyn_size = degree + 1;
00158    if(polyn_size * sp_field->get_extension_degree() > 8 * mem_byte_len)
00159       {
00160       throw Botan::Decoding_Error("memory vector for polynomial has wrong size");
00161       }
00162    this->coeff = secure_vector<gf2m>(degree+1);
00163    gf2m ext_deg = this->msp_field->get_extension_degree();
00164    for (l = 0; l < polyn_size; l++)
00165       {
00166       k = (l * ext_deg) / 8;
00167 
00168       j = (l * ext_deg) % 8;
00169       a = mem[k] >> j;
00170       if (j + ext_deg > 8)
00171          {
00172          a ^= mem[k + 1] << (8- j);
00173          }
00174       if(j + ext_deg > 16)
00175          {
00176          a ^= mem[k + 2] << (16- j);
00177          }
00178       a &= ((1 << ext_deg) - 1);
00179       (*this).set_coef( l, a);
00180       }
00181 
00182    this->get_degree();
00183    }
00184 
00185 #if 0
00186 void polyn_gf2m::encode(u32bit min_numo_coeffs, byte* mem, u32bit mem_len) const
00187    {
00188    u32bit i;
00189    u32bit numo_coeffs, needed_size;
00190    this->get_degree();
00191    numo_coeffs = (min_numo_coeffs > static_cast<u32bit>(this->m_deg+1)) ? min_numo_coeffs : this->m_deg+1;
00192    needed_size = sizeof(this->coeff[0]) * numo_coeffs;
00193    if(mem_len < needed_size)
00194       {
00195       Invalid_Argument("provided memory too small to encode polynomial");
00196       }
00197 
00198    for(i = 0; i < numo_coeffs; i++)
00199       {
00200       gf2m to_enc;
00201       if(i >= static_cast<u32bit>(this->m_deg+1))
00202          {
00203          /* encode a zero */
00204          to_enc = 0;
00205          }
00206       else
00207          {
00208          to_enc = this->coeff[i];
00209          }
00210       mem += encode_gf2m(to_enc, mem);
00211       }
00212    }
00213 #endif
00214 
00215 
00216 void polyn_gf2m::set_to_zero()
00217    {
00218    clear_mem(&this->coeff[0], this->coeff.size());
00219    this->m_deg = -1;
00220    }
00221 
00222 int polyn_gf2m::get_degree() const
00223    {
00224    int d = this->coeff.size() - 1;
00225    while ((d >= 0) && (this->coeff[d] == 0))
00226       --d;
00227    const_cast<polyn_gf2m*>(this)->m_deg = d;
00228    return d;
00229    }
00230 
00231 
00232 static gf2m eval_aux(const gf2m * /*restrict*/ coeff, gf2m a, int d, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field)
00233    {
00234    gf2m b;
00235    b = coeff[d--];
00236    for (; d >= 0; --d)
00237       if (b != 0)
00238          {
00239          b = sp_field->gf_mul(b, a) ^ coeff[d];
00240          }
00241       else
00242          {
00243          b = coeff[d];
00244          }
00245    return b;
00246    }
00247 
00248 gf2m polyn_gf2m::eval(gf2m a)
00249    {
00250    return eval_aux(&this->coeff[0], a, this->m_deg, this->msp_field);
00251    }
00252 
00253 
00254 // p will contain it's remainder modulo g
00255 void polyn_gf2m::remainder(polyn_gf2m &p, const polyn_gf2m & g)
00256    {
00257    int i, j, d;
00258    std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field;
00259    d = p.get_degree() - g.get_degree();
00260    if (d >= 0) {
00261    gf2m la = msp_field->gf_inv_rn(g.get_lead_coef());
00262 
00263    for (i = p.get_degree(); d >= 0; --i, --d) {
00264    if (p[i] != 0) {
00265    gf2m lb = msp_field->gf_mul_rrn(la, p[i]);
00266    for (j = 0; j < g.get_degree(); ++j)
00267       {
00268       p[j+d] ^= msp_field->gf_mul_zrz(lb, g[j]);
00269       }
00270    (*&p).set_coef( i, 0);
00271    }
00272    }
00273    p.set_degree( g.get_degree() - 1);
00274    while ((p.get_degree() >= 0) && (p[p.get_degree()] == 0))
00275       p.set_degree( p.get_degree() - 1);
00276    }
00277    }
00278 
00279 std::vector<polyn_gf2m> polyn_gf2m::sqmod_init(const polyn_gf2m & g)
00280    {
00281    std::vector<polyn_gf2m> sq;
00282    const int signed_deg = g.get_degree();
00283    if(signed_deg <= 0)
00284       throw Invalid_Argument("cannot compute sqmod for such low degree");
00285 
00286    const u32bit d = static_cast<u32bit>(signed_deg);
00287    u32bit t = g.m_deg;
00288    // create t zero polynomials
00289    u32bit i;
00290    for (i = 0; i < t; ++i)
00291       {
00292       sq.push_back(polyn_gf2m(t+1, g.get_sp_field()));
00293       }
00294    for (i = 0; i < d / 2; ++i)
00295       {
00296       sq[i].set_degree( 2 * i);
00297       (*&sq[i]).set_coef( 2 * i, 1);
00298       }
00299 
00300    for (; i < d; ++i)
00301       {
00302       clear_mem(&sq[i].coeff[0], 2);
00303       copy_mem(&sq[i].coeff[0] + 2, &sq[i - 1].coeff[0], d);
00304       sq[i].set_degree( sq[i - 1].get_degree() + 2);
00305       polyn_gf2m::remainder(sq[i], g);
00306       }
00307    return sq;
00308    }
00309 
00310 /*Modulo p square of a certain polynomial g, sq[] contains the square
00311 Modulo g of the base canonical polynomials of degree < d, where d is
00312 the degree of G. The table sq[] will be calculated by polyn_gf2m__sqmod_init*/
00313 polyn_gf2m polyn_gf2m::sqmod( const std::vector<polyn_gf2m> & sq, int d)
00314    {
00315    int i, j;
00316    gf2m la;
00317    std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = this->msp_field;
00318 
00319    polyn_gf2m result(d - 1, sp_field);
00320    // terms of low degree
00321    for (i = 0; i < d / 2; ++i)
00322       {
00323       (*&result).set_coef( i * 2, sp_field->gf_square((*this)[i]));
00324       }
00325 
00326    // terms of high degree
00327    for (; i < d; ++i)
00328       {
00329       gf2m lpi = (*this)[i];
00330       if (lpi != 0)
00331          {
00332          lpi = sp_field->gf_log(lpi);
00333          la = sp_field->gf_mul_rrr(lpi, lpi);
00334          for (j = 0; j < d; ++j)
00335             {
00336             result[j] ^= sp_field->gf_mul_zrz(la, sq[i][j]);
00337             }
00338          }
00339       }
00340 
00341    // Update degre
00342    result.set_degree( d - 1);
00343    while ((result.get_degree() >= 0) && (result[result.get_degree()] == 0))
00344       result.set_degree( result.get_degree() - 1);
00345    return result;
00346    }
00347 
00348 
00349 // destructive
00350 polyn_gf2m polyn_gf2m::gcd_aux(polyn_gf2m& p1, polyn_gf2m& p2)
00351    {
00352    if (p2.get_degree() == -1)
00353       return p1;
00354    else {
00355    polyn_gf2m::remainder(p1, p2);
00356    return polyn_gf2m::gcd_aux(p2, p1);
00357    }
00358    }
00359 
00360 
00361 polyn_gf2m polyn_gf2m::gcd(polyn_gf2m const& p1, polyn_gf2m const& p2)
00362    {
00363    polyn_gf2m a(p1);
00364    polyn_gf2m b(p2);
00365    if (a.get_degree() < b.get_degree())
00366       {
00367       return polyn_gf2m(polyn_gf2m::gcd_aux(b, a));
00368       }
00369    else
00370       {
00371       return polyn_gf2m(polyn_gf2m::gcd_aux(a, b));
00372       }
00373    }
00374 
00375 
00376 
00377 
00378 
00379 // Returns the degree of the smallest factor
00380 void polyn_gf2m::degppf(const polyn_gf2m & g, int* p_result)
00381    {
00382    int i, d;
00383    polyn_gf2m s(g.get_sp_field());
00384 
00385    d = g.get_degree();
00386    std::vector<polyn_gf2m> u = polyn_gf2m::sqmod_init(g);
00387 
00388    polyn_gf2m p( d - 1, g.msp_field);
00389 
00390    p.set_degree( 1);
00391    (*&p).set_coef( 1, 1);
00392    (*p_result) = d;
00393    for (i = 1; i <= (d / 2) * g.msp_field->get_extension_degree(); ++i)
00394       {
00395       polyn_gf2m r = p.sqmod(u, d);
00396       if ((i % g.msp_field->get_extension_degree()) == 0)
00397          {
00398          r[1] ^= 1;
00399          r.get_degree(); // The degree may change
00400          s = polyn_gf2m::gcd( g, r);
00401 
00402          if (s.get_degree() > 0)
00403             {
00404             (*p_result) = i / g.msp_field->get_extension_degree();
00405             break;
00406             }
00407          r[1] ^= 1;
00408          r.get_degree(); // The degree may change
00409          }
00410       // No need for the exchange s
00411       s = p;
00412       p = r;
00413       r = s;
00414       }
00415 
00416 
00417    }
00418 
00419 void polyn_gf2m::patchup_deg_secure( u32bit trgt_deg, volatile gf2m patch_elem)
00420    {
00421    u32bit i;
00422    if(this->coeff.size() < trgt_deg)
00423       {
00424       return;
00425       }
00426    for(i = 0; i < this->coeff.size(); i++)
00427       {
00428       u32bit equal, equal_mask;
00429       this->coeff[i] |= patch_elem;
00430       equal = (i == trgt_deg);
00431       equal_mask = expand_mask_16bit(equal);
00432       patch_elem &= ~equal_mask;
00433       }
00434    this->calc_degree_secure();
00435    }
00436 // We suppose m_deg(g) >= m_deg(p)
00437 // v is the problem
00438 std::pair<polyn_gf2m, polyn_gf2m> polyn_gf2m::eea_with_coefficients( const polyn_gf2m & p, const polyn_gf2m & g, int break_deg)
00439    {
00440 
00441    std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field;
00442    int i, j, dr, du, delta;
00443    gf2m a;
00444    polyn_gf2m aux;
00445 
00446    // initialisation of the local variables
00447    // r0 <- g, r1 <- p, u0 <- 0, u1 <- 1
00448    dr = g.get_degree();
00449 
00450    polyn_gf2m r0(dr, g.msp_field);
00451    polyn_gf2m r1(dr - 1, g.msp_field);
00452    polyn_gf2m u0(dr - 1, g.msp_field);
00453    polyn_gf2m u1(dr - 1, g.msp_field);
00454 
00455    r0 = g;
00456    r1 = p;
00457    u0.set_to_zero();
00458    u1.set_to_zero();
00459    (*&u1).set_coef( 0, 1);
00460    u1.set_degree( 0);
00461 
00462 
00463    // invariants:
00464    // r1 = u1 * p + v1 * g
00465    // r0 = u0 * p + v0 * g
00466    // and m_deg(u1) = m_deg(g) - m_deg(r0)
00467    // It stops when m_deg (r1) <t (m_deg (r0)> = t)
00468    // And therefore m_deg (u1) = m_deg (g) - m_deg (r0) <m_deg (g) - break_deg
00469    du = 0;
00470    dr = r1.get_degree();
00471    delta = r0.get_degree() - dr;
00472 
00473 
00474    while (dr >= break_deg)
00475       {
00476 
00477       for (j = delta; j >= 0; --j)
00478          {
00479          a = msp_field->gf_div(r0[dr + j], r1[dr]);
00480          if (a != 0)
00481             {
00482             gf2m la = msp_field->gf_log(a);
00483             // u0(z) <- u0(z) + a * u1(z) * z^j
00484             for (i = 0; i <= du; ++i)
00485                {
00486                u0[i + j] ^= msp_field->gf_mul_zrz(la, u1[i]);
00487                }
00488             // r0(z) <- r0(z) + a * r1(z) * z^j
00489             for (i = 0; i <= dr; ++i)
00490                {
00491                r0[i + j] ^= msp_field->gf_mul_zrz(la, r1[i]);
00492                }
00493             }
00494          } // end loop over j
00495 
00496       if(break_deg != 1) /* key eq. solving */
00497          {
00498          /* [ssms_icisc09] Countermeasure
00499          * d_break from paper equals break_deg - 1
00500          * */
00501 
00502          volatile gf2m fake_elem = 0x01;
00503          volatile gf2m cond1, cond2;
00504          int trgt_deg = r1.get_degree() - 1;
00505          r0.calc_degree_secure();
00506          u0.calc_degree_secure();
00507          if(!(g.get_degree() % 2))
00508             {
00509             /* t even */
00510             cond1 = r0.get_degree() < break_deg - 1;
00511             }
00512          else
00513             {
00514             /* t odd */
00515             cond1 =  r0.get_degree() <= break_deg - 1;
00516             cond2 =  u0.get_degree() < break_deg - 1;
00517             cond1 &= cond2;
00518             }
00519          /* expand cond1 to a full mask */
00520          //CSEC_MASK__GEN_MASK_16B(cond1, mask);
00521          gf2m mask = generate_gf2m_mask(cond1);
00522          fake_elem &= mask;
00523          r0.patchup_deg_secure(trgt_deg, fake_elem);
00524          }
00525       if(break_deg == 1) /* syndrome inversion */
00526          {
00527          volatile gf2m fake_elem = 0x00;
00528          volatile u32bit trgt_deg = 0;
00529          r0.calc_degree_secure();
00530          u0.calc_degree_secure();
00531          /**
00532          * countermeasure against the low weight attacks for w=4, w=6 and w=8.
00533          * Higher values are not covered since for w=8 we already have a
00534          * probability for a positive of 1/n^3 from random ciphertexts with the
00535          * given weight. For w = 10 it would be 1/n^4 and so on. Thus attacks
00536          * based on such high values of w are considered impractical.
00537          *
00538          * The outer test for the degree of u ( Omega in the paper ) needs not to
00539          * be disguised. Each of the three is performed at most once per EEA
00540          * (syndrome inversion) execution, the attacker knows this already when
00541          * preparing the ciphertext with the given weight. Inside these three
00542          * cases however, we must use timing neutral (branch free) operations to
00543          * implement the condition detection and the counteractions.
00544          *
00545          */
00546          if(u0.get_degree() == 4)
00547             {
00548             u32bit mask = 0;
00549             /**
00550             * Condition that the EEA would break now
00551             */
00552             int cond_r = r0.get_degree() == 0;
00553             /**
00554             * Now come the conditions for all odd coefficients of this sigma
00555             * candiate. If they are all fulfilled, then we know that we have a low
00556             * weight error vector, since the key-equation solving EEA is skipped if
00557             * the degree of tau^2 is low (=m_deg(u0)) and all its odd cofficients are
00558             * zero (they would cause "full-lenght" contributions from the square
00559             * root computation).
00560             */
00561             // Condition for the coefficient to Y to be cancelled out by the
00562             // addition of Y before the square root computation:
00563             int cond_u1 = msp_field->gf_mul(u0.coeff[1], msp_field->gf_inv(r0.coeff[0])) == 1;
00564 
00565             // Condition sigma_3 = 0:
00566             int cond_u3 = u0.coeff[3] == 0;
00567             // combine the conditions:
00568             cond_r &= (cond_u1 & cond_u3);
00569             // mask generation:
00570             mask = expand_mask_16bit(cond_r);
00571             trgt_deg = 2 & mask;
00572             fake_elem = 1 & mask;
00573             }
00574          else if(u0.get_degree() == 6)
00575             {
00576             u32bit mask = 0;
00577             int cond_r= r0.get_degree() == 0;
00578             int cond_u1 = msp_field->gf_mul(u0.coeff[1], msp_field->gf_inv(r0.coeff[0])) == 1;
00579             int cond_u3 = u0.coeff[3] == 0;
00580 
00581             int cond_u5 = u0.coeff[5] == 0;
00582 
00583             cond_r &= (cond_u1 & cond_u3 & cond_u5);
00584             mask = expand_mask_16bit(cond_r);
00585             trgt_deg = 4 & mask;
00586             fake_elem = 1 & mask;
00587             }
00588          else if(u0.get_degree() == 8)
00589             {
00590             u32bit mask = 0;
00591             int cond_r= r0.get_degree() == 0;
00592             int cond_u1 = msp_field->gf_mul(u0[1], msp_field->gf_inv(r0[0])) == 1;
00593             int cond_u3 = u0.coeff[3] == 0;
00594 
00595             int cond_u5 = u0.coeff[5] == 0;
00596 
00597             int cond_u7 = u0.coeff[7] == 0;
00598 
00599             cond_r &= (cond_u1 & cond_u3 & cond_u5 & cond_u7);
00600             mask = expand_mask_16bit(cond_r);
00601             trgt_deg = 6 & mask;
00602             fake_elem = 1 & mask;
00603             }
00604          r0.patchup_deg_secure(trgt_deg, fake_elem);
00605          }
00606       // exchange
00607       aux = r0; r0 = r1; r1 = aux;
00608       aux = u0; u0 = u1; u1 = aux;
00609 
00610       du = du + delta;
00611       delta = 1;
00612       while (r1[dr - delta] == 0)
00613          {
00614          delta++;
00615          }
00616 
00617 
00618       dr -= delta;
00619       } /* end  while loop (dr >= break_deg) */
00620 
00621 
00622    u1.set_degree( du);
00623    r1.set_degree( dr);
00624    //return u1 and r1;
00625    return std::make_pair(u1,r1); // coefficients u,v
00626    }
00627 
00628 polyn_gf2m::polyn_gf2m(int t, Botan::RandomNumberGenerator& rng, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field)
00629    :m_deg(t),
00630     coeff(t+1),
00631     msp_field(sp_field)
00632    {
00633    int i;
00634    (*this).set_coef( t, 1);
00635    i = 0;
00636    int m_deg;
00637    do
00638       {
00639       for (i = 0; i < t; ++i)
00640          {
00641          (*this).set_coef( i, random_code_element(sp_field->get_cardinality(), rng));
00642          }
00643       polyn_gf2m::degppf(*this, &m_deg);
00644       }
00645    while (m_deg < t);
00646    }
00647 
00648 
00649 void polyn_gf2m::poly_shiftmod( const polyn_gf2m & g)
00650    {
00651    int i, t;
00652    gf2m a;
00653 
00654    if(g.get_degree() <= 0)
00655       {
00656       throw Invalid_Argument("shiftmod cannot be called on polynomials of degree 0 or less");
00657       }
00658    std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field;
00659 
00660    t = g.get_degree();
00661    a = msp_field->gf_div(this->coeff[t-1], g.coeff[t]);
00662    for (i = t - 1; i > 0; --i)
00663       {
00664       this->coeff[i] = this->coeff[i - 1] ^ this->msp_field->gf_mul(a, g.coeff[i]);
00665       }
00666    this->coeff[0] = msp_field->gf_mul(a, g.coeff[0]);
00667    }
00668 
00669 std::vector<polyn_gf2m> polyn_gf2m::sqrt_mod_init(const polyn_gf2m & g)
00670    {
00671    u32bit i, t;
00672    u32bit nb_polyn_sqrt_mat;
00673    std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field;
00674    std::vector<polyn_gf2m> result;
00675    t = g.get_degree();
00676    nb_polyn_sqrt_mat = t/2;
00677 
00678    std::vector<polyn_gf2m> sq_aux = polyn_gf2m::sqmod_init(g);
00679 
00680 
00681    polyn_gf2m p( t - 1, g.get_sp_field());
00682    p.set_degree( 1);
00683 
00684    (*&p).set_coef( 1, 1);
00685    // q(z) = 0, p(z) = z
00686    for (i = 0; i < t * msp_field->get_extension_degree() - 1; ++i)
00687       {
00688       // q(z) <- p(z)^2 mod g(z)
00689       polyn_gf2m q = p.sqmod(sq_aux, t);
00690       // q(z) <-> p(z)
00691       polyn_gf2m aux = q;
00692       q = p;
00693       p = aux;
00694       }
00695    // p(z) = z^(2^(tm-1)) mod g(z) = sqrt(z) mod g(z)
00696 
00697    for (i = 0; i < nb_polyn_sqrt_mat; ++i)
00698       {
00699       result.push_back(polyn_gf2m(t - 1, g.get_sp_field()));
00700       }
00701 
00702    result[0] = p;
00703    result[0].get_degree();
00704    for(i = 1; i < nb_polyn_sqrt_mat; i++)
00705       {
00706       result[i] = result[i - 1];
00707       result[i].poly_shiftmod(g),
00708          result[i].get_degree();
00709       }
00710 
00711    return result;
00712    }
00713 
00714 std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<gf2m> const& support, int n)
00715    {
00716    int i,j,t;
00717    gf2m a;
00718 
00719 
00720    std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = generator.msp_field;
00721 
00722    std::vector<polyn_gf2m> result;
00723    t = generator.get_degree();
00724 
00725    //g(z)=g_t+g_(t-1).z^(t-1)+......+g_1.z+g_0
00726    //f(z)=f_(t-1).z^(t-1)+......+f_1.z+f_0
00727 
00728    for(j=0;j<n;j++)
00729       {
00730       result.push_back(polyn_gf2m( t-1, msp_field));
00731 
00732       (*&result[j]).set_coef(t-1,1);
00733       for(i=t-2;i>=0;i--)
00734          {
00735          (*&result[j]).set_coef(i, (generator)[i+1]  ^
00736                                 msp_field->gf_mul(lex_to_gray(support[j]),result[j][i+1]));
00737          }
00738       a = ((generator)[0] ^ msp_field->gf_mul(lex_to_gray(support[j]),result[j][0]));
00739       for(i=0;i<t;i++)
00740          {
00741          (*&result[j]).set_coef(i, msp_field->gf_div(result[j][i],a));
00742          }
00743       }
00744    return result;
00745    }
00746 
00747 polyn_gf2m::polyn_gf2m(const secure_vector<byte>& encoded, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field )
00748    :msp_field(sp_field)
00749    {
00750    if(encoded.size() % 2)
00751       {
00752       throw Decoding_Error("encoded polynomial has odd length");
00753       }
00754    for(u32bit i = 0; i < encoded.size(); i += 2)
00755       {
00756       gf2m el = (encoded[i] << 8) | encoded[i + 1];
00757       coeff.push_back(el);
00758       }
00759    get_degree();
00760 
00761    }
00762 secure_vector<byte> polyn_gf2m::encode() const
00763    {
00764    secure_vector<byte> result;
00765 
00766    if(m_deg < 1)
00767       {
00768       result.push_back(0);
00769       result.push_back(0);
00770       return result;
00771       }
00772 
00773    u32bit len = m_deg+1;
00774    for(unsigned i = 0; i < len; i++)
00775       {
00776       // "big endian" encoding of the GF(2^m) elements
00777       result.push_back(coeff[i] >> 8);
00778       result.push_back(coeff[i]);
00779       }
00780    return result;
00781    }
00782 
00783 void polyn_gf2m::swap(polyn_gf2m& other)
00784    {
00785    std::swap(this->m_deg, other.m_deg);
00786    std::swap(this->msp_field, other.msp_field);
00787    std::swap(this->coeff, other.coeff);
00788    }
00789 
00790 bool polyn_gf2m::operator==(const polyn_gf2m & other) const
00791    {
00792    if(m_deg != other.m_deg || coeff != other.coeff)
00793       {
00794       return false;
00795       }
00796    return true;
00797    }
00798 
00799 }