Merge pull request #286 from randombit/mce-cleanup

Cleanup and document McEliece implementation

1 files changed, 68 insertions, 105 deletions

diff --git a/src/lib/pubkey/mce/mceliece.cpp b/src/lib/pubkey/mce/mceliece.cpp
index 08b3f13a3..dd05b8212 100644
--- a/src/lib/pubkey/mce/mceliece.cpp
+++ b/src/lib/pubkey/mce/mceliece.cpp
@@ -9,164 +9,127 @@
  *
  */
 
+#include <botan/internal/mce_internal.h>
 #include <botan/mceliece.h>
-#include <botan/mceliece_key.h>
-#include <botan/internal/code_based_key_gen.h>
-#include <botan/polyn_gf2m.h>
-#include <botan/code_based_util.h>
-#include <botan/goppa_code.h>
+#include <botan/internal/code_based_util.h>
 #include <botan/internal/bit_ops.h>
+#include <set>
 
 namespace Botan {
 
 namespace {
 
-void concat_vectors(byte* x, const byte* a, const byte* b, u32bit dimension, u32bit codimension)
+secure_vector<byte> concat_vectors(const secure_vector<byte>& a, const secure_vector<byte>& b,
+                                   u32bit dimension, u32bit codimension)
    {
-   if(dimension % 8 == 0)
+   secure_vector<byte> x(bit_size_to_byte_size(dimension) + bit_size_to_byte_size(codimension));
+
+   const size_t final_bits = dimension % 8;
+
+   if(final_bits == 0)
       {
       const size_t dim_bytes = bit_size_to_byte_size(dimension);
-      copy_mem(x, a, dim_bytes);
-      copy_mem(x + dim_bytes, b, bit_size_to_byte_size(codimension));
+      copy_mem(&x[0], a.data(), dim_bytes);
+      copy_mem(&x[dim_bytes], b.data(), bit_size_to_byte_size(codimension));
       }
    else
       {
-      u32bit i, j, k, l;
-      i = dimension - 8 * (dimension/ 8);
-      j = 8 - i;
-      l = dimension / 8;
-      copy_mem(x, a, 1 * (dimension / 8));
-      x[l] = static_cast<byte>(a[l] & ((1 << i) - 1));
-
-      for(k = 0; k < codimension / 8; ++k)
+      copy_mem(&x[0], a.data(), (dimension / 8));
+      u32bit l = dimension / 8;
+      x[l] = static_cast<byte>(a[l] & ((1 << final_bits) - 1));
+
+      for(u32bit k = 0; k < codimension / 8; ++k)
          {
-         x[l] ^= static_cast<byte>(b[k] << i);
+         x[l] ^= static_cast<byte>(b[k] << final_bits);
          ++l;
-         x[l] = static_cast<byte>(b[k] >> j);
+         x[l] = static_cast<byte>(b[k] >> (8 - final_bits));
          }
-      x[l] ^= static_cast<byte>(b[k] << i);
+      x[l] ^= static_cast<byte>(b[codimension/8] << final_bits);
       }
+
+   return x;
    }
 
-std::vector<byte> mult_by_pubkey(const byte *cleartext,
-                                 std::vector<byte> const& public_matrix,
-                                 u32bit code_length, u32bit t)
+secure_vector<byte> mult_by_pubkey(const secure_vector<byte>& cleartext,
+                                   std::vector<byte> const& public_matrix,
+                                   u32bit code_length, u32bit t)
    {
-   std::vector<byte> ciphertext(code_length);
-   u32bit i, j;
-   u32bit ext_deg = ceil_log2(code_length);
-   u32bit codimension = ext_deg * t;
-   u32bit dimension = code_length - codimension;
-   std::vector<byte> cR(bit_size_to_32bit_size(codimension)* sizeof(u32bit));
+   const u32bit ext_deg = ceil_log2(code_length);
+   const u32bit codimension = ext_deg * t;
+   const u32bit dimension = code_length - codimension;
+   secure_vector<byte> cR(bit_size_to_32bit_size(codimension) * sizeof(u32bit));
 
    const byte* pt = public_matrix.data();
 
-   for(i = 0; i < dimension / 8; ++i)
+   for(size_t i = 0; i < dimension / 8; ++i)
       {
-      for(j = 0; j < 8; ++j)
+      for(size_t j = 0; j < 8; ++j)
          {
          if(cleartext[i] & (1 << j))
             {
             xor_buf(cR.data(), pt, cR.size());
             }
-         pt += bit_size_to_32bit_size(codimension) * sizeof(u32bit);
+         pt += cR.size();
          }
       }
 
-   for(j = 0; j < dimension % 8 ; ++j)
+   for(size_t i = 0; i < dimension % 8 ; ++i)
       {
-      if(cleartext[i] & (1 << j))
+      if(cleartext[dimension/8] & (1 << i))
          {
-         xor_buf(cR.data(), pt, bit_size_to_byte_size(codimension));
+         xor_buf(cR.data(), pt, cR.size());
          }
-      pt += bit_size_to_32bit_size(codimension) * sizeof(u32bit);
+      pt += cR.size();
       }
 
-   concat_vectors(ciphertext.data(), cleartext, cR.data(), dimension, codimension);
+   secure_vector<byte> ciphertext = concat_vectors(cleartext, cR, dimension, codimension);
+   ciphertext.resize((code_length+7)/8);
    return ciphertext;
    }
 
-}
-
-secure_vector<gf2m> create_random_error_positions(unsigned code_length,
-                                                  unsigned error_weight,
-                                                  RandomNumberGenerator& rng)
-   {
-   secure_vector<gf2m> result(error_weight);
-   gf2m i;
-   for(i = 0; i < result.size(); i++)
-      {
-      unsigned j;
-      char try_again = 0;
-      do
-         {
-         try_again = 0;
-         gf2m new_pos = random_code_element(code_length, rng);
-         for(j = 0; j < i; j++)
-            {
-            if(new_pos == result[j])
-               {
-               try_again = 1;
-               break;
-               }
-            }
-         result[i] = new_pos;
-         } while(try_again);
-      }
-   return result;
-   }
-
-McEliece_Private_Operation::McEliece_Private_Operation(const McEliece_PrivateKey& private_key)
-   :m_priv_key(private_key)
+secure_vector<byte> create_random_error_vector(unsigned code_length,
+                                               unsigned error_weight,
+                                               RandomNumberGenerator& rng)
    {
-   }
-
-secure_vector<byte> McEliece_Private_Operation::decrypt(const byte msg[], size_t msg_len)
-   {
-   secure_vector<gf2m> err_pos;
+   secure_vector<byte> result((code_length+7)/8);
 
-   secure_vector<byte> plaintext = mceliece_decrypt(
-      err_pos,
-      msg, msg_len,
-      m_priv_key
-      );
+   size_t bits_set = 0;
 
-   return mceliece_message_parts(err_pos, plaintext, m_priv_key.get_code_length()).get_concat();
-   }
+   while(bits_set < error_weight)
+      {
+      gf2m x = random_code_element(code_length, rng);
 
-McEliece_Public_Operation::McEliece_Public_Operation(const McEliece_PublicKey& public_key, u32bit the_code_length)
-   :m_pub_key(public_key),
-    m_code_length(the_code_length)
-   {}
+      const size_t byte_pos = x / 8, bit_pos = x % 8;
 
-secure_vector<byte> McEliece_Public_Operation::encrypt(const byte msg[], size_t msg_len, RandomNumberGenerator&)
-   {
-   mceliece_message_parts parts(msg, msg_len, m_pub_key.get_code_length());
-   secure_vector<gf2m> err_pos = parts.get_error_positions();
-   secure_vector<byte> message_word = parts.get_message_word();
-   secure_vector<byte> ciphertext((m_pub_key.get_code_length()+7)/8);
+      const byte mask = (1 << bit_pos);
 
+      if(result[byte_pos] & mask)
+         continue; // already set this bit
 
-   std::vector<byte> ciphertext_tmp = mceliece_encrypt( message_word,  m_pub_key.get_public_matrix(), err_pos, m_code_length);
+      result[byte_pos] |= mask;
+      bits_set++;
+      }
 
-   copy_mem(ciphertext.data(), ciphertext_tmp.data(), ciphertext.size());
-   return ciphertext;
+   return result;
    }
 
-std::vector<byte> mceliece_encrypt(const secure_vector<byte> & cleartext,
-                                   std::vector<byte> const& public_matrix,
-                                   const secure_vector<gf2m> & err_pos,
-                                   u32bit code_length)
+}
+
+void mceliece_encrypt(secure_vector<byte>& ciphertext_out,
+                      secure_vector<byte>& error_mask_out,
+                      const secure_vector<byte>& plaintext,
+                      const McEliece_PublicKey& key,
+                      RandomNumberGenerator& rng)
    {
-   std::vector<byte> ciphertext = mult_by_pubkey(cleartext.data(), public_matrix, code_length, err_pos.size());
+   secure_vector<byte> error_mask = create_random_error_vector(key.get_code_length(), key.get_t(), rng);
 
-   // flip t error positions
-   for(size_t i = 0; i < err_pos.size(); ++i)
-      {
-      ciphertext[err_pos[i] / 8] ^= (1 << (err_pos[i] % 8));
-      }
+   secure_vector<byte> ciphertext = mult_by_pubkey(plaintext, key.get_public_matrix(),
+                                                   key.get_code_length(), key.get_t());
 
-   return ciphertext;
+   ciphertext ^= error_mask;
+
+   ciphertext_out.swap(ciphertext);
+   error_mask_out.swap(error_mask);
    }
 
 }