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