13#include <botan/mceliece.h>
15#include <botan/ber_dec.h>
16#include <botan/der_enc.h>
18#include <botan/internal/bit_ops.h>
19#include <botan/internal/buffer_stuffer.h>
20#include <botan/internal/code_based_util.h>
21#include <botan/internal/loadstor.h>
22#include <botan/internal/mce_internal.h>
23#include <botan/internal/pk_ops_impl.h>
24#include <botan/internal/pk_options_impl.h>
25#include <botan/internal/polyn_gf2m.h>
34constexpr std::array<std::pair<size_t, size_t>, 6> MCE_SUPPORTED_PARAMS = {
35 {{1632, 33}, {2480, 45}, {2960, 57}, {3408, 67}, {4624, 95}, {6624, 115}}};
37bool mceliece_params_are_supported(
size_t code_length,
size_t t) {
38 for(
const auto& [supported_n, supported_t] : MCE_SUPPORTED_PARAMS) {
39 if(code_length == supported_n && t == supported_t) {
46uint32_t padding_mask(
size_t bit_count) {
47 const size_t used_bits = bit_count % 32;
51 return ~((
static_cast<uint32_t
>(1) << used_bits) - 1);
54void validate_public_matrix(
const std::vector<uint8_t>& public_matrix,
const McEliece_Params& params) {
55 if(public_matrix.size() != params.public_matrix_bytes) {
56 throw Decoding_Error(
"McEliece public matrix size does not match parameters");
59 const uint32_t unused_bits_mask = padding_mask(params.codimension);
60 if(unused_bits_mask == 0) {
64 const size_t row_bytes = params.words_per_matrix_row *
sizeof(uint32_t);
65 const size_t final_word_offset = (params.words_per_matrix_row - 1) *
sizeof(uint32_t);
66 for(
size_t row = 0; row != params.dimension; ++row) {
67 const uint8_t* row_ptr = public_matrix.data() + row * row_bytes;
69 if((final_word & unused_bits_mask) != 0) {
70 throw Decoding_Error(
"McEliece public matrix contains non-zero padding bits");
75void validate_polynomial(
const polyn_gf2m& polyn,
77 size_t min_coeff_count,
79 const std::shared_ptr<GF2m_Field> field = polyn.get_sp_field();
80 if(!field || field->get_extension_degree() != params.ext_deg) {
81 throw Decoding_Error(
"McEliece polynomial uses an inconsistent field");
84 if(polyn.get_coeff_count() < min_coeff_count) {
85 throw Decoding_Error(
"McEliece polynomial has too few coefficients");
88 const int degree = polyn.get_degree();
90 if(degree >= 0 &&
static_cast<size_t>(degree) > max_degree) {
94 const size_t field_cardinality =
static_cast<size_t>(1) << params.ext_deg;
95 for(
size_t i = 0; i != polyn.get_coeff_count(); ++i) {
96 if(polyn.get_coef(i) >= field_cardinality) {
97 throw Decoding_Error(
"McEliece polynomial coefficient is out of range");
102void validate_support_inverse(
const std::vector<gf2m>& inverse_support,
const McEliece_Params& params) {
103 if(inverse_support.size() != params.code_length) {
104 throw Decoding_Error(
"McEliece support size does not match code length");
107 std::vector<uint8_t> seen(params.code_length);
108 for(
const gf2m support_elem : inverse_support) {
109 if(support_elem >= params.code_length) {
112 if(seen[support_elem] != 0) {
115 seen[support_elem] = 1;
119void validate_parity_check_matrix(
const std::vector<uint32_t>& parity_check_matrix_coeffs,
121 if(parity_check_matrix_coeffs.size() != params.words_per_matrix_row * params.code_length) {
122 throw Decoding_Error(
"McEliece parity check matrix has wrong length");
125 const uint32_t unused_bits_mask = padding_mask(params.codimension);
126 if(unused_bits_mask == 0) {
130 for(
size_t row = 0; row != params.code_length; ++row) {
131 const uint32_t final_word =
132 parity_check_matrix_coeffs[row * params.words_per_matrix_row + params.words_per_matrix_row - 1];
133 if((final_word & unused_bits_mask) != 0) {
134 throw Decoding_Error(
"McEliece parity check matrix contains non-zero padding bits");
139void validate_private_components(
const polyn_gf2m& goppa_polyn,
140 const std::vector<uint32_t>& parity_check_matrix_coeffs,
141 const std::vector<polyn_gf2m>& square_root_matrix,
142 const std::vector<gf2m>& inverse_support,
143 const std::vector<uint8_t>& public_matrix,
145 validate_public_matrix(public_matrix, params);
147 if(goppa_polyn.get_degree() !=
static_cast<int>(params.t)) {
148 throw Decoding_Error(
"degree of decoded Goppa polynomial is incorrect");
150 validate_polynomial(goppa_polyn, params, params.t + 1, params.t);
151 if(goppa_polyn.get_lead_coef() != 1) {
155 if(square_root_matrix.size() != params.t / 2) {
156 throw Decoding_Error(
"McEliece square root matrix has wrong length");
158 for(
const auto& sqrt_polyn : square_root_matrix) {
159 validate_polynomial(sqrt_polyn, params, params.t, params.t - 1);
162 validate_support_inverse(inverse_support, params);
163 validate_parity_check_matrix(parity_check_matrix_coeffs, params);
169 if(!mceliece_params_are_supported(code_length, t)) {
173 const size_t ext_deg =
ceil_log2(code_length);
174 if(ext_deg < 2 || ext_deg > 15) {
175 throw Decoding_Error(
"McEliece code length out of supported range");
178 const size_t codimension = ext_deg * t;
179 if(codimension >= code_length) {
183 const size_t dimension = code_length - codimension;
185 const size_t public_matrix_bytes = dimension * words_per_matrix_row *
sizeof(uint32_t);
187 return McEliece_Params{code_length, t, ext_deg, codimension, dimension, words_per_matrix_row, public_matrix_bytes};
193 if(!mceliece_params_are_supported(code_length, t)) {
201McEliece_PrivateKey& McEliece_PrivateKey::operator=(const McEliece_PrivateKey&) = default;
202McEliece_PrivateKey& McEliece_PrivateKey::operator=(McEliece_PrivateKey&&) noexcept = default;
203McEliece_PrivateKey::~McEliece_PrivateKey() = default;
206 const std::vector<uint32_t>& parity_check_matrix_coeffs,
207 const std::vector<
polyn_gf2m>& square_root_matrix,
208 const std::vector<
gf2m>& inverse_support,
209 const std::vector<uint8_t>& public_matrix) {
210 const int goppa_degree = goppa_polyn.get_degree();
211 if(goppa_degree <= 0) {
216 validate_private_components(
217 goppa_polyn, parity_check_matrix_coeffs, square_root_matrix, inverse_support, public_matrix, params);
219 m_public = std::make_shared<const McEliece_PublicKeyInternal>(public_matrix, params.
t, params.
code_length);
220 m_private = std::make_shared<const McEliece_PrivateKeyInternal>(std::vector<polyn_gf2m>{goppa_polyn},
223 parity_check_matrix_coeffs,
235 const size_t codimension =
ceil_log2(m_code_length) * m_t;
236 return m_code_length - codimension;
243 rng.
randomize(plaintext.data(), plaintext.size());
246 if(
const uint32_t used = bits % 8) {
247 const uint8_t mask = (1 << used) - 1;
248 plaintext[plaintext.size() - 1] &= mask;
256 validate_public_matrix(pub_matrix, params);
257 m_public = std::make_shared<const McEliece_PublicKeyInternal>(pub_matrix, t, the_code_length);
273 return m_public->message_word_bit_length();
277 return m_public->random_plaintext_element(rng);
287 validate_public_matrix(
m_public->public_matrix(), params);
295 return m_private->goppa_polyn();
299 return m_private->H_coeffs();
303 return m_private->Linv();
307 return m_private->sqrtmod();
311 return m_private->dimension();
315 return m_private->codimension();
327 std::vector<uint8_t> output;
354 throw Decoding_Error(
"Unexpected parameters for McEliece public key");
360 std::vector<uint8_t> public_matrix;
371 validate_public_matrix(public_matrix, params);
373 m_public = std::make_shared<const McEliece_PublicKeyInternal>(std::move(public_matrix), t, n);
386 for(
const auto& x : m_private->sqrtmod()) {
392 for(
const uint16_t Linv : m_private->Linv()) {
398 for(
const uint32_t coef : m_private->H_coeffs()) {
428 if(errors != errors_out || plaintext != plaintext_out) {
442 throw Decoding_Error(
"Unexpected parameters for McEliece private key");
447 std::vector<uint8_t> public_matrix;
455 validate_public_matrix(public_matrix, params);
457 const auto sp_field = std::make_shared<GF2m_Field>(params.
ext_deg);
458 std::vector<polyn_gf2m> g = {
polyn_gf2m(enc_g, sp_field)};
459 std::vector<polyn_gf2m> sqrtmod;
461 for(uint32_t i = 0; i < t / 2; i++) {
464 while(sqrt_enc.size() < (t * 2)) {
466 sqrt_enc.push_back(0);
467 sqrt_enc.push_back(0);
469 if(sqrt_enc.size() != t * 2) {
470 throw Decoding_Error(
"length of square root polynomial entry is too large");
477 if(enc_support.size() % 2 != 0) {
480 if(enc_support.size() / 2 != n) {
481 throw Decoding_Error(
"encoded support has length different from code length");
483 std::vector<gf2m> Linv;
484 for(uint32_t i = 0; i < n * 2; i += 2) {
485 const gf2m el = (enc_support[i] << 8) | enc_support[i + 1];
490 if(enc_H.size() % 4 != 0) {
491 throw Decoding_Error(
"encoded parity check matrix has length which is not a multiple of four");
494 throw Decoding_Error(
"encoded parity check matrix has wrong length");
497 std::vector<uint32_t> coeffs;
498 for(uint32_t i = 0; i < enc_H.size(); i += 4) {
499 coeffs.push_back(
make_uint32(enc_H[i], enc_H[i + 1], enc_H[i + 2], enc_H[i + 3]));
502 validate_private_components(g[0], coeffs, sqrtmod, Linv, public_matrix, params);
504 m_public = std::make_shared<const McEliece_PublicKeyInternal>(std::move(public_matrix), t, n);
505 m_private = std::make_shared<const McEliece_PrivateKeyInternal>(
506 std::move(g), std::move(sqrtmod), std::move(Linv), std::move(coeffs), params.
codimension, params.
dimension);
513 if(m_private->goppa_polyn_vec() != other.m_private->goppa_polyn_vec()) {
517 if(m_private->sqrtmod() != other.m_private->sqrtmod()) {
520 if(m_private->Linv() != other.m_private->Linv()) {
523 if(m_private->H_coeffs() != other.m_private->H_coeffs()) {
527 if(m_private->codimension() != other.m_private->codimension() ||
528 m_private->dimension() != other.m_private->dimension()) {
557 MCE_KEM_Encryptor(std::shared_ptr<const McEliece_PublicKeyInternal> key,
const PK_KEM_Options_Reader& options) :
558 KEM_Encryption_with_KDF(options,
PK_Ops::KemSharedKeyQuality::RequiresKDF), m_key(std::move(key)) {}
561 size_t raw_kem_shared_key_length()
const override {
562 const size_t err_sz = (m_key->code_length() + 7) / 8;
563 const size_t ptext_sz = (m_key->message_word_bit_length() + 7) / 8;
564 return ptext_sz + err_sz;
567 size_t encapsulated_key_length()
const override {
return (m_key->code_length() + 7) / 8; }
569 void raw_kem_encrypt(std::span<uint8_t> out_encapsulated_key,
570 std::span<uint8_t> raw_shared_key,
571 RandomNumberGenerator& rng)
override {
580 std::copy(ciphertext.begin(), ciphertext.end(), out_encapsulated_key.begin());
583 BufferStuffer bs(raw_shared_key);
584 bs.append(plaintext);
585 bs.append(error_mask);
588 std::shared_ptr<const McEliece_PublicKeyInternal> m_key;
593 MCE_KEM_Decryptor(std::shared_ptr<const McEliece_PrivateKeyInternal> key,
const PK_KEM_Options_Reader& options) :
597 size_t raw_kem_shared_key_length()
const override {
598 const size_t err_sz = (m_key->code_length() + 7) / 8;
599 const size_t ptext_sz = (m_key->message_word_bit_length() + 7) / 8;
600 return ptext_sz + err_sz;
603 size_t encapsulated_key_length()
const override {
return (m_key->code_length() + 7) / 8; }
605 void raw_kem_decrypt(std::span<uint8_t> out_shared_key, std::span<const uint8_t> encapsulated_key)
override {
608 mceliece_decrypt(plaintext, error_mask, encapsulated_key.data(), encapsulated_key.size(), *m_key);
612 BufferStuffer bs(out_shared_key);
613 bs.append(plaintext);
614 bs.append(error_mask);
617 std::shared_ptr<const McEliece_PrivateKeyInternal> m_key;
630 return std::make_unique<MCE_KEM_Encryptor>(
m_public, options);
638 return std::make_unique<MCE_KEM_Decryptor>(m_private, options);
#define BOTAN_ASSERT_NOMSG(expr)
bool parameters_are_empty() const
virtual OID object_identifier() const
void push_back(const BER_Object &obj)
BER_Decoder & decode(bool &out)
BER_Decoder & verify_end()
BER_Decoder start_sequence()
secure_vector< uint8_t > get_contents()
DER_Encoder & start_sequence()
DER_Encoder & encode(bool b)
secure_vector< uint8_t > private_key_bits() const override
const std::vector< polyn_gf2m > & get_sqrtmod() const
McEliece_PrivateKey(RandomNumberGenerator &rng, size_t code_length, size_t t)
std::unique_ptr< Public_Key > public_key() const override
size_t get_codimension() const
size_t get_dimension() const
std::unique_ptr< PK_Ops::KEM_Decryption > _create_kem_decryption_op(RandomNumberGenerator &rng, const PK_KEM_Options_Reader &options) const override
const polyn_gf2m & get_goppa_polyn() const
const std::vector< gf2m > & get_Linv() const
bool operator==(const McEliece_PrivateKey &other) const
const std::vector< uint32_t > & get_H_coeffs() const
bool check_key(RandomNumberGenerator &rng, bool strong) const override
secure_vector< uint8_t > random_plaintext_element(RandomNumberGenerator &rng) const
size_t message_word_bit_length() const
secure_vector< uint8_t > random_plaintext_element(RandomNumberGenerator &rng) const
size_t get_message_word_bit_length() const
std::shared_ptr< const McEliece_PublicKeyInternal > m_public
std::vector< uint8_t > raw_public_key_bits() const override
std::string algo_name() const override
std::vector< uint8_t > public_key_bits() const override
std::unique_ptr< PK_Ops::KEM_Encryption > _create_kem_encryption_op(const PK_KEM_Options_Reader &options) const override
std::unique_ptr< Private_Key > generate_another(RandomNumberGenerator &rng) const final
McEliece_PublicKey()=default
McEliece_PublicKey(const AlgorithmIdentifier &alg_id, std::span< const uint8_t > key_bits)
const std::vector< uint8_t > & get_public_matrix() const
bool check_key(RandomNumberGenerator &rng, bool strong) const override
size_t estimated_strength() const override
size_t get_code_length() const
bool operator==(const McEliece_PublicKey &other) const
AlgorithmIdentifier algorithm_identifier() const override
size_t key_length() const override
void randomize(std::span< uint8_t > output)
constexpr uint8_t get_byte(T input)
void mceliece_decrypt(secure_vector< uint8_t > &plaintext_out, secure_vector< uint8_t > &error_mask_out, const secure_vector< uint8_t > &ciphertext, const McEliece_PrivateKeyInternal &key)
constexpr uint32_t make_uint32(uint8_t i0, uint8_t i1, uint8_t i2, uint8_t i3)
constexpr uint8_t ceil_log2(T x)
McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator &rng, size_t ext_deg, size_t code_length, size_t t)
size_t mceliece_work_factor(size_t n, size_t t)
void require_software_provider(const OptionsT &options, std::string_view algo_name)
constexpr auto load_le(ParamTs &&... params)
void mceliece_encrypt(secure_vector< uint8_t > &ciphertext_out, secure_vector< uint8_t > &error_mask_out, const secure_vector< uint8_t > &plaintext, const McEliece_PublicKeyInternal &key, RandomNumberGenerator &rng)
std::vector< T, secure_allocator< T > > secure_vector
size_t bit_size_to_32bit_size(size_t bit_size)
McEliece_Params mceliece_validate_key_params(size_t code_length, size_t t)
McEliece_Params mceliece_validate_keygen_params(size_t code_length, size_t t)
size_t words_per_matrix_row