Add an implementation of McEliece encryption based on HyMES

(https://www.rocq.inria.fr/secret/CBCrypto/index.php?pg=hymes).
The original version is LGPL but cryptsource GmbH has secured
permission to release it under a BSD license. Also includes the
Overbeck CCA2 message encoding scheme.

1 files changed, 281 insertions, 0 deletions

diff --git a/src/lib/pubkey/mce/mceliece_key.cpp b/src/lib/pubkey/mce/mceliece_key.cpp
new file mode 100644
index 000000000..71e0ec4e8
--- /dev/null
+++ b/src/lib/pubkey/mce/mceliece_key.cpp
@@ -0,0 +1,281 @@
+/**
+ * (C) Copyright Projet SECRET, INRIA, Rocquencourt
+ * (C) Bhaskar Biswas and  Nicolas Sendrier
+ *
+ * (C) 2014 cryptosource GmbH
+ * (C) 2014 Falko Strenzke [email protected]
+ *
+ * Distributed under the terms of the Botan license
+ *
+ */
+
+#include <botan/mceliece_key.h>
+#include <botan/internal/bit_ops.h>
+#include <botan/gf2m_small_m.h>
+#include <botan/mceliece.h>
+#include <botan/internal/code_based_key_gen.h>
+#include <botan/alg_id.h>
+#include <botan/der_enc.h>
+#include <botan/ber_dec.h>
+#include <botan/oids.h>
+
+namespace Botan {
+
+McEliece_PrivateKey::McEliece_PrivateKey(polyn_gf2m const& goppa_polyn,
+                                         std::vector<u32bit> const& parity_check_matrix_coeffs,
+                                         std::vector<polyn_gf2m> const& square_root_matrix,
+                                         std::vector<gf2m> const& inverse_support,
+                                         std::vector<byte> const& public_matrix) :
+   McEliece_PublicKey(public_matrix, goppa_polyn.get_degree(), inverse_support.size()),
+   m_g(goppa_polyn),
+   m_sqrtmod(square_root_matrix),
+   m_Linv(inverse_support),
+   m_coeffs(parity_check_matrix_coeffs),
+   m_codimension(ceil_log2(inverse_support.size()) * goppa_polyn.get_degree()),
+   m_dimension(inverse_support.size() - m_codimension)
+   {
+   };
+
+McEliece_PrivateKey::McEliece_PrivateKey(RandomNumberGenerator& rng, size_t code_length, size_t t)
+   {
+   u32bit ext_deg = ceil_log2(code_length);
+   *this = generate_mceliece_key(rng, ext_deg, code_length, t);
+   }
+
+unsigned McEliece_PublicKey::get_message_word_bit_length() const
+   {
+   u32bit codimension = ceil_log2(m_code_length) * m_t;
+   return m_code_length - codimension;
+   }
+
+AlgorithmIdentifier McEliece_PublicKey::algorithm_identifier() const
+   {
+   return AlgorithmIdentifier(get_oid(), std::vector<byte>());
+   }
+
+std::vector<byte> McEliece_PublicKey::x509_subject_public_key() const
+   {
+   // encode the public key
+   return unlock(DER_Encoder()
+                 .start_cons(SEQUENCE)
+                 .start_cons(SEQUENCE)
+                 .encode(static_cast<size_t>(get_code_length()))
+                 .encode(static_cast<size_t>(get_t()))
+                 .end_cons()
+                 .encode(m_public_matrix, OCTET_STRING)
+                 .end_cons()
+                 .get_contents());
+   }
+
+McEliece_PublicKey::McEliece_PublicKey(const McEliece_PublicKey & other) :
+   m_public_matrix(other.m_public_matrix),
+   m_t(other.m_t),
+   m_code_length(other.m_code_length)
+   {
+   }
+
+McEliece_PublicKey::McEliece_PublicKey(const std::vector<byte>& key_bits)
+   {
+   BER_Decoder dec(key_bits);
+   size_t n;
+   size_t t;
+   dec.start_cons(SEQUENCE)
+      .start_cons(SEQUENCE)
+      .decode(n)
+      .decode(t)
+      .end_cons()
+      .decode(m_public_matrix, OCTET_STRING)
+      .end_cons();
+   m_t = t;
+   m_code_length = n;
+   }
+
+secure_vector<byte> McEliece_PrivateKey::pkcs8_private_key() const
+   {
+   DER_Encoder enc;
+   enc.start_cons(SEQUENCE)
+      .start_cons(SEQUENCE)
+      .encode(static_cast<size_t>(get_code_length()))
+      .encode(static_cast<size_t>(get_t()))
+      .end_cons()
+      .encode(m_public_matrix, OCTET_STRING)
+      .encode(m_g.encode(), OCTET_STRING); // g as octet string
+   enc.start_cons(SEQUENCE);
+   for(u32bit i = 0; i < m_sqrtmod.size(); i++)
+      {
+      enc.encode(m_sqrtmod[i].encode(), OCTET_STRING);
+      }
+   enc.end_cons();
+   secure_vector<byte> enc_support;
+   for(u32bit i = 0; i < m_Linv.size(); i++)
+      {
+      enc_support.push_back(m_Linv[i] >> 8);
+      enc_support.push_back(m_Linv[i]);
+      }
+   enc.encode(enc_support, OCTET_STRING);
+   secure_vector<byte> enc_H;
+   for(u32bit i = 0; i < m_coeffs.size(); i++)
+      {
+      enc_H.push_back(m_coeffs[i] >> 24);
+      enc_H.push_back(m_coeffs[i] >> 16);
+      enc_H.push_back(m_coeffs[i] >> 8);
+      enc_H.push_back(m_coeffs[i]);
+      }
+   enc.encode(enc_H, OCTET_STRING);
+   enc.end_cons();
+   return enc.get_contents();
+   }
+
+bool McEliece_PrivateKey::check_key(RandomNumberGenerator& rng, bool) const
+   {
+   const McEliece_PublicKey* p_pk = dynamic_cast<const McEliece_PublicKey*>(this);
+
+   McEliece_Private_Operation priv_op(*this);
+   McEliece_Public_Operation pub_op(*p_pk, p_pk->get_code_length() );
+
+   secure_vector<byte> plaintext((p_pk->get_message_word_bit_length()+7)/8);
+   rng.randomize(&plaintext[0], plaintext.size() - 1);
+   secure_vector<gf2m> err_pos = create_random_error_positions(p_pk->get_code_length(), p_pk->get_t(), rng);
+
+   mceliece_message_parts parts(err_pos, plaintext, p_pk->get_code_length());
+   secure_vector<byte> message_and_error_input = parts.get_concat();
+   secure_vector<byte> ciphertext = pub_op.encrypt(&message_and_error_input[0], message_and_error_input.size(), rng);
+   secure_vector<byte> message_and_error_output = priv_op.decrypt(&ciphertext[0], ciphertext.size() );
+
+   return (message_and_error_input == message_and_error_output);
+   }
+
+McEliece_PrivateKey::McEliece_PrivateKey(const secure_vector<byte>& key_bits)
+   {
+   size_t n, t;
+   secure_vector<byte> g_enc;
+   BER_Decoder dec_base(key_bits);
+   BER_Decoder dec = dec_base.start_cons(SEQUENCE)
+      .start_cons(SEQUENCE)
+      .decode(n)
+      .decode(t)
+      .end_cons()
+      .decode(m_public_matrix, OCTET_STRING)
+      .decode(g_enc, OCTET_STRING);
+
+   if(t == 0 || n == 0)
+      throw Decoding_Error("invalid McEliece parameters");
+
+   u32bit ext_deg = ceil_log2(n);
+   m_code_length = n;
+   m_t = t;
+   m_codimension = (ext_deg * t);
+   m_dimension = (n - m_codimension);
+
+   std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field(new gf2m_small_m::Gf2m_Field(ext_deg));
+   m_g = polyn_gf2m(g_enc, sp_field);
+   if(m_g.get_degree() != static_cast<int>(t))
+      {
+      throw Decoding_Error("degree of decoded Goppa polynomial is incorrect");
+      }
+   BER_Decoder dec2 = dec.start_cons(SEQUENCE);
+   for(u32bit i = 0; i < t/2; i++)
+      {
+      secure_vector<byte> sqrt_enc;
+      dec2.decode(sqrt_enc, OCTET_STRING);
+      while(sqrt_enc.size() < (t*2))
+         {
+         // ensure that the length is always t
+         sqrt_enc.push_back(0);
+         sqrt_enc.push_back(0);
+         }
+      if(sqrt_enc.size() != t*2)
+         {
+         throw Decoding_Error("length of square root polynomial entry is too large");
+         }
+      m_sqrtmod.push_back(polyn_gf2m(sqrt_enc, sp_field));
+      }
+   secure_vector<byte> enc_support;
+   BER_Decoder dec3 = dec2.end_cons()
+      .decode(enc_support, OCTET_STRING);
+   if(enc_support.size() % 2)
+      {
+      throw Decoding_Error("encoded support has odd length");
+      }
+   if(enc_support.size() / 2 != n)
+      {
+      throw Decoding_Error("encoded support has length different from code length");
+      }
+   for(u32bit i = 0; i < n*2; i+=2)
+      {
+      gf2m el = (enc_support[i] << 8) |  enc_support[i+1];
+      m_Linv.push_back(el);
+      }
+   secure_vector<byte> enc_H;
+   dec3.decode(enc_H, OCTET_STRING)
+      .end_cons();
+   if(enc_H.size() % 4)
+      {
+      throw Decoding_Error("encoded parity check matrix has length which is not a multiple of four");
+      }
+   if(enc_H.size()/4 != bit_size_to_32bit_size(m_codimension) * m_code_length )
+      {
+      throw Decoding_Error("encoded parity check matrix has wrong length");
+      }
+
+   for(u32bit i = 0; i < enc_H.size(); i+=4)
+      {
+      u32bit coeff = (enc_H[i] << 24) | (enc_H[i+1] << 16) | (enc_H[i+2] << 8) | enc_H[i+3];
+      m_coeffs.push_back(coeff);
+      }
+
+   }
+
+
+bool McEliece_PrivateKey::operator==(const McEliece_PrivateKey & other) const
+   {
+   if(*static_cast<const McEliece_PublicKey*>(this) != *static_cast<const McEliece_PublicKey*>(&other))
+      {
+      return false;
+      }
+   if(m_g != other.m_g)
+      {
+      return false;
+      }
+
+   if( m_sqrtmod != other.m_sqrtmod)
+      {
+      return false;
+      }
+   if( m_Linv != other.m_Linv)
+      {
+      return false;
+      }
+   if( m_coeffs != other.m_coeffs)
+      {
+      return false;
+      }
+
+   if(m_codimension != other.m_codimension || m_dimension != other.m_dimension)
+      {
+      return false;
+      }
+
+   return true;
+   }
+
+bool McEliece_PublicKey::operator==(const McEliece_PublicKey& other) const
+   {
+   if(m_public_matrix != other.m_public_matrix)
+      {
+      return false;
+      }
+   if(m_t != other.m_t )
+      {
+      return false;
+      }
+   if( m_code_length != other.m_code_length)
+      {
+      return false;
+      }
+   return true;
+   }
+
+}
+
+