Botan  1.11.15
src/lib/pubkey/mce/code_based_key_gen.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/internal/code_based_key_gen.h>
00013 #include <botan/code_based_util.h>
00014 #include <botan/gf2m_rootfind_dcmp.h>
00015 #include <botan/internal/binary_matrix.h>
00016 #include <botan/loadstor.h>
00017 #include <botan/polyn_gf2m.h>
00018 
00019 namespace Botan {
00020 
00021 namespace {
00022 
00023 void randomize_support(u32bit n, std::vector<gf2m> & L, RandomNumberGenerator & rng)
00024    {
00025    unsigned int i, j;
00026    gf2m_small_m::gf2m tmp;
00027 
00028    for (i = 0; i < n; ++i)
00029       {
00030 
00031       gf2m_small_m::gf2m rnd;
00032       rng.randomize(reinterpret_cast<byte*>(&rnd), sizeof(rnd));
00033       j = rnd % n; // no rejection sampling, but for useful code-based parameters with n <= 13 this seem tolerable
00034 
00035       tmp = L[j];
00036       L[j] = L[i];
00037       L[i] = tmp;
00038       }
00039    }
00040 
00041 std::unique_ptr<binary_matrix> generate_R(std::vector<gf2m> &L, polyn_gf2m* g, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field, u32bit code_length, u32bit t )
00042    {
00043    //L- Support
00044    //t- Number of errors
00045    //n- Length of the Goppa code
00046    //m- The extension degree of the GF
00047    //g- The generator polynomial.
00048    gf2m_small_m::gf2m x,y;
00049    u32bit i,j,k,r,n;
00050    std::vector<int> Laux(code_length);
00051    n=code_length;
00052    r=t*sp_field->get_extension_degree();
00053 
00054    binary_matrix H(r, n) ;
00055 
00056    for(i=0;i< n;i++)
00057       {
00058       x = g->eval(lex_to_gray(L[i]));//evaluate the polynomial at the point L[i].
00059       x = sp_field->gf_inv(x);
00060       y = x;
00061       for(j=0;j<t;j++)
00062          {
00063          for(k=0;k<sp_field->get_extension_degree();k++)
00064             {
00065             if(y & (1<<k))
00066                {
00067                //the co-eff. are set in 2^0,...,2^11 ; 2^0,...,2^11 format along the rows/cols?
00068                H.set_coef_to_one(j*sp_field->get_extension_degree()+ k,i);
00069                }
00070             }
00071          y = sp_field->gf_mul(y,lex_to_gray(L[i]));
00072          }
00073       }//The H matrix is fed.
00074 
00075    secure_vector<int> perm = H.row_reduced_echelon_form();
00076    if (perm.size() == 0)
00077       {
00078       // result still is NULL
00079       throw Invalid_State("could not bring matrix in row reduced echelon form");
00080       }
00081 
00082    std::unique_ptr<binary_matrix> result(new binary_matrix(n-r,r)) ;
00083    for (i = 0; i < (*result).m_rown; ++i)
00084       {
00085       for (j = 0; j < (*result).m_coln; ++j)
00086          {
00087          if (H.coef(j,perm[i]))
00088             {
00089             result->toggle_coeff(i,j);
00090             }
00091          }
00092       }
00093    for (i = 0; i < code_length; ++i)
00094       {
00095       Laux[i] = L[perm[i]];
00096       }
00097    for (i = 0; i < code_length; ++i)
00098       {
00099       L[i] = Laux[i];
00100       }
00101    return result;
00102    }
00103 }
00104 
00105 McEliece_PrivateKey generate_mceliece_key( RandomNumberGenerator & rng, u32bit ext_deg, u32bit code_length, u32bit t)
00106    {
00107    u32bit i, j, k, l;
00108    std::unique_ptr<binary_matrix> R;
00109 
00110    u32bit codimension = t * ext_deg;
00111    if(code_length <= codimension)
00112       {
00113       throw Invalid_Argument("invalid McEliece parameters");
00114       }
00115    std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field ( new Gf2m_Field(ext_deg ));
00116 
00117    //pick the support.........
00118    std::vector<gf2m> L(code_length);
00119 
00120    for(i=0;i<code_length;i++)
00121       {
00122       L[i]=i;
00123       }
00124    randomize_support(code_length,L,rng);
00125    polyn_gf2m g(sp_field); // create as zero
00126    bool success = false;
00127    do
00128       {
00129       // create a random irreducible polynomial
00130       g = polyn_gf2m (t, rng, sp_field);
00131 
00132       try{
00133       R = generate_R(L,&g, sp_field, code_length, t);
00134       success = true;
00135       }
00136       catch(const Invalid_State &)
00137          {
00138          }
00139       } while (!success);
00140 
00141    std::vector<polyn_gf2m> sqrtmod = polyn_gf2m::sqrt_mod_init( g);
00142    std::vector<polyn_gf2m> F = syndrome_init(g, L, code_length);
00143 
00144    // Each F[i] is the (precomputed) syndrome of the error vector with
00145    // a single '1' in i-th position.
00146    // We do not store the F[i] as polynomials of degree t , but
00147    // as binary vectors of length ext_deg * t (this will
00148    // speed up the syndrome computation)
00149    //
00150    //
00151    std::vector<u32bit> H(bit_size_to_32bit_size(codimension) * code_length );
00152    u32bit* sk = &H[0];
00153    for (i = 0; i < code_length; ++i)
00154       {
00155       for (l = 0; l < t; ++l)
00156          {
00157          k = (l * ext_deg) / 32;
00158          j = (l * ext_deg) % 32;
00159          sk[k] ^= F[i].get_coef( l) << j;
00160          if (j + ext_deg > 32)
00161             {
00162             sk[k + 1] ^= F[i].get_coef( l) >> (32 - j);
00163             }
00164          }
00165       sk += bit_size_to_32bit_size(codimension);
00166       }
00167 
00168    // We need the support L for decoding (decryption). In fact the
00169    // inverse is needed
00170 
00171    std::vector<gf2m> Linv(code_length) ;
00172    for (i = 0; i < code_length; ++i)
00173       {
00174       Linv[L[i]] = i;
00175       }
00176    std::vector<byte> pubmat (R->m_elem.size() * 4);
00177    for(i = 0; i < R->m_elem.size(); i++)
00178       {
00179       store_le(R->m_elem[i], &pubmat[i*4]);
00180       }
00181 
00182    return McEliece_PrivateKey(g, H, sqrtmod, Linv, pubmat);
00183    }
00184 
00185 }