Botan 3.5.0
Crypto and TLS for C&
mceliece_key.cpp
Go to the documentation of this file.
1/*
2 * (C) Copyright Projet SECRET, INRIA, Rocquencourt
3 * (C) Bhaskar Biswas and Nicolas Sendrier
4 *
5 * (C) 2014 cryptosource GmbH
6 * (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
7 * (C) 2015 Jack Lloyd
8 *
9 * Botan is released under the Simplified BSD License (see license.txt)
10 *
11 */
12
13#include <botan/mceliece.h>
14
15#include <botan/ber_dec.h>
16#include <botan/der_enc.h>
17#include <botan/rng.h>
18#include <botan/internal/bit_ops.h>
19#include <botan/internal/code_based_util.h>
20#include <botan/internal/loadstor.h>
21#include <botan/internal/mce_internal.h>
22#include <botan/internal/pk_ops_impl.h>
23#include <botan/internal/polyn_gf2m.h>
24#include <botan/internal/stl_util.h>
25
26namespace Botan {
27
28McEliece_PrivateKey::McEliece_PrivateKey(const McEliece_PrivateKey&) = default;
29McEliece_PrivateKey::McEliece_PrivateKey(McEliece_PrivateKey&&) noexcept = default;
30McEliece_PrivateKey& McEliece_PrivateKey::operator=(const McEliece_PrivateKey&) = default;
31McEliece_PrivateKey& McEliece_PrivateKey::operator=(McEliece_PrivateKey&&) noexcept = default;
32McEliece_PrivateKey::~McEliece_PrivateKey() = default;
33
35 const std::vector<uint32_t>& parity_check_matrix_coeffs,
36 const std::vector<polyn_gf2m>& square_root_matrix,
37 const std::vector<gf2m>& inverse_support,
38 const std::vector<uint8_t>& public_matrix) :
39 McEliece_PublicKey(public_matrix, goppa_polyn.get_degree(), inverse_support.size()),
40 m_g{goppa_polyn},
41 m_sqrtmod(square_root_matrix),
42 m_Linv(inverse_support),
43 m_coeffs(parity_check_matrix_coeffs),
44 m_codimension(static_cast<size_t>(ceil_log2(inverse_support.size())) * goppa_polyn.get_degree()),
45 m_dimension(inverse_support.size() - m_codimension) {}
46
48 uint32_t ext_deg = ceil_log2(code_length);
49 *this = generate_mceliece_key(rng, ext_deg, code_length, t);
50}
51
53 return m_g[0];
54}
55
57 size_t codimension = ceil_log2(m_code_length) * m_t;
58 return m_code_length - codimension;
59}
60
62 const size_t bits = get_message_word_bit_length();
63
64 secure_vector<uint8_t> plaintext((bits + 7) / 8);
65 rng.randomize(plaintext.data(), plaintext.size());
66
67 // unset unused bits in the last plaintext byte
68 if(uint32_t used = bits % 8) {
69 const uint8_t mask = (1 << used) - 1;
70 plaintext[plaintext.size() - 1] &= mask;
71 }
72
73 return plaintext;
74}
75
79
80std::vector<uint8_t> McEliece_PublicKey::raw_public_key_bits() const {
81 return m_public_matrix;
82}
83
84std::vector<uint8_t> McEliece_PublicKey::public_key_bits() const {
85 std::vector<uint8_t> output;
86 DER_Encoder(output)
89 .encode(static_cast<size_t>(get_code_length()))
90 .encode(static_cast<size_t>(get_t()))
91 .end_cons()
93 .end_cons();
94 return output;
95}
96
98 return m_code_length;
99}
100
104
105McEliece_PublicKey::McEliece_PublicKey(std::span<const uint8_t> key_bits) {
106 BER_Decoder dec(key_bits);
107 size_t n;
108 size_t t;
109 dec.start_sequence()
111 .decode(n)
112 .decode(t)
113 .end_cons()
115 .end_cons();
116 m_t = t;
117 m_code_length = n;
118}
119
121 DER_Encoder enc;
122 enc.start_sequence()
124 .encode(static_cast<size_t>(get_code_length()))
125 .encode(static_cast<size_t>(get_t()))
126 .end_cons()
128 .encode(m_g[0].encode(), ASN1_Type::OctetString); // g as octet string
129 enc.start_sequence();
130 for(size_t i = 0; i < m_sqrtmod.size(); i++) {
131 enc.encode(m_sqrtmod[i].encode(), ASN1_Type::OctetString);
132 }
133 enc.end_cons();
134 secure_vector<uint8_t> enc_support;
135
136 for(uint16_t Linv : m_Linv) {
137 enc_support.push_back(get_byte<0>(Linv));
138 enc_support.push_back(get_byte<1>(Linv));
139 }
140 enc.encode(enc_support, ASN1_Type::OctetString);
142 for(uint32_t coef : m_coeffs) {
143 enc_H.push_back(get_byte<0>(coef));
144 enc_H.push_back(get_byte<1>(coef));
145 enc_H.push_back(get_byte<2>(coef));
146 enc_H.push_back(get_byte<3>(coef));
147 }
148 enc.encode(enc_H, ASN1_Type::OctetString);
149 enc.end_cons();
150 return enc.get_contents();
151}
152
153bool McEliece_PrivateKey::check_key(RandomNumberGenerator& rng, bool /*unused*/) const {
154 const secure_vector<uint8_t> plaintext = this->random_plaintext_element(rng);
155
156 secure_vector<uint8_t> ciphertext;
158 mceliece_encrypt(ciphertext, errors, plaintext, *this, rng);
159
160 secure_vector<uint8_t> plaintext_out;
161 secure_vector<uint8_t> errors_out;
162 mceliece_decrypt(plaintext_out, errors_out, ciphertext, *this);
163
164 if(errors != errors_out || plaintext != plaintext_out) {
165 return false;
166 }
167
168 return true;
169}
170
171McEliece_PrivateKey::McEliece_PrivateKey(std::span<const uint8_t> key_bits) {
172 size_t n, t;
174 BER_Decoder dec_base(key_bits);
175 BER_Decoder dec = dec_base.start_sequence()
177 .decode(n)
178 .decode(t)
179 .end_cons()
182
183 if(t == 0 || n == 0) {
184 throw Decoding_Error("invalid McEliece parameters");
185 }
186
187 uint32_t ext_deg = ceil_log2(n);
188 m_code_length = n;
189 m_t = t;
190 m_codimension = (ext_deg * t);
191 m_dimension = (n - m_codimension);
192
193 auto sp_field = std::make_shared<GF2m_Field>(ext_deg);
194 m_g = {polyn_gf2m(enc_g, sp_field)};
195 if(m_g[0].get_degree() != static_cast<int>(t)) {
196 throw Decoding_Error("degree of decoded Goppa polynomial is incorrect");
197 }
198 BER_Decoder dec2 = dec.start_sequence();
199 for(uint32_t i = 0; i < t / 2; i++) {
200 secure_vector<uint8_t> sqrt_enc;
201 dec2.decode(sqrt_enc, ASN1_Type::OctetString);
202 while(sqrt_enc.size() < (t * 2)) {
203 // ensure that the length is always t
204 sqrt_enc.push_back(0);
205 sqrt_enc.push_back(0);
206 }
207 if(sqrt_enc.size() != t * 2) {
208 throw Decoding_Error("length of square root polynomial entry is too large");
209 }
210 m_sqrtmod.push_back(polyn_gf2m(sqrt_enc, sp_field));
211 }
212 secure_vector<uint8_t> enc_support;
213 BER_Decoder dec3 = dec2.end_cons().decode(enc_support, ASN1_Type::OctetString);
214 if(enc_support.size() % 2) {
215 throw Decoding_Error("encoded support has odd length");
216 }
217 if(enc_support.size() / 2 != n) {
218 throw Decoding_Error("encoded support has length different from code length");
219 }
220 for(uint32_t i = 0; i < n * 2; i += 2) {
221 gf2m el = (enc_support[i] << 8) | enc_support[i + 1];
222 m_Linv.push_back(el);
223 }
226 if(enc_H.size() % 4) {
227 throw Decoding_Error("encoded parity check matrix has length which is not a multiple of four");
228 }
229 if(enc_H.size() / 4 != bit_size_to_32bit_size(m_codimension) * m_code_length) {
230 throw Decoding_Error("encoded parity check matrix has wrong length");
231 }
232
233 for(uint32_t i = 0; i < enc_H.size(); i += 4) {
234 uint32_t coeff = (enc_H[i] << 24) | (enc_H[i + 1] << 16) | (enc_H[i + 2] << 8) | enc_H[i + 3];
235 m_coeffs.push_back(coeff);
236 }
237}
238
240 if(*static_cast<const McEliece_PublicKey*>(this) != *static_cast<const McEliece_PublicKey*>(&other)) {
241 return false;
242 }
243 if(m_g != other.m_g) {
244 return false;
245 }
246
247 if(m_sqrtmod != other.m_sqrtmod) {
248 return false;
249 }
250 if(m_Linv != other.m_Linv) {
251 return false;
252 }
253 if(m_coeffs != other.m_coeffs) {
254 return false;
255 }
256
257 if(m_codimension != other.m_codimension || m_dimension != other.m_dimension) {
258 return false;
259 }
260
261 return true;
262}
263
264std::unique_ptr<Public_Key> McEliece_PrivateKey::public_key() const {
265 return std::make_unique<McEliece_PublicKey>(get_public_matrix(), get_t(), get_code_length());
266}
267
269 if(m_public_matrix != other.m_public_matrix) {
270 return false;
271 }
272 if(m_t != other.m_t) {
273 return false;
274 }
275 if(m_code_length != other.m_code_length) {
276 return false;
277 }
278 return true;
279}
280
281namespace {
282
283class MCE_KEM_Encryptor final : public PK_Ops::KEM_Encryption_with_KDF {
284 public:
285 MCE_KEM_Encryptor(const McEliece_PublicKey& key, std::string_view kdf) :
286 KEM_Encryption_with_KDF(kdf), m_key(key) {}
287
288 private:
289 size_t raw_kem_shared_key_length() const override {
290 const size_t err_sz = (m_key.get_code_length() + 7) / 8;
291 const size_t ptext_sz = (m_key.get_message_word_bit_length() + 7) / 8;
292 return ptext_sz + err_sz;
293 }
294
295 size_t encapsulated_key_length() const override { return (m_key.get_code_length() + 7) / 8; }
296
297 void raw_kem_encrypt(std::span<uint8_t> out_encapsulated_key,
298 std::span<uint8_t> raw_shared_key,
299 RandomNumberGenerator& rng) override {
300 secure_vector<uint8_t> plaintext = m_key.random_plaintext_element(rng);
301
302 secure_vector<uint8_t> ciphertext, error_mask;
303 mceliece_encrypt(ciphertext, error_mask, plaintext, m_key, rng);
304
305 // TODO: Perhaps avoid the copies below
306 BOTAN_ASSERT_NOMSG(out_encapsulated_key.size() == ciphertext.size());
307 std::copy(ciphertext.begin(), ciphertext.end(), out_encapsulated_key.begin());
308
309 BOTAN_ASSERT_NOMSG(raw_shared_key.size() == plaintext.size() + error_mask.size());
310 BufferStuffer bs(raw_shared_key);
311 bs.append(plaintext);
312 bs.append(error_mask);
313 }
314
315 const McEliece_PublicKey& m_key;
316};
317
318class MCE_KEM_Decryptor final : public PK_Ops::KEM_Decryption_with_KDF {
319 public:
320 MCE_KEM_Decryptor(const McEliece_PrivateKey& key, std::string_view kdf) :
321 KEM_Decryption_with_KDF(kdf), m_key(key) {}
322
323 private:
324 size_t raw_kem_shared_key_length() const override {
325 const size_t err_sz = (m_key.get_code_length() + 7) / 8;
326 const size_t ptext_sz = (m_key.get_message_word_bit_length() + 7) / 8;
327 return ptext_sz + err_sz;
328 }
329
330 size_t encapsulated_key_length() const override { return (m_key.get_code_length() + 7) / 8; }
331
332 void raw_kem_decrypt(std::span<uint8_t> out_shared_key, std::span<const uint8_t> encapsulated_key) override {
333 secure_vector<uint8_t> plaintext, error_mask;
334 mceliece_decrypt(plaintext, error_mask, encapsulated_key.data(), encapsulated_key.size(), m_key);
335
336 // TODO: perhaps avoid the copies below
337 BOTAN_ASSERT_NOMSG(out_shared_key.size() == plaintext.size() + error_mask.size());
338 BufferStuffer bs(out_shared_key);
339 bs.append(plaintext);
340 bs.append(error_mask);
341 }
342
343 const McEliece_PrivateKey& m_key;
344};
345
346} // namespace
347
348std::unique_ptr<Private_Key> McEliece_PublicKey::generate_another(RandomNumberGenerator& rng) const {
349 return std::make_unique<McEliece_PrivateKey>(rng, get_code_length(), get_t());
350}
351
352std::unique_ptr<PK_Ops::KEM_Encryption> McEliece_PublicKey::create_kem_encryption_op(std::string_view params,
353 std::string_view provider) const {
354 if(provider == "base" || provider.empty()) {
355 return std::make_unique<MCE_KEM_Encryptor>(*this, params);
356 }
357 throw Provider_Not_Found(algo_name(), provider);
358}
359
360std::unique_ptr<PK_Ops::KEM_Decryption> McEliece_PrivateKey::create_kem_decryption_op(RandomNumberGenerator& /*rng*/,
361 std::string_view params,
362 std::string_view provider) const {
363 if(provider == "base" || provider.empty()) {
364 return std::make_unique<MCE_KEM_Decryptor>(*this, params);
365 }
366 throw Provider_Not_Found(algo_name(), provider);
367}
368
369} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
virtual OID object_identifier() const
Definition pk_keys.cpp:22
void push_back(const BER_Object &obj)
Definition ber_dec.cpp:286
BER_Decoder & decode(bool &out)
Definition ber_dec.h:186
BER_Decoder & end_cons()
Definition ber_dec.cpp:309
BER_Decoder start_sequence()
Definition ber_dec.h:123
secure_vector< uint8_t > get_contents()
Definition der_enc.cpp:132
DER_Encoder & start_sequence()
Definition der_enc.h:64
DER_Encoder & end_cons()
Definition der_enc.cpp:171
DER_Encoder & encode(bool b)
Definition der_enc.cpp:250
secure_vector< uint8_t > private_key_bits() const override
McEliece_PrivateKey(RandomNumberGenerator &rng, size_t code_length, size_t t)
std::unique_ptr< Public_Key > public_key() const override
std::unique_ptr< PK_Ops::KEM_Decryption > create_kem_decryption_op(RandomNumberGenerator &rng, std::string_view params, std::string_view provider) const override
const polyn_gf2m & get_goppa_polyn() const
bool operator==(const McEliece_PrivateKey &other) const
bool check_key(RandomNumberGenerator &rng, bool strong) const override
secure_vector< uint8_t > random_plaintext_element(RandomNumberGenerator &rng) const
size_t get_message_word_bit_length() const
std::vector< uint8_t > raw_public_key_bits() const override
size_t get_t() const
Definition mceliece.h:50
std::unique_ptr< PK_Ops::KEM_Encryption > create_kem_encryption_op(std::string_view params, std::string_view provider) const override
std::string algo_name() const override
Definition mceliece.h:38
std::vector< uint8_t > public_key_bits() const override
std::unique_ptr< Private_Key > generate_another(RandomNumberGenerator &rng) const final
std::vector< uint8_t > m_public_matrix
Definition mceliece.h:74
const std::vector< uint8_t > & get_public_matrix() const
Definition mceliece.h:56
size_t estimated_strength() const override
size_t get_code_length() const
Definition mceliece.h:52
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)
Definition rng.h:52
int(* final)(unsigned char *, CTX *)
constexpr uint8_t get_byte(T input)
Definition loadstor.h:75
void mceliece_decrypt(secure_vector< uint8_t > &plaintext_out, secure_vector< uint8_t > &error_mask_out, const secure_vector< uint8_t > &ciphertext, const McEliece_PrivateKey &key)
void mceliece_encrypt(secure_vector< uint8_t > &ciphertext_out, secure_vector< uint8_t > &error_mask_out, const secure_vector< uint8_t > &plaintext, const McEliece_PublicKey &key, RandomNumberGenerator &rng)
Definition mceliece.cpp:109
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)
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61
size_t bit_size_to_32bit_size(size_t bit_size)
constexpr uint8_t ceil_log2(T x)
Definition bit_ops.h:122
uint16_t gf2m