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