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