13#include <botan/mceliece.h>
14#include <botan/internal/mce_internal.h>
15#include <botan/internal/code_based_util.h>
16#include <botan/internal/loadstor.h>
17#include <botan/internal/polyn_gf2m.h>
23class binary_matrix
final
26 binary_matrix(
size_t m_rown,
size_t m_coln);
28 void row_xor(
size_t a,
size_t b);
29 secure_vector<size_t> row_reduced_echelon_form();
34 uint32_t coef(
size_t i,
size_t j)
36 return (m_elem[(i) * m_rwdcnt + (j) / 32] >> (j % 32)) & 1;
39 void set_coef_to_one(
size_t i,
size_t j)
41 m_elem[(i) * m_rwdcnt + (j) / 32] |= (
static_cast<uint32_t
>(1) << ((j) % 32)) ;
44 void toggle_coeff(
size_t i,
size_t j)
46 m_elem[(i) * m_rwdcnt + (j) / 32] ^= (
static_cast<uint32_t
>(1) << ((j) % 32)) ;
49 size_t rows()
const {
return m_rown; }
51 size_t columns()
const {
return m_coln; }
53 const std::vector<uint32_t>& elem()
const {
return m_elem; }
59 std::vector<uint32_t> m_elem;
62binary_matrix::binary_matrix(
size_t rown,
size_t coln)
66 m_rwdcnt = 1 + ((m_coln - 1) / 32);
67 m_elem = std::vector<uint32_t>(m_rown * m_rwdcnt);
70void binary_matrix::row_xor(
size_t a,
size_t b)
72 for(
size_t i = 0; i != m_rwdcnt; i++)
74 m_elem[a*m_rwdcnt+i] ^= m_elem[b*m_rwdcnt+i];
79secure_vector<size_t> binary_matrix::row_reduced_echelon_form()
81 secure_vector<size_t> perm(m_coln);
82 for(
size_t i = 0; i != m_coln; i++)
89 size_t max = m_coln - 1;
90 for(
size_t i = 0; i != m_rown; i++, max--)
92 bool found_row =
false;
94 for(
size_t j = i; !found_row && j != m_rown; j++)
110 perm[m_coln - m_rown - 1 - failcnt] =
static_cast<int>(max);
120 perm[i+m_coln - m_rown] = max;
121 for(
size_t j=i+1;j<m_rown;j++)
130 for(
size_t j = i; j != 0; --j)
142void randomize_support(std::vector<gf2m>& L, RandomNumberGenerator& rng)
144 for(
size_t i = 0; i != L.size(); ++i)
149 std::swap(L[i], L[rnd % L.size()]);
153std::unique_ptr<binary_matrix> generate_R(std::vector<gf2m> &L, polyn_gf2m* g,
const GF2m_Field& sp_field,
size_t code_length,
size_t t)
161 const size_t r = t * sp_field.get_extension_degree();
163 binary_matrix H(r, code_length);
165 for(
size_t i = 0; i != code_length; i++)
168 x = sp_field.gf_inv(x);
170 for(
size_t j=0;j<t;j++)
172 for(
size_t k=0;k<sp_field.get_extension_degree();k++)
177 H.set_coef_to_one(j*sp_field.get_extension_degree()+ k,i);
184 secure_vector<size_t> perm = H.row_reduced_echelon_form();
187 throw Invalid_State(
"McEliece keygen failed - could not bring matrix to row reduced echelon form");
190 auto result = std::make_unique<binary_matrix>(code_length - r, r);
191 for(
size_t i = 0; i < result->rows(); ++i)
193 for(
size_t j = 0; j < result->columns(); ++j)
195 if(H.coef(j, perm[i]))
197 result->toggle_coeff(i,j);
202 std::vector<gf2m> Laux(code_length);
203 for(
size_t i = 0; i < code_length; ++i)
205 Laux[i] = L[perm[i]];
208 for(
size_t i = 0; i < code_length; ++i)
218 const size_t codimension = t * ext_deg;
220 if(code_length <= codimension)
225 auto sp_field = std::make_shared<GF2m_Field>(ext_deg);
228 std::vector<gf2m> L(code_length);
230 for(
size_t i = 0; i != L.size(); i++)
232 L[i] =
static_cast<gf2m>(i);
234 randomize_support(L, rng);
237 bool success =
false;
238 std::unique_ptr<binary_matrix> R;
247 R = generate_R(L, &g, *sp_field, code_length, t);
256 std::vector<polyn_gf2m> F =
syndrome_init(g, L,
static_cast<int>(code_length));
265 uint32_t* sk = H.data();
266 for(
size_t i = 0; i < code_length; ++i)
268 for(
size_t l = 0; l < t; ++l)
270 const size_t k = (l * ext_deg) / 32;
271 const uint8_t j = (l * ext_deg) % 32;
272 sk[k] ^=
static_cast<uint32_t
>(F[i].get_coef(l)) << j;
275 sk[k + 1] ^= F[i].get_coef(l) >> (32 - j);
284 std::vector<gf2m> Linv(code_length) ;
285 for(
size_t i = 0; i != Linv.size(); ++i)
287 Linv[L[i]] =
static_cast<gf2m>(i);
289 std::vector<uint8_t> pubmat(R->elem().size() * 4);
290 for(
size_t i = 0; i < R->elem().size(); i++)
292 store_le(R->elem()[i], &pubmat[i*4]);
static std::vector< polyn_gf2m > sqrt_mod_init(const polyn_gf2m &g)
int(* final)(unsigned char *, CTX *)
constexpr void store_le(uint16_t in, uint8_t out[2])
gf2m lex_to_gray(gf2m lex)
std::vector< polyn_gf2m > syndrome_init(polyn_gf2m const &generator, std::vector< gf2m > const &support, int n)
McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator &rng, size_t ext_deg, size_t code_length, size_t t)
gf2m random_gf2m(RandomNumberGenerator &rng)
size_t bit_size_to_32bit_size(size_t bit_size)