Coverage Report

Created: 2020-05-23 13:54

/src/botan/src/lib/pubkey/mce/mceliece_key.cpp
Line
Count
Source (jump to first uncovered line)
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
0
   {
38
0
   }
Unexecuted instantiation: Botan::McEliece_PrivateKey::McEliece_PrivateKey(Botan::polyn_gf2m const&, std::__1::vector<unsigned int, std::__1::allocator<unsigned int> > const&, std::__1::vector<Botan::polyn_gf2m, std::__1::allocator<Botan::polyn_gf2m> > const&, std::__1::vector<unsigned short, std::__1::allocator<unsigned short> > const&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&)
Unexecuted instantiation: Botan::McEliece_PrivateKey::McEliece_PrivateKey(Botan::polyn_gf2m const&, std::__1::vector<unsigned int, std::__1::allocator<unsigned int> > const&, std::__1::vector<Botan::polyn_gf2m, std::__1::allocator<Botan::polyn_gf2m> > const&, std::__1::vector<unsigned short, std::__1::allocator<unsigned short> > const&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&)
39
40
McEliece_PrivateKey::McEliece_PrivateKey(RandomNumberGenerator& rng, size_t code_length, size_t t)
41
0
   {
42
0
   uint32_t ext_deg = ceil_log2(code_length);
43
0
   *this = generate_mceliece_key(rng, ext_deg, code_length, t);
44
0
   }
Unexecuted instantiation: Botan::McEliece_PrivateKey::McEliece_PrivateKey(Botan::RandomNumberGenerator&, unsigned long, unsigned long)
Unexecuted instantiation: Botan::McEliece_PrivateKey::McEliece_PrivateKey(Botan::RandomNumberGenerator&, unsigned long, unsigned long)
45
46
size_t McEliece_PublicKey::get_message_word_bit_length() const
47
0
   {
48
0
   size_t codimension = ceil_log2(m_code_length) * m_t;
49
0
   return m_code_length - codimension;
50
0
   }
51
52
secure_vector<uint8_t> McEliece_PublicKey::random_plaintext_element(RandomNumberGenerator& rng) const
53
0
   {
54
0
   const size_t bits = get_message_word_bit_length();
55
0
56
0
   secure_vector<uint8_t> plaintext((bits+7)/8);
57
0
   rng.randomize(plaintext.data(), plaintext.size());
58
0
59
0
   // unset unused bits in the last plaintext byte
60
0
   if(uint32_t used = bits % 8)
61
0
      {
62
0
      const uint8_t mask = (1 << used) - 1;
63
0
      plaintext[plaintext.size() - 1] &= mask;
64
0
      }
65
0
66
0
   return plaintext;
67
0
   }
68
69
AlgorithmIdentifier McEliece_PublicKey::algorithm_identifier() const
70
0
   {
71
0
   return AlgorithmIdentifier(get_oid(), AlgorithmIdentifier::USE_EMPTY_PARAM);
72
0
   }
73
74
std::vector<uint8_t> McEliece_PublicKey::public_key_bits() const
75
0
   {
76
0
   std::vector<uint8_t> output;
77
0
   DER_Encoder(output)
78
0
      .start_cons(SEQUENCE)
79
0
         .start_cons(SEQUENCE)
80
0
         .encode(static_cast<size_t>(get_code_length()))
81
0
         .encode(static_cast<size_t>(get_t()))
82
0
         .end_cons()
83
0
      .encode(m_public_matrix, OCTET_STRING)
84
0
      .end_cons();
85
0
   return output;
86
0
   }
87
88
size_t McEliece_PublicKey::key_length() const
89
0
   {
90
0
   return m_code_length;
91
0
   }
92
93
size_t McEliece_PublicKey::estimated_strength() const
94
0
   {
95
0
   return mceliece_work_factor(m_code_length, m_t);
96
0
   }
97
98
McEliece_PublicKey::McEliece_PublicKey(const std::vector<uint8_t>& key_bits)
99
0
   {
100
0
   BER_Decoder dec(key_bits);
101
0
   size_t n;
102
0
   size_t t;
103
0
   dec.start_cons(SEQUENCE)
104
0
      .start_cons(SEQUENCE)
105
0
      .decode(n)
106
0
      .decode(t)
107
0
      .end_cons()
108
0
      .decode(m_public_matrix, OCTET_STRING)
109
0
      .end_cons();
110
0
   m_t = t;
111
0
   m_code_length = n;
112
0
   }
