Botan 3.14.1
Crypto and TLS for C&
cmce_keys_internal.cpp
Go to the documentation of this file.
1/*
2 * Classic McEliece key generation with Internal Private and Public Key classes
3 * (C) 2023 Jack Lloyd
4 * 2023,2024 Fabian Albert, Amos Treiber - Rohde & Schwarz Cybersecurity
5 *
6 * Botan is released under the Simplified BSD License (see license.txt)
7 **/
8
9#include <botan/internal/cmce_keys_internal.h>
10
11#include <botan/internal/buffer_slicer.h>
12#include <botan/internal/concat_util.h>
13
14namespace Botan {
15
16namespace {
17
18/**
19 * @brief Try to generate a Classic McEliece keypair for a given seed.
20 *
21 * @param[out] out_next_seed The next seed to use for key generation, if this iteration fails
22 * @param params Classic McEliece parameters
23 * @param seed The seed to used for this key generation iteration
24 * @return a keypair on success, std::nullopt otherwise
25 */
26std::optional<Classic_McEliece_KeyPair_Internal> try_generate_keypair(std::span<uint8_t> out_next_seed,
27 const Classic_McEliece_Parameters& params,
28 CmceKeyGenSeed seed) {
29 BOTAN_ASSERT_EQUAL(seed.size(), 32, "Valid seed length");
30 BOTAN_ASSERT_EQUAL(out_next_seed.size(), 32, "Valid output seed length");
31
32 auto big_e_xof = params.prg(seed);
33
34 auto s = big_e_xof->output<CmceRejectionSeed>(params.n() / 8);
35 const auto ordering_bits = big_e_xof->output<CmceOrderingBits>((params.sigma2() * params.q()) / 8);
36 const auto irreducible_bits = big_e_xof->output<CmceIrreducibleBits>((params.sigma1() * params.t()) / 8);
37 big_e_xof->output(out_next_seed);
38
39 // Field-ordering generation - Classic McEliece ISO 8.2
40 auto field_ordering = Classic_McEliece_Field_Ordering::create_field_ordering(params, ordering_bits);
41 if(!field_ordering) {
42 return std::nullopt;
43 }
44
45 // Irreducible-polynomial generation - Classic McEliece ISO 8.1
46 auto g = params.poly_ring().compute_minimal_polynomial(irreducible_bits);
47 if(!g) {
48 return std::nullopt;
49 }
50
51 // Matrix generation for Goppa codes - Classic McEliece ISO 7.2
52 auto pk_matrix_and_pivots =
53 Classic_McEliece_Matrix::create_matrix_and_apply_pivots(params, field_ordering.value(), g.value());
54 if(!pk_matrix_and_pivots) {
55 return std::nullopt;
56 }
57 auto& [pk_matrix, pivots] = pk_matrix_and_pivots.value();
58
59 // Key generation was successful - Create and return keys
61 .private_key = std::make_shared<Classic_McEliece_PrivateKeyInternal>(
62 params, std::move(seed), pivots, std::move(g.value()), std::move(field_ordering.value()), std::move(s)),
63 .public_key = std::make_shared<Classic_McEliece_PublicKeyInternal>(params, std::move(pk_matrix))};
64}
65
66} // namespace
67
69 const Classic_McEliece_Parameters& params, std::span<const uint8_t> sk_bytes) {
70 if(sk_bytes.size() != params.sk_size_bytes()) {
71 throw Decoding_Error("Invalid Classic McEliece private key length");
72 }
73 BufferSlicer sk_slicer(sk_bytes);
74
75 auto delta = sk_slicer.copy<CmceKeyGenSeed>(params.seed_len());
76 auto c = CmceColumnSelection(sk_slicer.take(params.sk_c_bytes()));
77 // c selects exactly the 32 pivot columns of the semi-systematic form
78 if(CT::driveby_unpoison(c.hamming_weight() != 32)) {
79 throw Decoding_Error("Invalid Classic McEliece private key column selection");
80 }
81 auto g = Classic_McEliece_Minimal_Polynomial::from_bytes(sk_slicer.take(params.sk_poly_g_bytes()), params.poly_f());
83 params, secure_bitvector(sk_slicer.take(params.sk_alpha_control_bytes())));
84 auto s = sk_slicer.copy<CmceRejectionSeed>(params.sk_s_bytes());
85 BOTAN_ASSERT_NOMSG(sk_slicer.empty());
86
88 params, std::move(delta), std::move(c), std::move(g), std::move(field_ordering), std::move(s));
89}
90
92 const auto control_bits = m_field_ordering.alphas_control_bits();
93
94 /* NIST Impl. guide 6.1 Control-Bit Gen:
95 * As low-cost protection against faults in the control-bit computation, implementors are advised
96 * to check after the computation that applying the Benes network produces pi, and to
97 * restart key generation if this test fails; applying the Benes network is very fast.
98 *
99 * Here, we just assert that applying the Benes network produces pi.
100 */
102 .ct_is_equal(m_field_ordering)
103 .as_bool(),
104 "Control Bit Computation Check");
105
106 return concat(m_delta.get(), m_c.get().to_bytes(), m_g.serialize(), control_bits.to_bytes(), m_s);
107}
108
110 auto prg = m_params.prg(m_delta);
111
112 const auto s = prg->output<CmceRejectionSeed>(m_params.n() / 8);
113 const auto ordering_bits = prg->output<CmceOrderingBits>((m_params.sigma2() * m_params.q()) / 8);
114 const auto irreducible_bits = prg->output<CmceIrreducibleBits>((m_params.sigma1() * m_params.t()) / 8);
115
116 // Recomputing s as hash of delta
117 auto ret = CT::Mask<size_t>::expand(CT::is_equal<uint8_t>(s.data(), m_s.data(), m_params.n() / 8));
118
119 // Checking weight of c
120 ret &= CT::Mask<size_t>::is_equal(c().hamming_weight(), 32);
121
122 if(auto g = m_params.poly_ring().compute_minimal_polynomial(irreducible_bits)) {
123 for(size_t i = 0; i < g->degree() - 1; ++i) {
124 ret &= CT::Mask<size_t>::expand(GF_Mask::is_equal(g->coef_at(i), m_g.coef_at(i)).elem_mask());
125 }
126 } else {
128 }
129
130 // Check alpha control bits
131 if(auto field_ord_from_seed = Classic_McEliece_Field_Ordering::create_field_ordering(m_params, ordering_bits)) {
132 field_ord_from_seed->permute_with_pivots(m_params, c());
133 ret &= CT::Mask<size_t>::expand(field_ord_from_seed->ct_is_equal(field_ordering()));
134 } else {
136 }
137
138 return ret.as_bool();
139}
140
141std::shared_ptr<Classic_McEliece_PublicKeyInternal> Classic_McEliece_PublicKeyInternal::create_from_private_key(
143 auto pk_matrix_and_pivot = Classic_McEliece_Matrix::create_matrix(sk.params(), sk.field_ordering(), sk.g());
144 if(!pk_matrix_and_pivot.has_value()) {
145 throw Decoding_Error("Cannot create public key from private key. Private key is invalid.");
146 }
147 auto& [pk_matrix, pivot] = pk_matrix_and_pivot.value();
148
149 // There should not be a pivot of any other form. Otherwise the gauss
150 // algorithm failed effectively.
151 if(!CT::driveby_unpoison(pivot.equals(bitvector{0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00}))) {
152 throw Decoding_Error("Cannot create public key from private key. Private key is invalid.");
153 }
154
155 return std::make_shared<Classic_McEliece_PublicKeyInternal>(sk.params(), std::move(pk_matrix));
156}
157
160 BOTAN_ASSERT_EQUAL(seed.size(), params.seed_len(), "Valid seed length");
161
162 CmceKeyGenSeed next_seed(seed.size());
163 CmceKeyGenSeed current_seed(seed.begin(), seed.end());
164
165 while(true) {
166 if(auto keypair = try_generate_keypair(next_seed, params, std::move(current_seed))) {
167 return keypair.value();
168 }
169 current_seed = next_seed;
170 }
171}
172
173} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_ASSERT_EQUAL(expr1, expr2, assertion_made)
Definition assert.h:95
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:69
auto copy(const size_t count)
std::span< const uint8_t > take(const size_t count)
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:397
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:447
static constexpr Mask< T > cleared()
Definition ct_utils.h:392
static std::optional< Classic_McEliece_Field_Ordering > create_field_ordering(const Classic_McEliece_Parameters &params, StrongSpan< const CmceOrderingBits > random_bits)
Creates a field ordering from a random bit sequence. Corresponds to the algorithm described in Classi...
static Classic_McEliece_Field_Ordering create_from_control_bits(const Classic_McEliece_Parameters &params, const secure_bitvector &control_bits)
Create the field ordering from the control bits of a benes network.
static std::optional< std::pair< Classic_McEliece_Matrix, CmceColumnSelection > > create_matrix(const Classic_McEliece_Parameters &params, const Classic_McEliece_Field_Ordering &field_ordering, const Classic_McEliece_Minimal_Polynomial &g)
Create the matrix H for a Classic McEliece instance given its parameters, field ordering and minimal ...
static std::optional< std::pair< Classic_McEliece_Matrix, CmceColumnSelection > > create_matrix_and_apply_pivots(const Classic_McEliece_Parameters &params, Classic_McEliece_Field_Ordering &field_ordering, const Classic_McEliece_Minimal_Polynomial &g)
Create the matrix H for a Classic McEliece instance given its parameters, field ordering and minimal ...
static Classic_McEliece_Minimal_Polynomial from_bytes(std::span< const uint8_t > bytes, CmceGfMod poly_f)
Create a polynomial from bytes according to ISO Section 9.2.9.
static constexpr size_t seed_len()
The byte length of the seed delta. See ISO 9.2.12.
Representation of a Classic McEliece private key.
const CmceRejectionSeed & s() const
The seed s for implicit rejection on decryption failure.
const Classic_McEliece_Field_Ordering & field_ordering() const
The field ordering alpha.
bool check_key() const
Checks the private key for consistency with the first component delta, i.e., recomputes s as a hash o...
secure_vector< uint8_t > serialize() const
Serializes the Classic McEliece private key as defined in Classic McEliece ISO Section 9....
const CmceKeyGenSeed & delta() const
The seed delta that was used to create the private key.
const Classic_McEliece_Parameters & params() const
The Classic McEliece parameters.
static Classic_McEliece_PrivateKeyInternal from_bytes(const Classic_McEliece_Parameters &params, std::span< const uint8_t > sk_bytes)
Parses a Classic McEliece private key from a byte sequence.
Classic_McEliece_PrivateKeyInternal(const Classic_McEliece_Parameters &params, CmceKeyGenSeed delta, CmceColumnSelection c, Classic_McEliece_Minimal_Polynomial g, Classic_McEliece_Field_Ordering alpha, CmceRejectionSeed s)
Construct a Classic McEliece private key.
const CmceColumnSelection & c() const
The column selection pivot vector c as defined in Classic McEliece ISO Section 9.2....
const Classic_McEliece_Minimal_Polynomial & g() const
The minimal polynomial g.
static std::shared_ptr< Classic_McEliece_PublicKeyInternal > create_from_private_key(const Classic_McEliece_PrivateKeyInternal &sk)
Create a Classic McEliece public key from a private key.
static GF_Mask is_equal(Classic_McEliece_GF a, Classic_McEliece_GF b)
Definition cmce_gf.h:169
decltype(auto) begin() noexcept(noexcept(this->m_span.begin()))
decltype(auto) end() noexcept(noexcept(this->m_span.end()))
decltype(auto) size() const noexcept(noexcept(this->m_span.size()))
constexpr decltype(auto) driveby_unpoison(T &&v)
Definition ct_utils.h:243
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
Definition ct_utils.h:803
Strong< secure_vector< uint8_t >, struct CmceOrderingBits_ > CmceOrderingBits
Definition cmce_types.h:37
bitvector_base< secure_allocator > secure_bitvector
Definition bitvector.h:1418
Strong< secure_vector< uint8_t >, struct CmceIrreducibleBits_ > CmceIrreducibleBits
Definition cmce_types.h:40
bitvector_base< std::allocator > bitvector
Definition bitvector.h:1419
Strong< secure_bitvector, struct CmceColumnSelection_ > CmceColumnSelection
Represents c of private key.
Definition cmce_types.h:46
constexpr auto concat(Rs &&... ranges)
Definition concat_util.h:95
Strong< secure_vector< uint8_t >, struct CmceKeyGenSeed_ > CmceKeyGenSeed
Represents a delta (can be altered; final value stored in private key).
Definition cmce_types.h:34
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
Strong< secure_vector< uint8_t >, struct CmceRejectionSeed_ > CmceRejectionSeed
Represents s of private key.
Definition cmce_types.h:43
Representation of a Classic McEliece key pair.
static Classic_McEliece_KeyPair_Internal generate(const Classic_McEliece_Parameters &params, StrongSpan< const CmceInitialSeed > seed)
Generate a Classic McEliece key pair using the algorithm described in Classic McEliece ISO Section 8....