Botan 3.0.0-alpha0
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#include <botan/internal/polyn_gf2m.h>
15#include <botan/internal/mce_internal.h>
16#include <botan/internal/bit_ops.h>
17#include <botan/internal/code_based_util.h>
18#include <botan/internal/pk_ops_impl.h>
19#include <botan/internal/loadstor.h>
20#include <botan/der_enc.h>
21#include <botan/ber_dec.h>
22#include <botan/rng.h>
23
24namespace Botan {
25
26McEliece_PrivateKey::McEliece_PrivateKey(const McEliece_PrivateKey&) = default;
27McEliece_PrivateKey::McEliece_PrivateKey(McEliece_PrivateKey&&) = default;
28McEliece_PrivateKey& McEliece_PrivateKey::operator=(const McEliece_PrivateKey&) = default;
29McEliece_PrivateKey& McEliece_PrivateKey::operator=(McEliece_PrivateKey&&) = default;
31
33 std::vector<uint32_t> const& parity_check_matrix_coeffs,
34 std::vector<polyn_gf2m> const& square_root_matrix,
35 std::vector<gf2m> const& inverse_support,
36 std::vector<uint8_t> const& public_matrix) :
37 McEliece_PublicKey(public_matrix, goppa_polyn.get_degree(), inverse_support.size()),
38 m_g{goppa_polyn},
39 m_sqrtmod(square_root_matrix),
40 m_Linv(inverse_support),
41 m_coeffs(parity_check_matrix_coeffs),
42 m_codimension(static_cast<size_t>(ceil_log2(inverse_support.size())) * goppa_polyn.get_degree()),
43 m_dimension(inverse_support.size() - m_codimension)
44 {
45 }
46
48 {
49 uint32_t ext_deg = ceil_log2(code_length);
50 *this = generate_mceliece_key(rng, ext_deg, code_length, t);
51 }
52
54 {
55 return m_g[0];
56 }
57
59 {
60 size_t codimension = ceil_log2(m_code_length) * m_t;
61 return m_code_length - codimension;
62 }
63
65 {
66 const size_t bits = get_message_word_bit_length();
67
68 secure_vector<uint8_t> plaintext((bits+7)/8);
69 rng.randomize(plaintext.data(), plaintext.size());
70
71 // unset unused bits in the last plaintext byte
72 if(uint32_t used = bits % 8)
73 {
74 const uint8_t mask = (1 << used) - 1;
75 plaintext[plaintext.size() - 1] &= mask;
76 }
77
78 return plaintext;
79 }
80
82 {
84 }
85
86std::vector<uint8_t> McEliece_PublicKey::public_key_bits() const
87 {
88 std::vector<uint8_t> output;
89 DER_Encoder(output)
92 .encode(static_cast<size_t>(get_code_length()))
93 .encode(static_cast<size_t>(get_t()))
94 .end_cons()
96 .end_cons();
97 return output;
98 }
99
101 {
102 return m_code_length;
103 }
104
106 {
108 }
109
110McEliece_PublicKey::McEliece_PublicKey(const std::vector<uint8_t>& key_bits)
111 {
112 BER_Decoder dec(key_bits);
113 size_t n;
114 size_t t;
115 dec.start_sequence()
117 .decode(n)
118 .decode(t)
119 .end_cons()
121 .end_cons();
122 m_t = t;
123 m_code_length = n;
124 }
125
127 {
128 DER_Encoder enc;
129 enc.start_sequence()
131 .encode(static_cast<size_t>(get_code_length()))
132 .encode(static_cast<size_t>(get_t()))
133 .end_cons()
135 .encode(m_g[0].encode(), ASN1_Type::OctetString); // g as octet string
136 enc.start_sequence();
137 for(size_t i = 0; i < m_sqrtmod.size(); i++)
138 {
139 enc.encode(m_sqrtmod[i].encode(), ASN1_Type::OctetString);
140 }
141 enc.end_cons();
142 secure_vector<uint8_t> enc_support;
143
144 for(uint16_t Linv : m_Linv)
145 {
146 enc_support.push_back(get_byte<0>(Linv));
147 enc_support.push_back(get_byte<1>(Linv));
148 }
149 enc.encode(enc_support, ASN1_Type::OctetString);
151 for(uint32_t coef : m_coeffs)
152 {
153 enc_H.push_back(get_byte<0>(coef));
154 enc_H.push_back(get_byte<1>(coef));
155 enc_H.push_back(get_byte<2>(coef));
156 enc_H.push_back(get_byte<3>(coef));
157 }
158 enc.encode(enc_H, ASN1_Type::OctetString);
159 enc.end_cons();
160 return enc.get_contents();
161 }
162
164 {
165 const secure_vector<uint8_t> plaintext = this->random_plaintext_element(rng);
166
167 secure_vector<uint8_t> ciphertext;
169 mceliece_encrypt(ciphertext, errors, plaintext, *this, rng);
170
171 secure_vector<uint8_t> plaintext_out;
172 secure_vector<uint8_t> errors_out;
173 mceliece_decrypt(plaintext_out, errors_out, ciphertext, *this);
174
175 if(errors != errors_out || plaintext != plaintext_out)
176 return false;
177
178 return true;
179 }
180
182 {
183 size_t n, t;
185 BER_Decoder dec_base(key_bits);
186 BER_Decoder dec = dec_base.start_sequence()
188 .decode(n)
189 .decode(t)
190 .end_cons()
193
194 if(t == 0 || n == 0)
195 throw Decoding_Error("invalid McEliece parameters");
196
197 uint32_t ext_deg = ceil_log2(n);
198 m_code_length = n;
199 m_t = t;
200 m_codimension = (ext_deg * t);
201 m_dimension = (n - m_codimension);
202
203 auto sp_field = std::make_shared<GF2m_Field>(ext_deg);
204 m_g = { polyn_gf2m(enc_g, sp_field) };
205 if(m_g[0].get_degree() != static_cast<int>(t))
206 {
207 throw Decoding_Error("degree of decoded Goppa polynomial is incorrect");
208 }
209 BER_Decoder dec2 = dec.start_sequence();
210 for(uint32_t i = 0; i < t/2; i++)
211 {
212 secure_vector<uint8_t> sqrt_enc;
213 dec2.decode(sqrt_enc, ASN1_Type::OctetString);
214 while(sqrt_enc.size() < (t*2))
215 {
216 // ensure that the length is always t
217 sqrt_enc.push_back(0);
218 sqrt_enc.push_back(0);
219 }
220 if(sqrt_enc.size() != t*2)
221 {
222 throw Decoding_Error("length of square root polynomial entry is too large");
223 }
224 m_sqrtmod.push_back(polyn_gf2m(sqrt_enc, sp_field));
225 }
226 secure_vector<uint8_t> enc_support;
227 BER_Decoder dec3 = dec2.end_cons()
228 .decode(enc_support, ASN1_Type::OctetString);
229 if(enc_support.size() % 2)
230 {
231 throw Decoding_Error("encoded support has odd length");
232 }
233 if(enc_support.size() / 2 != n)
234 {
235 throw Decoding_Error("encoded support has length different from code length");
236 }
237 for(uint32_t i = 0; i < n*2; i+=2)
238 {
239 gf2m el = (enc_support[i] << 8) | enc_support[i+1];
240 m_Linv.push_back(el);
241 }
243 dec3.decode(enc_H, ASN1_Type::OctetString)
244 .end_cons();
245 if(enc_H.size() % 4)
246 {
247 throw Decoding_Error("encoded parity check matrix has length which is not a multiple of four");
248 }
249 if(enc_H.size() / 4 != bit_size_to_32bit_size(m_codimension) * m_code_length)
250 {
251 throw Decoding_Error("encoded parity check matrix has wrong length");
252 }
253
254 for(uint32_t i = 0; i < enc_H.size(); i+=4)
255 {
256 uint32_t coeff = (enc_H[i] << 24) | (enc_H[i+1] << 16) | (enc_H[i+2] << 8) | enc_H[i+3];
257 m_coeffs.push_back(coeff);
258 }
259
260 }
261
263 {
264 if(*static_cast<const McEliece_PublicKey*>(this) != *static_cast<const McEliece_PublicKey*>(&other))
265 {
266 return false;
267 }
268 if(m_g != other.m_g)
269 {
270 return false;
271 }
272
273 if( m_sqrtmod != other.m_sqrtmod)
274 {
275 return false;
276 }
277 if( m_Linv != other.m_Linv)
278 {
279 return false;
280 }
281 if( m_coeffs != other.m_coeffs)
282 {
283 return false;
284 }
285
286 if(m_codimension != other.m_codimension || m_dimension != other.m_dimension)
287 {
288 return false;
289 }
290
291 return true;
292 }
293
294std::unique_ptr<Public_Key> McEliece_PrivateKey::public_key() const
295 {
296 return std::make_unique<McEliece_PublicKey>(
298 }
299
301 {
303 {
304 return false;
305 }
306 if(m_t != other.m_t)
307 {
308 return false;
309 }
310 if( m_code_length != other.m_code_length)
311 {
312 return false;
313 }
314 return true;
315 }
316
317namespace {
318
319class MCE_KEM_Encryptor final : public PK_Ops::KEM_Encryption_with_KDF
320 {
321 public:
322
323 MCE_KEM_Encryptor(const McEliece_PublicKey& key,
324 const std::string& kdf) :
325 KEM_Encryption_with_KDF(kdf), m_key(key) {}
326
327 private:
328 void raw_kem_encrypt(secure_vector<uint8_t>& out_encapsulated_key,
329 secure_vector<uint8_t>& raw_shared_key,
330 Botan::RandomNumberGenerator& rng) override
331 {
332 secure_vector<uint8_t> plaintext = m_key.random_plaintext_element(rng);
333
334 secure_vector<uint8_t> ciphertext, error_mask;
335 mceliece_encrypt(ciphertext, error_mask, plaintext, m_key, rng);
336
337 raw_shared_key.clear();
338 raw_shared_key += plaintext;
339 raw_shared_key += error_mask;
340
341 out_encapsulated_key.swap(ciphertext);
342 }
343
344 const McEliece_PublicKey& m_key;
345 };
346
347class MCE_KEM_Decryptor final : public PK_Ops::KEM_Decryption_with_KDF
348 {
349 public:
350
351 MCE_KEM_Decryptor(const McEliece_PrivateKey& key,
352 const std::string& kdf) :
353 KEM_Decryption_with_KDF(kdf), m_key(key) {}
354
355 private:
356 secure_vector<uint8_t>
357 raw_kem_decrypt(const uint8_t encap_key[], size_t len) override
358 {
359 secure_vector<uint8_t> plaintext, error_mask;
360 mceliece_decrypt(plaintext, error_mask, encap_key, len, m_key);
361
362 secure_vector<uint8_t> output;
363 output.reserve(plaintext.size() + error_mask.size());
364 output.insert(output.end(), plaintext.begin(), plaintext.end());
365 output.insert(output.end(), error_mask.begin(), error_mask.end());
366 return output;
367 }
368
369 const McEliece_PrivateKey& m_key;
370 };
371
372}
373
374std::unique_ptr<PK_Ops::KEM_Encryption>
376 const std::string& params,
377 const std::string& provider) const
378 {
379 if(provider == "base" || provider.empty())
380 return std::make_unique<MCE_KEM_Encryptor>(*this, params);
381 throw Provider_Not_Found(algo_name(), provider);
382 }
383
384std::unique_ptr<PK_Ops::KEM_Decryption>
386 const std::string& params,
387 const std::string& provider) const
388 {
389 if(provider == "base" || provider.empty())
390 return std::make_unique<MCE_KEM_Decryptor>(*this, params);
391 throw Provider_Not_Found(algo_name(), provider);
392 }
393
394}
395
396
void push_back(const BER_Object &obj)
Definition: ber_dec.cpp:279
BER_Decoder & decode(bool &out)
Definition: ber_dec.h:187
BER_Decoder & end_cons()
Definition: ber_dec.cpp:303
BER_Decoder start_sequence()
Definition: ber_dec.h:111
secure_vector< uint8_t > get_contents()
Definition: der_enc.cpp:155
DER_Encoder & start_sequence()
Definition: der_enc.h:66
DER_Encoder & end_cons()
Definition: der_enc.cpp:194
DER_Encoder & encode(bool b)
Definition: der_enc.cpp:288
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
polyn_gf2m const & get_goppa_polyn() const
bool operator==(const McEliece_PrivateKey &other) const
McEliece_PrivateKey & operator=(const McEliece_PrivateKey &)
std::unique_ptr< PK_Ops::KEM_Decryption > create_kem_decryption_op(RandomNumberGenerator &rng, const std::string &params, const std::string &provider) const override
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
size_t get_t() const
Definition: mceliece.h:51
std::string algo_name() const override
Definition: mceliece.h:39
std::vector< uint8_t > public_key_bits() const override
std::vector< uint8_t > m_public_matrix
Definition: mceliece.h:67
const std::vector< uint8_t > & get_public_matrix() const
Definition: mceliece.h:54
std::unique_ptr< PK_Ops::KEM_Encryption > create_kem_encryption_op(RandomNumberGenerator &rng, const std::string &params, const std::string &provider) const override
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
virtual OID get_oid() const
Definition: pk_keys.cpp:53
virtual void randomize(uint8_t output[], size_t length)=0
int(* final)(unsigned char *, CTX *)
std::array< int16_t, KyberConstants::N > m_coeffs
Definition: kyber.cpp:275
std::string encode(const uint8_t der[], size_t length, const std::string &label, size_t width)
Definition: pem.cpp:41
Definition: alg_id.cpp:13
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)
Definition: goppa_code.cpp:130
constexpr uint8_t ceil_log2(T x)
Definition: bit_ops.h:119
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:120
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)
size_t bit_size_to_32bit_size(size_t bit_size)
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
uint16_t gf2m
Definition: gf2m_small_m.h:20