Botan
1.11.15
|
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 }