Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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