Botan  2.4.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  return DER_Encoder()
78  .encode(static_cast<size_t>(get_code_length()))
79  .encode(static_cast<size_t>(get_t()))
80  .end_cons()
82  .end_cons()
84  }
85 
87  {
88  return m_code_length;
89  }
90 
92  {
94  }
95 
96 McEliece_PublicKey::McEliece_PublicKey(const std::vector<uint8_t>& key_bits)
97  {
98  BER_Decoder dec(key_bits);
99  size_t n;
100  size_t t;
101  dec.start_cons(SEQUENCE)
103  .decode(n)
104  .decode(t)
105  .end_cons()
107  .end_cons();
108  m_t = t;
109  m_code_length = n;
110  }
111 
113  {
114  DER_Encoder enc;
115  enc.start_cons(SEQUENCE)
117  .encode(static_cast<size_t>(get_code_length()))
118  .encode(static_cast<size_t>(get_t()))
119  .end_cons()
121  .encode(m_g.encode(), OCTET_STRING); // g as octet string
122  enc.start_cons(SEQUENCE);
123  for(uint32_t i = 0; i < m_sqrtmod.size(); i++)
124  {
125  enc.encode(m_sqrtmod[i].encode(), OCTET_STRING);
126  }
127  enc.end_cons();
128  secure_vector<uint8_t> enc_support;
129  for(uint32_t i = 0; i < m_Linv.size(); i++)
130  {
131  enc_support.push_back(m_Linv[i] >> 8);
132  enc_support.push_back(m_Linv[i]);
133  }
134  enc.encode(enc_support, OCTET_STRING);
136  for(uint32_t i = 0; i < m_coeffs.size(); i++)
137  {
138  enc_H.push_back(m_coeffs[i] >> 24);
139  enc_H.push_back(m_coeffs[i] >> 16);
140  enc_H.push_back(m_coeffs[i] >> 8);
141  enc_H.push_back(m_coeffs[i]);
142  }
143  enc.encode(enc_H, OCTET_STRING);
144  enc.end_cons();
145  return enc.get_contents();
146  }
147 
149  {
150  const secure_vector<uint8_t> plaintext = this->random_plaintext_element(rng);
151 
152  secure_vector<uint8_t> ciphertext;
153  secure_vector<uint8_t> errors;
154  mceliece_encrypt(ciphertext, errors, plaintext, *this, rng);
155 
156  secure_vector<uint8_t> plaintext_out;
157  secure_vector<uint8_t> errors_out;
158  mceliece_decrypt(plaintext_out, errors_out, ciphertext, *this);
159 
160  if(errors != errors_out || plaintext != plaintext_out)
161  return false;
162 
163  return true;
164  }
165 
167  {
168  size_t n, t;
170  BER_Decoder dec_base(key_bits);
171  BER_Decoder dec = dec_base.start_cons(SEQUENCE)
173  .decode(n)
174  .decode(t)
175  .end_cons()
177  .decode(enc_g, OCTET_STRING);
178 
179  if(t == 0 || n == 0)
180  throw Decoding_Error("invalid McEliece parameters");
181 
182  uint32_t ext_deg = ceil_log2(n);
183  m_code_length = n;
184  m_t = t;
185  m_codimension = (ext_deg * t);
186  m_dimension = (n - m_codimension);
187 
188  std::shared_ptr<GF2m_Field> sp_field(new GF2m_Field(ext_deg));
189  m_g = polyn_gf2m(enc_g, sp_field);
190  if(m_g.get_degree() != static_cast<int>(t))
191  {
192  throw Decoding_Error("degree of decoded Goppa polynomial is incorrect");
193  }
194  BER_Decoder dec2 = dec.start_cons(SEQUENCE);
195  for(uint32_t i = 0; i < t/2; i++)
196  {
197  secure_vector<uint8_t> sqrt_enc;
198  dec2.decode(sqrt_enc, OCTET_STRING);
199  while(sqrt_enc.size() < (t*2))
200  {
201  // ensure that the length is always t
202  sqrt_enc.push_back(0);
203  sqrt_enc.push_back(0);
204  }
205  if(sqrt_enc.size() != t*2)
206  {
207  throw Decoding_Error("length of square root polynomial entry is too large");
208  }
209  m_sqrtmod.push_back(polyn_gf2m(sqrt_enc, sp_field));
210  }
211  secure_vector<uint8_t> enc_support;
212  BER_Decoder dec3 = dec2.end_cons()
213  .decode(enc_support, OCTET_STRING);
214  if(enc_support.size() % 2)
215  {
216  throw Decoding_Error("encoded support has odd length");
217  }
218  if(enc_support.size() / 2 != n)
219  {
220  throw Decoding_Error("encoded support has length different from code length");
221  }
222  for(uint32_t i = 0; i < n*2; i+=2)
223  {
224  gf2m el = (enc_support[i] << 8) | enc_support[i+1];
225  m_Linv.push_back(el);
226  }
228  dec3.decode(enc_H, OCTET_STRING)
229  .end_cons();
230  if(enc_H.size() % 4)
231  {
232  throw Decoding_Error("encoded parity check matrix has length which is not a multiple of four");
233  }
234  if(enc_H.size()/4 != bit_size_to_32bit_size(m_codimension) * m_code_length )
235  {
236  throw Decoding_Error("encoded parity check matrix has wrong length");
237  }
238 
239  for(uint32_t i = 0; i < enc_H.size(); i+=4)
240  {
241  uint32_t coeff = (enc_H[i] << 24) | (enc_H[i+1] << 16) | (enc_H[i+2] << 8) | enc_H[i+3];
242  m_coeffs.push_back(coeff);
243  }
244 
245  }
246 
248  {
249  if(*static_cast<const McEliece_PublicKey*>(this) != *static_cast<const McEliece_PublicKey*>(&other))
250  {
251  return false;
252  }
253  if(m_g != other.m_g)
254  {
255  return false;
256  }
257 
258  if( m_sqrtmod != other.m_sqrtmod)
259  {
260  return false;
261  }
262  if( m_Linv != other.m_Linv)
263  {
264  return false;
265  }
266  if( m_coeffs != other.m_coeffs)
267  {
268  return false;
269  }
270 
271  if(m_codimension != other.m_codimension || m_dimension != other.m_dimension)
272  {
273  return false;
274  }
275 
276  return true;
277  }
278 
280  {
281  if(m_public_matrix != other.m_public_matrix)
282  {
283  return false;
284  }
285  if(m_t != other.m_t )
286  {
287  return false;
288  }
289  if( m_code_length != other.m_code_length)
290  {
291  return false;
292  }
293  return true;
294  }
295 
296 namespace {
297 
298 class MCE_KEM_Encryptor final : public PK_Ops::KEM_Encryption_with_KDF
299  {
300  public:
301 
302  MCE_KEM_Encryptor(const McEliece_PublicKey& key,
303  const std::string& kdf) :
304  KEM_Encryption_with_KDF(kdf), m_key(key) {}
305 
306  private:
307  void raw_kem_encrypt(secure_vector<uint8_t>& out_encapsulated_key,
308  secure_vector<uint8_t>& raw_shared_key,
309  Botan::RandomNumberGenerator& rng) override
310  {
311  secure_vector<uint8_t> plaintext = m_key.random_plaintext_element(rng);
312 
313  secure_vector<uint8_t> ciphertext, error_mask;
314  mceliece_encrypt(ciphertext, error_mask, plaintext, m_key, rng);
315 
316  raw_shared_key.clear();
317  raw_shared_key += plaintext;
318  raw_shared_key += error_mask;
319 
320  out_encapsulated_key.swap(ciphertext);
321  }
322 
323  const McEliece_PublicKey& m_key;
324  };
325 
326 class MCE_KEM_Decryptor final : public PK_Ops::KEM_Decryption_with_KDF
327  {
328  public:
329 
330  MCE_KEM_Decryptor(const McEliece_PrivateKey& key,
331  const std::string& kdf) :
332  KEM_Decryption_with_KDF(kdf), m_key(key) {}
333 
334  private:
336  raw_kem_decrypt(const uint8_t encap_key[], size_t len) override
337  {
338  secure_vector<uint8_t> plaintext, error_mask;
339  mceliece_decrypt(plaintext, error_mask, encap_key, len, m_key);
340 
341  secure_vector<uint8_t> output;
342  output.reserve(plaintext.size() + error_mask.size());
343  output.insert(output.end(), plaintext.begin(), plaintext.end());
344  output.insert(output.end(), error_mask.begin(), error_mask.end());
345  return output;
346  }
347 
348  const McEliece_PrivateKey& m_key;
349  };
350 
351 }
352 
353 std::unique_ptr<PK_Ops::KEM_Encryption>
355  const std::string& params,
356  const std::string& provider) const
357  {
358  if(provider == "base" || provider.empty())
359  return std::unique_ptr<PK_Ops::KEM_Encryption>(new MCE_KEM_Encryptor(*this, params));
360  throw Provider_Not_Found(algo_name(), provider);
361  }
362 
363 std::unique_ptr<PK_Ops::KEM_Decryption>
365  const std::string& params,
366  const std::string& provider) const
367  {
368  if(provider == "base" || provider.empty())
369  return std::unique_ptr<PK_Ops::KEM_Decryption>(new MCE_KEM_Decryptor(*this, params));
370  throw Provider_Not_Found(algo_name(), provider);
371  }
372 
373 }
374 
375 
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)
std::vector< uint8_t > get_contents_unlocked()
Definition: der_enc.h:27
virtual void randomize(uint8_t output[], size_t length)=0
secure_vector< uint8_t > get_contents()
Definition: der_enc.cpp:123
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:241
BER_Decoder & decode(bool &v)
Definition: ber_dec.cpp:355
DER_Encoder & end_cons()
Definition: der_enc.cpp:146
bool check_key(RandomNumberGenerator &rng, bool strong) const override
DER_Encoder & encode(bool b)
Definition: der_enc.cpp:202
virtual OID get_oid() const
Definition: pk_keys.cpp:51
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:265
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:251
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:117
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:136
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
std::vector< uint8_t > public_key_bits() const override