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