Botan  2.1.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 
21 namespace Botan {
22 
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 
39  {
40  uint32_t ext_deg = ceil_log2(code_length);
41  *this = generate_mceliece_key(rng, ext_deg, code_length, t);
42  }
43 
45  {
46  uint32_t codimension = ceil_log2(m_code_length) * m_t;
47  return m_code_length - codimension;
48  }
49 
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 
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()
77  .encode(static_cast<size_t>(get_code_length()))
78  .encode(static_cast<size_t>(get_t()))
79  .end_cons()
81  .end_cons()
83  }
84 
86  {
87  return m_code_length;
88  }
89 
91  {
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)
102  .decode(n)
103  .decode(t)
104  .end_cons()
106  .end_cons();
107  m_t = t;
108  m_code_length = n;
109  }
110 
112  {
113  DER_Encoder enc;
114  enc.start_cons(SEQUENCE)
116  .encode(static_cast<size_t>(get_code_length()))
117  .encode(static_cast<size_t>(get_t()))
118  .end_cons()
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);
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 
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 
166  {
167  size_t n, t;
169  BER_Decoder dec_base(key_bits);
170  BER_Decoder dec = dec_base.start_cons(SEQUENCE)
172  .decode(n)
173  .decode(t)
174  .end_cons()
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  }
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 
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 
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>
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>
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 
secure_vector< uint8_t > random_plaintext_element(RandomNumberGenerator &rng) const
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
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:118
uint32_t get_t() const
Definition: mceliece.h:49
int get_degree() const
Definition: polyn_gf2m.cpp:230
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
std::string encode(const uint8_t der[], size_t length, const std::string &label, size_t width)
Definition: pem.cpp:43
secure_vector< uint8_t > get_contents()
Definition: der_enc.cpp:124
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:248
BER_Decoder & decode(bool &v)
Definition: ber_dec.cpp:376
uint32_t get_code_length() const
Definition: mceliece.h:50
DER_Encoder & end_cons()
Definition: der_enc.cpp:147
uint32_t get_message_word_bit_length() const
bool check_key(RandomNumberGenerator &rng, bool strong) const override
virtual OID get_oid() const
Definition: pk_keys.cpp:30
secure_vector< uint8_t > encode() const
Definition: polyn_gf2m.cpp:771
DER_Encoder & encode(bool b)
Definition: der_enc.cpp:216
size_t key_length() const override
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:121
BER_Decoder & end_cons()
Definition: ber_dec.cpp:272
McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator &rng, uint32_t ext_deg, uint32_t code_length, uint32_t t)
const McEliece_PublicKey & m_key
BER_Decoder start_cons(ASN1_Tag type_tag, ASN1_Tag class_tag=UNIVERSAL)
Definition: ber_dec.cpp:258
uint16_t gf2m
Definition: gf2m_small_m.h:20
Definition: alg_id.cpp:13
bool operator==(const McEliece_PrivateKey &other) const
bool operator==(const McEliece_PublicKey &other) const
size_t ceil_log2(T x)
Definition: bit_ops.h:106
McEliece_PrivateKey(RandomNumberGenerator &rng, size_t code_length, size_t t)
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:137
std::string algo_name() const override
Definition: mceliece.h:37
std::vector< uint8_t > public_key_bits() const override
size_t mceliece_work_factor(size_t n, size_t t)