Unexecuted instantiation: Botan::McEliece_PublicKey::McEliece_PublicKey(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&)
Unexecuted instantiation: Botan::McEliece_PublicKey::McEliece_PublicKey(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&)
113
114
secure_vector<uint8_t> McEliece_PrivateKey::private_key_bits() const
115
0
   {
116
0
   DER_Encoder enc;
117
0
   enc.start_cons(SEQUENCE)
118
0
      .start_cons(SEQUENCE)
119
0
      .encode(static_cast<size_t>(get_code_length()))
120
0
      .encode(static_cast<size_t>(get_t()))
121
0
      .end_cons()
122
0
      .encode(m_public_matrix, OCTET_STRING)
123
0
      .encode(m_g.encode(), OCTET_STRING); // g as octet string
124
0
   enc.start_cons(SEQUENCE);
125
0
   for(size_t i = 0; i < m_sqrtmod.size(); i++)
126
0
      {
127
0
      enc.encode(m_sqrtmod[i].encode(), OCTET_STRING);
128
0
      }
129
0
   enc.end_cons();
130
0
   secure_vector<uint8_t> enc_support;
131
0
132
0
   for(uint16_t Linv : m_Linv)
133
0
      {
134
0
      enc_support.push_back(get_byte(0, Linv));
135
0
      enc_support.push_back(get_byte(1, Linv));
136
0
      }
137
0
   enc.encode(enc_support, OCTET_STRING);
138
0
   secure_vector<uint8_t> enc_H;
139
0
   for(uint32_t coef : m_coeffs)
140
0
      {
141
0
      enc_H.push_back(get_byte(0, coef));
142
0
      enc_H.push_back(get_byte(1, coef));
143
0
      enc_H.push_back(get_byte(2, coef));
144
0
      enc_H.push_back(get_byte(3, coef));
145
0
      }
146
0
   enc.encode(enc_H, OCTET_STRING);
147
0
   enc.end_cons();
148
0
   return enc.get_contents();
149
0
   }
150
151
bool McEliece_PrivateKey::check_key(RandomNumberGenerator& rng, bool) const
152
0
   {
153
0
   const secure_vector<uint8_t> plaintext = this->random_plaintext_element(rng);
154
0
155
0
   secure_vector<uint8_t> ciphertext;
156
0
   secure_vector<uint8_t> errors;
157
0
   mceliece_encrypt(ciphertext, errors, plaintext, *this, rng);
158
0
159
0
   secure_vector<uint8_t> plaintext_out;
160
0
   secure_vector<uint8_t> errors_out;
161
0
   mceliece_decrypt(plaintext_out, errors_out, ciphertext, *this);
162
0
163
0
   if(errors != errors_out || plaintext != plaintext_out)
164
0
      return false;
165
0
166
0
   return true;
167
0
   }
168
169
McEliece_PrivateKey::McEliece_PrivateKey(const secure_vector<uint8_t>& key_bits)
170
0
   {
171
0
   size_t n, t;
172
0
   secure_vector<uint8_t> enc_g;
173
0
   BER_Decoder dec_base(key_bits);
174
0
   BER_Decoder dec = dec_base.start_cons(SEQUENCE)
175
0
      .start_cons(SEQUENCE)
176
0
      .decode(n)
177
0
      .decode(t)
178
0
      .end_cons()
179
0
      .decode(m_public_matrix, OCTET_STRING)
180
0
      .decode(enc_g, OCTET_STRING);
181
0
182
0
   if(t == 0 || n == 0)
183
0
      throw Decoding_Error("invalid McEliece parameters");
184
0
185
0
   uint32_t ext_deg = ceil_log2(n);
186
0
   m_code_length = n;
187
0
   m_t = t;
188
0
   m_codimension = (ext_deg * t);
189
0
   m_dimension = (n - m_codimension);
190
0
191
0
   std::shared_ptr<GF2m_Field> sp_field(new GF2m_Field(ext_deg));
192
0
   m_g = polyn_gf2m(enc_g, sp_field);
193
0
   if(m_g.get_degree() != static_cast<int>(t))
194
0
      {
195
0
      throw Decoding_Error("degree of decoded Goppa polynomial is incorrect");
196
0
      }
197
0
   BER_Decoder dec2 = dec.start_cons(SEQUENCE);
198
0
   for(uint32_t i = 0; i < t/2; i++)
199
0
      {
200
0
      secure_vector<uint8_t> sqrt_enc;
201
0
      dec2.decode(sqrt_enc, OCTET_STRING);
202
0
      while(sqrt_enc.size() < (t*2))
203
0
         {
204
0
         // ensure that the length is always t
205
0
         sqrt_enc.push_back(0);
206
0
         sqrt_enc.push_back(0);
207
0
         }
208
0
      if(sqrt_enc.size() != t*2)
209
0
         {
210
0
         throw Decoding_Error("length of square root polynomial entry is too large");
211
0
         }
212
0
      m_sqrtmod.push_back(polyn_gf2m(sqrt_enc, sp_field));
213
0
      }
214
0
   secure_vector<uint8_t> enc_support;
215
0
   BER_Decoder dec3 = dec2.end_cons()
216
0
      .decode(enc_support, OCTET_STRING);
217
0
   if(enc_support.size() % 2)
218
0
      {
219
0
      throw Decoding_Error("encoded support has odd length");
220
0
      }
221
0
   if(enc_support.size() / 2 != n)
222
0
      {
223
0
      throw Decoding_Error("encoded support has length different from code length");
224
0
      }
225
0
   for(uint32_t i = 0; i < n*2; i+=2)
226
0
      {
227
0
      gf2m el = (enc_support[i] << 8) |  enc_support[i+1];
228
0
      m_Linv.push_back(el);
229
0
      }
230
0
   secure_vector<uint8_t> enc_H;
231
0
   dec3.decode(enc_H, OCTET_STRING)
232
0
      .end_cons();
233
0
   if(enc_H.size() % 4)
234
0
      {
235
0
      throw Decoding_Error("encoded parity check matrix has length which is not a multiple of four");
236
0
      }
237
0
   if(enc_H.size() / 4 != bit_size_to_32bit_size(m_codimension) * m_code_length)
238
0
      {
239
0
      throw Decoding_Error("encoded parity check matrix has wrong length");
240
0
      }
241
0
242
0
   for(uint32_t i = 0; i < enc_H.size(); i+=4)
243
0
      {
244
0
      uint32_t coeff = (enc_H[i] << 24) | (enc_H[i+1] << 16) | (enc_H[i+2] << 8) | enc_H[i+3];
245
0
      m_coeffs.push_back(coeff);
246
0
      }
247
0
248
0
   }
