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