Add KEM scheme for McEliece

4 files changed, 179 insertions, 21 deletions

diff --git a/src/lib/pubkey/mce/info.txt b/src/lib/pubkey/mce/info.txt
index 6c0da2199..bc4249422 100644
--- a/src/lib/pubkey/mce/info.txt
+++ b/src/lib/pubkey/mce/info.txt
@@ -6,6 +6,7 @@ gf2m_rootfind_dcmp.h
 gf2m_small_m.h
 goppa_code.h
 mce_overbeck_cca2.h
+mce_kem.h
 mceliece.h
 mceliece_key.h
 polyn_gf2m.h
diff --git a/src/lib/pubkey/mce/mce_kem.cpp b/src/lib/pubkey/mce/mce_kem.cpp
new file mode 100644
index 000000000..31dc2cfe2
--- /dev/null
+++ b/src/lib/pubkey/mce/mce_kem.cpp
@@ -0,0 +1,65 @@
+/**
+ * (C) 2014 cryptosource GmbH
+ * (C) 2014 Falko Strenzke [email protected]
+ *
+ * Distributed under the terms of the Botan license
+ *
+ */
+
+#include <botan/mce_kem.h>
+#include <botan/sha2_64.h>
+
+namespace Botan {
+
+McEliece_KEM_Encryptor::McEliece_KEM_Encryptor(const McEliece_PublicKey& public_key) :
+   m_raw_pub_op(public_key, public_key.get_code_length())
+   {
+   }
+
+std::pair<secure_vector<byte>, secure_vector<byte>>
+McEliece_KEM_Encryptor::encrypt(RandomNumberGenerator& rng)
+   {
+   const McEliece_PublicKey& key = m_raw_pub_op.get_key();
+   secure_vector<Botan::byte> plaintext((key.get_message_word_bit_length()+7)/8);
+   rng.randomize(&plaintext[0], plaintext.size() );
+
+   // unset unused bits in the last plaintext byte
+   u32bit used = key.get_message_word_bit_length() % 8;
+   if(used)
+      {
+      byte mask = (1 << used) - 1;
+      plaintext[plaintext.size() - 1] &= mask;
+      }
+
+   secure_vector<gf2m> err_pos = create_random_error_positions(key.get_code_length(), key.get_t(), rng);
+
+   mceliece_message_parts parts(err_pos, plaintext, key.get_code_length());
+   secure_vector<Botan::byte> message_and_error_input = parts.get_concat();
+
+   SHA_512 hash;
+   hash.update(message_and_error_input);
+   secure_vector<byte> sym_key = hash.final();
+   secure_vector<byte> ciphertext = m_raw_pub_op.encrypt(&message_and_error_input[0],
+                                                         message_and_error_input.size(), rng);
+
+   return std::make_pair(ciphertext, sym_key);
+   }
+
+
+McEliece_KEM_Decryptor::McEliece_KEM_Decryptor(const McEliece_PrivateKey& mce_key) :
+   m_raw_priv_op(mce_key)
+   {
+   }
+
+secure_vector<Botan::byte> McEliece_KEM_Decryptor::decrypt(const byte msg[], size_t msg_len)
+   {
+   secure_vector<Botan::byte> message_and_error = m_raw_priv_op.decrypt(&msg[0], msg_len );
+
+   SHA_512 hash;
+   hash.update(message_and_error);
+
+   secure_vector<byte> sym_key = hash.final();
+   return sym_key;
+   }
+
+}
diff --git a/src/lib/pubkey/mce/mce_kem.h b/src/lib/pubkey/mce/mce_kem.h
new file mode 100644
index 000000000..4e46a0fab
--- /dev/null
+++ b/src/lib/pubkey/mce/mce_kem.h
@@ -0,0 +1,45 @@
+/**
+ * (C) 2014 cryptosource GmbH
+ * (C) 2014 Falko Strenzke [email protected]
+ *
+ * Distributed under the terms of the Botan license
+ *
+ */
+
+#ifndef BOTAN_MCE_KEM_H__
+#define BOTAN_MCE_KEM_H__
+
+#include <botan/mceliece.h>
+#include <utility>
+
+namespace Botan {
+
+class BOTAN_DLL McEliece_KEM_Encryptor
+   {
+   public:
+      McEliece_KEM_Encryptor(const McEliece_PublicKey& public_key);
+
+      /**
+      * returns the pair (mceliece ciphertext, symmetric key)
+      */
+      std::pair<secure_vector<byte>, secure_vector<byte>> encrypt(RandomNumberGenerator& rng);
+
+   private:
+      McEliece_Public_Operation m_raw_pub_op;
+   };
+
+class BOTAN_DLL McEliece_KEM_Decryptor
+   {
+    public:
+      McEliece_KEM_Decryptor(const McEliece_PrivateKey& mce_key);
+
+      /**
+      * returns the derived 512-bit symmetric key
+      */
+      secure_vector<Botan::byte> decrypt(const byte msg[], size_t msg_len);
+   private:
+      McEliece_Private_Operation m_raw_priv_op;
+  };
+}
+
+#endif /* h-guard */
diff --git a/src/tests/test_mceliece.cpp b/src/tests/test_mceliece.cpp
index 8246e219b..dddf93b94 100644
--- a/src/tests/test_mceliece.cpp
+++ b/src/tests/test_mceliece.cpp
@@ -9,9 +9,11 @@
 #include <botan/auto_rng.h>
 #include <botan/hex.h>
 #include <iostream>
