13 #include <botan/mceliece.h>
14 #include <botan/internal/mce_internal.h>
15 #include <botan/internal/code_based_util.h>
16 #include <botan/loadstor.h>
27 void row_xor(uint32_t a, uint32_t b);
28 secure_vector<int> row_reduced_echelon_form();
33 uint32_t coef(uint32_t i, uint32_t j)
38 void set_coef_to_one(uint32_t i, uint32_t j)
40 m_elem[(i) *
m_rwdcnt + (j) / 32] |= (
static_cast<uint32_t
>(1) << ((j) % 32)) ;
43 void toggle_coeff(uint32_t i, uint32_t j)
45 m_elem[(i) *
m_rwdcnt + (j) / 32] ^= (
static_cast<uint32_t
>(1) << ((j) % 32)) ;
55 binary_matrix::binary_matrix (uint32_t rown, uint32_t coln)
63 void binary_matrix::row_xor(uint32_t a, uint32_t b)
73 secure_vector<int> binary_matrix::row_reduced_echelon_form()
75 uint32_t i, failcnt, findrow,
max=
m_coln - 1;
77 secure_vector<int> perm(
m_coln);
84 for(i=0;i<
m_rown;i++,max--)
87 for(uint32_t j=i;j<
m_rown;j++)
100 perm[m_coln - m_rown - 1 - failcnt] =
max;
113 for(uint32_t j=i+1;j<
m_rown;j++)
121 for(
int j=i-1;j>=0;j--)
133 void randomize_support(std::vector<gf2m>& L, RandomNumberGenerator& rng)
135 for(uint32_t i = 0; i != L.size(); ++i)
140 std::swap(L[i], L[rnd % L.size()]);
144 std::unique_ptr<binary_matrix> generate_R(std::vector<gf2m> &L, polyn_gf2m* g, std::shared_ptr<GF2m_Field> sp_field, uint32_t
code_length, uint32_t t )
153 std::vector<int> Laux(code_length);
155 r=t*sp_field->get_extension_degree();
157 binary_matrix H(r, n) ;
162 x = sp_field->gf_inv(x);
166 for(k=0;k<sp_field->get_extension_degree();k++)
171 H.set_coef_to_one(j*sp_field->get_extension_degree()+ k,i);
178 secure_vector<int> perm = H.row_reduced_echelon_form();
179 if (perm.size() == 0)
182 throw Invalid_State(
"could not bring matrix in row reduced echelon form");
185 std::unique_ptr<binary_matrix> result(
new binary_matrix(n-r,r)) ;
186 for (i = 0; i < (*result).m_rown; ++i)
188 for (j = 0; j < (*result).m_coln; ++j)
190 if (H.coef(j,perm[i]))
192 result->toggle_coeff(i,j);
198 Laux[i] = L[perm[i]];
211 std::unique_ptr<binary_matrix> R;
213 uint32_t codimension = t * ext_deg;
214 if(code_length <= codimension)
218 std::shared_ptr<GF2m_Field> sp_field (
new GF2m_Field(ext_deg ));
221 std::vector<gf2m> L(code_length);
227 randomize_support(L, rng);
229 bool success =
false;
236 R = generate_R(L,&g, sp_field, code_length, t);
245 std::vector<polyn_gf2m> F =
syndrome_init(g, L, code_length);
255 uint32_t* sk = H.data();
258 for (l = 0; l < t; ++l)
260 k = (l * ext_deg) / 32;
261 j = (l * ext_deg) % 32;
262 sk[k] ^=
static_cast<uint32_t
>(F[i].get_coef(l)) << j;
263 if (j + ext_deg > 32)
265 sk[k + 1] ^= F[i].get_coef( l) >> (32 - j);
274 std::vector<gf2m> Linv(code_length) ;
279 std::vector<uint8_t> pubmat (R->m_elem.size() * 4);
280 for(i = 0; i < R->m_elem.size(); i++)
282 store_le(R->m_elem[i], &pubmat[i*4]);
uint32_t bit_size_to_32bit_size(uint32_t bit_size)
gf2m lex_to_gray(gf2m lex)
McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator &rng, uint32_t ext_deg, uint32_t code_length, uint32_t t)
static std::vector< polyn_gf2m > sqrt_mod_init(const polyn_gf2m &g)
std::vector< uint32_t > m_elem
std::vector< polyn_gf2m > syndrome_init(polyn_gf2m const &generator, std::vector< gf2m > const &support, int n)
gf2m random_gf2m(RandomNumberGenerator &rng)
void store_le(uint16_t in, uint8_t out[2])