Unexecuted instantiation: Botan::McEliece_PrivateKey::McEliece_PrivateKey(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&)
Unexecuted instantiation: Botan::McEliece_PrivateKey::McEliece_PrivateKey(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&)
249
250
bool McEliece_PrivateKey::operator==(const McEliece_PrivateKey & other) const
251
0
   {
252
0
   if(*static_cast<const McEliece_PublicKey*>(this) != *static_cast<const McEliece_PublicKey*>(&other))
253
0
      {
254
0
      return false;
255
0
      }
256
0
   if(m_g != other.m_g)
257
0
      {
258
0
      return false;
259
0
      }
260
0
261
0
   if( m_sqrtmod != other.m_sqrtmod)
262
0
      {
263
0
      return false;
264
0
      }
265
0
   if( m_Linv != other.m_Linv)
266
0
      {
267
0
      return false;
268
0
      }
269
0
   if( m_coeffs != other.m_coeffs)
270
0
      {
271
0
      return false;
272
0
      }
273
0
274
0
   if(m_codimension != other.m_codimension || m_dimension != other.m_dimension)
275
0
      {
276
0
      return false;
277
0
      }
278
0
279
0
   return true;
280
0
   }
281
282
bool McEliece_PublicKey::operator==(const McEliece_PublicKey& other) const
283
0
   {
284
0
   if(m_public_matrix != other.m_public_matrix)
285
0
      {
286
0
      return false;
287
0
      }
288
0
   if(m_t != other.m_t)
289
0
      {
290
0
      return false;
291
0
      }
292
0
   if( m_code_length != other.m_code_length)
293
0
      {
294
0
      return false;
295
0
      }
296
0
   return true;
297
0
   }
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
0
         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
0
         {
314
0
         secure_vector<uint8_t> plaintext = m_key.random_plaintext_element(rng);
315
0
316
0
         secure_vector<uint8_t> ciphertext, error_mask;
317
0
         mceliece_encrypt(ciphertext, error_mask, plaintext, m_key, rng);
318
0
319
0
         raw_shared_key.clear();
320
0
         raw_shared_key += plaintext;
321
0
         raw_shared_key += error_mask;
322
0
323
0
         out_encapsulated_key.swap(ciphertext);
324
0
         }
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
0
         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
0
         {
341
0
         secure_vector<uint8_t> plaintext, error_mask;
342
0
         mceliece_decrypt(plaintext, error_mask, encap_key, len, m_key);
343
0
344
0
         secure_vector<uint8_t> output;
345
0
         output.reserve(plaintext.size() + error_mask.size());
346
0
         output.insert(output.end(), plaintext.begin(), plaintext.end());
347
0
         output.insert(output.end(), error_mask.begin(), error_mask.end());
348
0
         return output;
349
0
         }
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
0
   {
361
0
   if(provider == "base" || provider.empty())
362
0
      return std::unique_ptr<PK_Ops::KEM_Encryption>(new MCE_KEM_Encryptor(*this, params));
363
0
   throw Provider_Not_Found(algo_name(), provider);
364
0
   }
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
0
   {
371
0
   if(provider == "base" || provider.empty())
372
0
      return std::unique_ptr<PK_Ops::KEM_Decryption>(new MCE_KEM_Decryptor(*this, params));
373
0
   throw Provider_Not_Found(algo_name(), provider);
374
0
   }
375
376
}
377
378