-#include <memory>
 
 #include <botan/mce_overbeck_cca2.h>
+#include <botan/mce_kem.h>
+
+#include <memory>
 
 using namespace Botan;
 
@@ -20,6 +22,8 @@ using namespace Botan;
 
 namespace {
 
+const size_t MCE_RUNS = 10;
+
 size_t test_mceliece_message_parts(RandomNumberGenerator& rng, size_t code_length, size_t error_weight)
    {
    secure_vector<gf2m> err_pos1 = create_random_error_positions(code_length, error_weight, rng);
@@ -49,7 +53,6 @@ size_t test_mceliece_message_parts(RandomNumberGenerator& rng, size_t code_lengt
    return 0;
    }
 
-
 size_t test_mceliece_overbeck(RandomNumberGenerator& rng, size_t code_length, size_t t )
    {
    McEliece_PrivateKey sk1(rng, code_length, t);
@@ -133,6 +136,58 @@ size_t test_mceliece_overbeck(RandomNumberGenerator& rng, size_t code_length, si
    return err_cnt;
    }
 
+size_t test_mceliece_kem(RandomNumberGenerator& rng, u32bit code_length, u32bit t)
+   {
+   size_t fails = 0;
+
+   McEliece_PrivateKey sk1(rng, code_length, t);
+   McEliece_PublicKey& pk1 = dynamic_cast<McEliece_PrivateKey&>(sk1);
+
+   const std::vector<byte> pk_enc = pk1.x509_subject_public_key();
+   const secure_vector<byte> sk_enc = sk1.pkcs8_private_key();
+
+   McEliece_PublicKey pk(pk_enc);
+   McEliece_PrivateKey sk(sk_enc);
+
+   if(pk1 != pk)
+      {
+      std::cout << "decoded McEliece public key differs from original one" << std::endl;
+      ++fails;
+      }
+
+   if(sk1 != sk)
+      {
+      std::cout << "decoded McEliece private key differs from original one" << std::endl;
+      ++fails;
+      }
+
+   if(!sk.check_key(rng, false))
+      {
+      std::cout << "error calling check key on McEliece key" << std::endl;
+      ++fails;
+      }
+
+   McEliece_KEM_Encryptor pub_op(pk);
+   McEliece_KEM_Decryptor priv_op(sk);
+
+   for(size_t i = 0; i != MCE_RUNS; i++)
+      {
+      const std::pair<secure_vector<byte>,secure_vector<byte> > ciphertext__sym_key = pub_op.encrypt(rng);
+      const secure_vector<byte>& ciphertext = ciphertext__sym_key.first;
+      const secure_vector<byte>& sym_key_encr = ciphertext__sym_key.second;
+
+      const secure_vector<byte> sym_key_decr = priv_op.decrypt(&ciphertext[0], ciphertext.size());
+
+      if(sym_key_encr != sym_key_decr)
+         {
+         std::cout << "mce KEM test failed, error during encryption/decryption" << std::endl;
+         ++fails;
+         }
+      }
+
+   return fails;
+   }
+
 size_t test_mceliece_raw(RandomNumberGenerator& rng, size_t code_length, size_t t)
    {
    McEliece_PrivateKey sk(rng, code_length, t);
@@ -142,7 +197,7 @@ size_t test_mceliece_raw(RandomNumberGenerator& rng, size_t code_length, size_t
    McEliece_Public_Operation pub_op(*p_pk, code_length );
    size_t err_cnt = 0;
 
-   for(size_t i = 0; i < 100; i++)
+   for(size_t i = 0; i != MCE_RUNS; i++)
       {
       secure_vector<byte> plaintext((p_pk->get_message_word_bit_length()+7)/8);
       rng.randomize(&plaintext[0], plaintext.size() - 1);
@@ -188,24 +243,6 @@ size_t test_mceliece()
    {
    AutoSeeded_RNG rng;
 
-
-   /*
-   size_t key_gen_loop_limit = 10000;
-   for(size_t i = 0; i < key_gen_loop_limit; i++)
-   {
-   if(i % 100 == 0)
-   {
-   std::cout << "max key gen test : iter " << i << " of " << key_gen_loop_limit << std::endl;
-   }
-   if( test_mceliece_overbeck(rng, 2048, 33))
-   {
-   std::cout << "error in overbeck test" << std::endl;
-   return 1;
-   }
-
-   }
-   */
-
    size_t  err_cnt = 0;
    size_t params__n__t_min_max[] = {
       256, 5, 15,
@@ -247,6 +284,16 @@ size_t test_mceliece()
 
          try
             {
+            err_cnt += test_mceliece_kem(rng, code_length, t);
+            }
+         catch(std::exception& e)
+            {
+            std::cout << e.what();
+            err_cnt++;
+            }
+
+         try
+            {
             // otherwise conversion not applicable because k=dimension would be too small
             if(code_length >= 2048)
                err_cnt += test_mceliece_overbeck(rng, code_length, t);