McEliece cleanups

Remove and consolidate various headers

Reduce memory usage of GF2m_Field by sharing the log and exponent
tables across all instances of a particular word size.

Remove McEliece_Public_Operation and McEliece_Private_Operation which
were difficult to use safely. Instead only the KEM operations are exposed.

Add McEliece_PublicKey::random_plaintext_element

Add command line `mce` tool and some McEliece documentation

Convert the speed program to check McEliece keys of the suggested size

Add McEliece KATs for both key generation and KEM

Fix HMAC_DRBG constructor which derefed a pointer before its time

25 files changed, 986 insertions, 1201 deletions

diff --git a/src/lib/pubkey/mce/binary_matrix.cpp b/src/lib/pubkey/mce/binary_matrix.cpp
deleted file mode 100644
index 45c9aab13..000000000
--- a/src/lib/pubkey/mce/binary_matrix.cpp
+++ /dev/null
@@ -1,95 +0,0 @@
-/**
- * (C) Copyright Projet SECRET, INRIA, Rocquencourt
- * (C) Bhaskar Biswas and  Nicolas Sendrier
- *
- * (C) 2014 cryptosource GmbH
- * (C) 2014 Falko Strenzke [email protected]
- *
- * Botan is released under the Simplified BSD License (see license.txt)
- *
- */
-
-#include <botan/internal/binary_matrix.h>
-
-namespace Botan {
-
-binary_matrix::binary_matrix (u32bit rown, u32bit coln)
-   {
-   m_coln = coln;
-   m_rown = rown;
-   m_rwdcnt = (1 + (m_coln - 1) / BITS_PER_U32);
-   m_elem = std::vector<u32bit>(m_rown * m_rwdcnt);
-   }
-
-void binary_matrix::row_xor(u32bit a, u32bit b)
-   {
-   u32bit i;
-   for(i=0;i<m_rwdcnt;i++)
-      {
-      m_elem[a*m_rwdcnt+i]^=m_elem[b*m_rwdcnt+i];
-      }
-   }
-
-//the matrix is reduced from LSB...(from right)
-secure_vector<int> binary_matrix::row_reduced_echelon_form()
-   {
-   u32bit i, failcnt, findrow, max=m_coln - 1;
-
-   secure_vector<int> perm(m_coln);
-   for(i=0;i<m_coln;i++)
-      {
-      perm[i]=i;//initialize permutation.
-      }
-   failcnt = 0;
-
-   for(i=0;i<m_rown;i++,max--)
-      {
-      findrow=0;
-      for(u32bit j=i;j<m_rown;j++)
-         {
-         if(coef(j,max))
-            {
-            if (i!=j)//not needed as ith row is 0 and jth row is 1.
-               row_xor(i,j);//xor to the row.(swap)?
-            findrow=1;
-            break;
-            }//largest value found (end if)
-         }
-
-      if(!findrow)//if no row with a 1 found then swap last column and the column with no 1 down.
-         {
-         perm[m_coln - m_rown - 1 - failcnt] = max;
-         failcnt++;
-         if (!max)
-            {
-            //CSEC_FREE_MEM_CHK_SET_NULL(*p_perm);
-            //CSEC_THR_RETURN();
-            perm.resize(0);
-            }
-         i--;
-         }
-      else
-         {
-         perm[i+m_coln - m_rown] = max;
-         for(u32bit j=i+1;j<m_rown;j++)//fill the column downwards with 0's
-            {
-            if(coef(j,(max)))
-               {
-               row_xor(j,i);//check the arg. order.
-               }
-            }
-
-         for(int j=i-1;j>=0;j--)//fill the column with 0's upwards too.
-            {
-            if(coef(j,(max)))
-               {
-               row_xor(j,i);
-               }
-            }
-         }
-      }//end for(i)
-   return perm;
-   }
-
-
-} // end namespace Botan
diff --git a/src/lib/pubkey/mce/binary_matrix.h b/src/lib/pubkey/mce/binary_matrix.h
deleted file mode 100644
index feb44632f..000000000
--- a/src/lib/pubkey/mce/binary_matrix.h
+++ /dev/null
@@ -1,60 +0,0 @@
-/**
- * (C) Copyright Projet SECRET, INRIA, Rocquencourt
- * (C) Bhaskar Biswas and  Nicolas Sendrier
- *
- * (C) 2014 cryptosource GmbH
- * (C) 2014 Falko Strenzke [email protected]
- *
- * Botan is released under the Simplified BSD License (see license.txt)
- *
- */
-
-#ifndef BOTAN_BINARY_MATRIX_H__
-#define BOTAN_BINARY_MATRIX_H__
-
-#include <botan/secmem.h>
-
-namespace Botan {
-
-#define BITS_PER_U32 (8 * sizeof (u32bit))
-
-struct binary_matrix
-   {
-   public:
-      binary_matrix(u32bit m_rown, u32bit m_coln);
-
-      void row_xor(u32bit a, u32bit b);
-      secure_vector<int> row_reduced_echelon_form();
-
-      /**
-      * return the coefficient out of F_2
-      */
-      u32bit coef(u32bit i, u32bit j)
-         {
-         return (m_elem[(i) * m_rwdcnt + (j) / BITS_PER_U32] >> (j % BITS_PER_U32)) & 1;
-         };
-
-      void set_coef_to_one(u32bit i, u32bit j)
-         {
-         m_elem[(i) * m_rwdcnt + (j) / BITS_PER_U32] |= (1UL << ((j) % BITS_PER_U32)) ;
-         };
-
-      void toggle_coeff(u32bit i, u32bit j)
-         {
-         m_elem[(i) * m_rwdcnt + (j) / BITS_PER_U32] ^= (1UL << ((j) % BITS_PER_U32)) ;
-         }
-
-      void set_to_zero()
-         {
-         zeroise(m_elem);
-         }
-
-      u32bit m_rown;  // number of rows.
-      u32bit m_coln; // number of columns.
-      u32bit m_rwdcnt; // number of words in a row
-      std::vector<u32bit> m_elem;
-   };
-
-}
-
-#endif
diff --git a/src/lib/pubkey/mce/code_based_key_gen.cpp b/src/lib/pubkey/mce/code_based_key_gen.cpp
index a3749abef..44b1cb4d6 100644
--- a/src/lib/pubkey/mce/code_based_key_gen.cpp
+++ b/src/lib/pubkey/mce/code_based_key_gen.cpp
@@ -9,26 +9,139 @@
  *
  */
 
-#include <botan/internal/code_based_key_gen.h>
-#include <botan/code_based_util.h>
-#include <botan/gf2m_rootfind_dcmp.h>
-#include <botan/internal/binary_matrix.h>
+#include <botan/mceliece.h>
+#include <botan/internal/code_based_util.h>
 #include <botan/loadstor.h>
-#include <botan/polyn_gf2m.h>
 
 namespace Botan {
 
 namespace {
 
+struct binary_matrix
+   {
+   public:
+      binary_matrix(u32bit m_rown, u32bit m_coln);
+
+      void row_xor(u32bit a, u32bit b);
+      secure_vector<int> row_reduced_echelon_form();
+
+      /**
+      * return the coefficient out of F_2
+      */
+      u32bit coef(u32bit i, u32bit j)
+         {
+         return (m_elem[(i) * m_rwdcnt + (j) / 32] >> (j % 32)) & 1;
+         };
+
+      void set_coef_to_one(u32bit i, u32bit j)
+         {
+         m_elem[(i) * m_rwdcnt + (j) / 32] |= (static_cast<u32bit>(1) << ((j) % 32)) ;
+         };
+
+      void toggle_coeff(u32bit i, u32bit j)
+         {
+         m_elem[(i) * m_rwdcnt + (j) / 32] ^= (static_cast<u32bit>(1) << ((j) % 32)) ;
+         }
+
+      void set_to_zero()
+         {
+         zeroise(m_elem);
+         }
+
+      //private:
+      u32bit m_rown;  // number of rows.
+      u32bit m_coln; // number of columns.
+      u32bit m_rwdcnt; // number of words in a row
+      std::vector<u32bit> m_elem;
+   };
+
+binary_matrix::binary_matrix (u32bit rown, u32bit coln)
+   {
+   m_coln = coln;
+   m_rown = rown;
+   m_rwdcnt = 1 + ((m_coln - 1) / 32);
+   m_elem = std::vector<u32bit>(m_rown * m_rwdcnt);
+   }
+
+void binary_matrix::row_xor(u32bit a, u32bit b)
+   {
+   u32bit i;
+   for(i=0;i<m_rwdcnt;i++)
+      {
+      m_elem[a*m_rwdcnt+i]^=m_elem[b*m_rwdcnt+i];
+      }
+   }
+
+//the matrix is reduced from LSB...(from right)
+secure_vector<int> binary_matrix::row_reduced_echelon_form()
+   {
+   u32bit i, failcnt, findrow, max=m_coln - 1;
+
+   secure_vector<int> perm(m_coln);
+   for(i=0;i<m_coln;i++)
+      {
+      perm[i]=i;//initialize permutation.
+      }
+   failcnt = 0;
+
+   for(i=0;i<m_rown;i++,max--)
+      {
+      findrow=0;
+      for(u32bit j=i;j<m_rown;j++)
+         {
+         if(coef(j,max))
+            {
+            if (i!=j)//not needed as ith row is 0 and jth row is 1.
+               row_xor(i,j);//xor to the row.(swap)?
+            findrow=1;
+            break;
+            }//largest value found (end if)
+         }
+
+      if(!findrow)//if no row with a 1 found then swap last column and the column with no 1 down.
+         {
+         perm[m_coln - m_rown - 1 - failcnt] = max;
+         failcnt++;
+         if (!max)
+            {
+            //CSEC_FREE_MEM_CHK_SET_NULL(*p_perm);
+            //CSEC_THR_RETURN();
+            perm.resize(0);
+            }
+         i--;
+         }
+      else
+         {
+         perm[i+m_coln - m_rown] = max;
+         for(u32bit j=i+1;j<m_rown;j++)//fill the column downwards with 0's
+            {
+            if(coef(j,(max)))
+               {
+               row_xor(j,i);//check the arg. order.
+               }
+            }
+
+         for(int j=i-1;j>=0;j--)//fill the column with 0's upwards too.
+            {
+            if(coef(j,(max)))
+               {
+               row_xor(j,i);
+               }
+            }
+         }
+      }//end for(i)
+   return perm;
+   }
+
 void randomize_support(u32bit n, std::vector<gf2m> & L, RandomNumberGenerator & rng)
    {
    unsigned int i, j;
-   gf2m_small_m::gf2m tmp;
+   gf2m tmp;
 
    for (i = 0; i < n; ++i)
       {
 
-      gf2m_small_m::gf2m rnd;
+      gf2m rnd;
       rng.randomize(reinterpret_cast<byte*>(&rnd), sizeof(rnd));
       j = rnd % n; // no rejection sampling, but for useful code-based parameters with n <= 13 this seem tolerable
 
@@ -38,14 +151,14 @@ void randomize_support(u32bit n, std::vector<gf2m> & L, RandomNumberGenerator &
       }
    }
 
-std::unique_ptr<binary_matrix> generate_R(std::vector<gf2m> &L, polyn_gf2m* g, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field, u32bit code_length, u32bit t )
+std::unique_ptr<binary_matrix> generate_R(std::vector<gf2m> &L, polyn_gf2m* g, std::shared_ptr<GF2m_Field> sp_field, u32bit code_length, u32bit t )
    {
    //L- Support
    //t- Number of errors
    //n- Length of the Goppa code
    //m- The extension degree of the GF
    //g- The generator polynomial.
-   gf2m_small_m::gf2m x,y;
+   gf2m x,y;
    u32bit i,j,k,r,n;
    std::vector<int> Laux(code_length);
    n=code_length;
@@ -112,7 +225,7 @@ McEliece_PrivateKey generate_mceliece_key( RandomNumberGenerator & rng, u32bit e
       {
       throw Invalid_Argument("invalid McEliece parameters");
       }
-   std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field ( new Gf2m_Field(ext_deg ));
+   std::shared_ptr<GF2m_Field> sp_field ( new GF2m_Field(ext_deg ));
 
    //pick the support.........
    std::vector<gf2m> L(code_length);
diff --git a/src/lib/pubkey/mce/code_based_key_gen.h b/src/lib/pubkey/mce/code_based_key_gen.h
deleted file mode 100644
index 6764e13d6..000000000
--- a/src/lib/pubkey/mce/code_based_key_gen.h
+++ /dev/null
@@ -1,26 +0,0 @@
-/**
- * (C) Copyright Projet SECRET, INRIA, Rocquencourt
- * (C) Bhaskar Biswas and  Nicolas Sendrier
- *
- * (C) 2014 cryptosource GmbH
- * (C) 2014 Falko Strenzke [email protected]
- *
- * Botan is released under the Simplified BSD License (see license.txt)
- *
- */
-
-#ifndef BOTAN_CODE_BASED_KEY_GEN_H__
-#define BOTAN_CODE_BASED_KEY_GEN_H__
-
-#include <botan/mceliece_key.h>
-
-namespace Botan {
-
-McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator &rng,
-                                          u32bit ext_deg,
-                                          u32bit code_length,
-                                          u32bit t);
-
-}
-
-#endif
diff --git a/src/lib/pubkey/mce/code_based_util.h b/src/lib/pubkey/mce/code_based_util.h
index 6b567dbff..a959ad0d3 100644
--- a/src/lib/pubkey/mce/code_based_util.h
+++ b/src/lib/pubkey/mce/code_based_util.h
@@ -13,6 +13,7 @@
 #define BOTAN_CODE_BASED_UTIL_H__
 
 #include <botan/gf2m_small_m.h>
+#include <stdexcept>
 
 namespace Botan {
 
@@ -28,18 +29,18 @@ u16bit expand_mask_16bit(T tst)
    return ~(result - 1);
    }
 
-inline gf2m_small_m::gf2m gray_to_lex(gf2m_small_m::gf2m gray)
+inline gf2m gray_to_lex(gf2m gray)
    {
-   gf2m_small_m::gf2m result = gray ^ (gray>>8);
+   gf2m result = gray ^ (gray >> 8);
    result ^= (result >> 4);
    result ^= (result >> 2);
    result ^= (result >> 1);
    return result;
    }
 
-inline gf2m_small_m::gf2m lex_to_gray(gf2m_small_m::gf2m lex)
+inline gf2m lex_to_gray(gf2m lex)
    {
-   return (lex>>1) ^ lex;
+   return (lex >> 1) ^ lex;
    }
 
 inline u32bit bit_size_to_byte_size(u32bit bit_size)
diff --git a/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp b/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp
index 2d4f06130..d23d05172 100644
--- a/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp
+++ b/src/lib/pubkey/mce/gf2m_rootfind_dcmp.cpp
@@ -6,314 +6,307 @@
  *
  */
 
-#include <botan/gf2m_rootfind_dcmp.h>
-#include <botan/gf2m_small_m.h>
+#include <botan/polyn_gf2m.h>
 #include <botan/internal/bit_ops.h>
-#include <botan/code_based_util.h>
+#include <botan/internal/code_based_util.h>
 
-namespace Botan
-{
+namespace Botan {
 
 namespace {
 
-  u32bit patch_root_array(
-    gf2m* res_root_arr,
-    u32bit res_root_arr_len,
-    u32bit root_pos)
-  {
-    volatile u32bit i;
-    volatile gf2m patch_elem = 0x01;
-    volatile gf2m cond_mask = (root_pos == res_root_arr_len);
-    cond_mask = expand_mask_16bit(cond_mask);
-    cond_mask = ~cond_mask; /* now cond = 1 if not enough roots */
-    patch_elem &= cond_mask;
-    for(i = 0; i < res_root_arr_len; i++)
-    {
+u32bit patch_root_array(gf2m* res_root_arr,
+                        u32bit res_root_arr_len,
+                        u32bit root_pos)
+   {
+   volatile u32bit i;
+   volatile gf2m patch_elem = 0x01;
+   volatile gf2m cond_mask = (root_pos == res_root_arr_len);
+   cond_mask = expand_mask_16bit(cond_mask);
+   cond_mask = ~cond_mask; /* now cond = 1 if not enough roots */
+   patch_elem &= cond_mask;
+   for(i = 0; i < res_root_arr_len; i++)
+      {
 
       gf2m masked_patch_elem = (patch_elem++) & cond_mask;
       res_root_arr[i] ^= masked_patch_elem++;
-    }
-    return res_root_arr_len;
-  }
-
-struct gf2m_decomp_rootfind_state
-{
-    gf2m_decomp_rootfind_state(const polyn_gf2m & p_polyn, u32bit code_length);
-
-  void calc_LiK(const polyn_gf2m & sigma);
-  gf2m calc_Fxj_j_neq_0( const polyn_gf2m & sigma, gf2m j_gray);
-  void calc_next_Aij();
-  void calc_Ai_zero(const polyn_gf2m & sigma);
-  secure_vector<gf2m> find_roots(const polyn_gf2m & sigma);
-   u32bit get_code_length() const { return code_length; };
-    u32bit code_length;
-  secure_vector<gf2m> m_Lik; // size is outer_summands * m
-  secure_vector<gf2m> m_Aij; // ...
-  u32bit m_outer_summands;
-  gf2m m_j;
-  gf2m m_j_gray;
-  gf2m m_sigma_3_l;
-  gf2m m_sigma_3_neq_0_mask;
-} ;
-
+      }
+   return res_root_arr_len;
+   }
+
+class gf2m_decomp_rootfind_state
+   {
+   public:
+      gf2m_decomp_rootfind_state(const polyn_gf2m & p_polyn, u32bit code_length);
+
+      void calc_LiK(const polyn_gf2m & sigma);
+      gf2m calc_Fxj_j_neq_0( const polyn_gf2m & sigma, gf2m j_gray);
+      void calc_next_Aij();
+      void calc_Ai_zero(const polyn_gf2m & sigma);
+      secure_vector<gf2m> find_roots(const polyn_gf2m & sigma);
+      u32bit get_code_length() const { return code_length; };
+      u32bit code_length;
+      secure_vector<gf2m> m_Lik; // size is outer_summands * m
+      secure_vector<gf2m> m_Aij; // ...
+      u32bit m_outer_summands;
+      gf2m m_j;
+      gf2m m_j_gray;
+      gf2m m_sigma_3_l;
+      gf2m m_sigma_3_neq_0_mask;
+   };
 
 /*
- * !! Attention: assumes gf2m is 16bit !!
- */
+* !! Attention: assumes gf2m is 16bit !!
+*/
 #if 0
 gf2m brootf_decomp__gray_to_lex(gf2m gray)
-{
-  static_assert(sizeof(gf2m) == 2, "Expected size");
-  gf2m result = gray ^ (gray>>8);
-  result ^= (result >> 4);
-  result ^= (result >> 2);
-  result ^= (result >> 1);
-  return result;
-}
+   {
+   static_assert(sizeof(gf2m) == 2, "Expected size");
+   gf2m result = gray ^ (gray>>8);
+   result ^= (result >> 4);
+   result ^= (result >> 2);
+   result ^= (result >> 1);
+   return result;
+   }
 #endif
 
 /**
- * calculates ceil((t-4)/5) = outer_summands - 1
- */
+* calculates ceil((t-4)/5) = outer_summands - 1
+*/
 u32bit brootf_decomp__calc_sum_limit(u32bit t)
-{
-  u32bit result;
-  if(t < 4)
-  {
-    return 0;
-  }
-  result = t - 4;
-  result += 4;
-  result /= 5;
-  return result;
-}
+   {
+   u32bit result;
+   if(t < 4)
+      {
+      return 0;
+      }
+   result = t - 4;
+   result += 4;
+   result /= 5;
+   return result;
+   }
+
 }
 
 secure_vector<gf2m> find_roots_gf2m_decomp(const polyn_gf2m & polyn, u32bit code_length)
-{
-  gf2m_decomp_rootfind_state state(polyn, code_length);
-  return state.find_roots(polyn);
-
-}
+   {
+   gf2m_decomp_rootfind_state state(polyn, code_length);
+   return state.find_roots(polyn);
+   }
+
+gf2m_decomp_rootfind_state::gf2m_decomp_rootfind_state(const polyn_gf2m & polyn, u32bit the_code_length) :
+   code_length(the_code_length)
+   {
+   gf2m coeff_3;
+   gf2m coeff_head;
+   std::shared_ptr<GF2m_Field> sp_field = polyn.get_sp_field();
+   int deg_sigma = polyn.get_degree();
+   if(deg_sigma <= 3)
+      {
+      throw std::exception();
+      }
+   this->m_j = 0;
+   coeff_3 = polyn.get_coef( 3);
+   coeff_head = polyn.get_coef( deg_sigma); /* dummy value for SCA CM */
+   if(coeff_3 != 0)
+      {
+      this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_3);
+      this->m_sigma_3_neq_0_mask = 0xFFFF;
+      }
+   else
+      {
+      // dummy value needed for timing countermeasure
+      this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_head);
+      this->m_sigma_3_neq_0_mask = 0 ;
+      }
 
-gf2m_decomp_rootfind_state::gf2m_decomp_rootfind_state(const polyn_gf2m & polyn, u32bit the_code_length)
-  :code_length(the_code_length)
-{
-
-  gf2m coeff_3;
-  gf2m coeff_head;
-  std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = polyn.get_sp_field();
-  int deg_sigma = polyn.get_degree();
-  if(deg_sigma <= 3)
-  {
-    throw std::exception();
-  }
-  this->m_j = 0;
-  coeff_3 = polyn.get_coef( 3);
-  coeff_head = polyn.get_coef( deg_sigma); /* dummy value for SCA CM */
-  if(coeff_3 != 0)
-  {
-    this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_3);
-    this->m_sigma_3_neq_0_mask = 0xFFFF;
-  }
-  else
-  {
-    // dummy value needed for timing countermeasure
-    this->m_sigma_3_l = sp_field->gf_l_from_n(coeff_head);
-    this->m_sigma_3_neq_0_mask = 0 ;
-  }
-
-  this->m_outer_summands =  1 + brootf_decomp__calc_sum_limit(deg_sigma);
-  this->m_Lik.resize(this->m_outer_summands * sp_field->get_extension_degree());
-  this->m_Aij.resize(this->m_outer_summands);
-}
+   this->m_outer_summands =  1 + brootf_decomp__calc_sum_limit(deg_sigma);
+   this->m_Lik.resize(this->m_outer_summands * sp_field->get_extension_degree());
+   this->m_Aij.resize(this->m_outer_summands);
+   }
 
 void gf2m_decomp_rootfind_state::calc_Ai_zero(const polyn_gf2m & sigma)
-{
-  u32bit i;
-  /*
+   {
+   u32bit i;
+   /*
    * this function assumes this the first gray code element is zero
    */
-  for(i = 0; i < this->m_outer_summands; i++)
-  {
-    this->m_Aij[i] = sigma.get_coef(5*i);
-  }
-  this->m_j = 0;
-  this->m_j_gray = 0;
-}
+   for(i = 0; i < this->m_outer_summands; i++)
+      {
+      this->m_Aij[i] = sigma.get_coef(5*i);
+      }
+   this->m_j = 0;
+   this->m_j_gray = 0;
+   }
 
 void gf2m_decomp_rootfind_state::calc_next_Aij()
-{
-  /*
+   {
+   /*
    * upon function entry, we have in the state j, Aij.
    * first thing, we declare Aij Aij_minusone and increase j.
    * Case j=0 upon function entry also included, then Aij contains A_{i,j=0}.
    */
-  u32bit i;
-  gf2m diff, new_j_gray;
-  u32bit Lik_pos_base;
-
-  this->m_j++;
-
-  new_j_gray =  lex_to_gray(this->m_j);
-
-  if(this->m_j & 1)  /* half of the times */
-  {
-    Lik_pos_base = 0;
-  }
-  else if(this->m_j & 2) /* one quarter of the times */
-  {
-    Lik_pos_base = this->m_outer_summands;
-  }
-  else if( this->m_j & 4) /* one eighth of the times */
-  {
-    Lik_pos_base = this->m_outer_summands * 2;
-  }
-  else if( this->m_j & 8) /* one sixteenth of the times */
-  {
-    Lik_pos_base = this->m_outer_summands * 3;
-  }
-  else if( this->m_j & 16) /* ... */
-  {
-    Lik_pos_base = this->m_outer_summands * 4;
-  }
-  else
-  {
-    gf2m delta_offs = 5;
-    diff = this->m_j_gray ^ new_j_gray;
-    while(((static_cast<gf2m>(1) << delta_offs) & diff) == 0)
-    {
-      delta_offs++;
-
-    }
-    Lik_pos_base = delta_offs * this->m_outer_summands;
-  }
-  this->m_j_gray = new_j_gray;
-
-  i = 0;
-  for(; i < this->m_outer_summands; i++)
-  {
-    this->m_Aij[i] ^= this->m_Lik[Lik_pos_base + i];
-  }
+   u32bit i;
+   gf2m diff, new_j_gray;
+   u32bit Lik_pos_base;
+
+   this->m_j++;
+
+   new_j_gray =  lex_to_gray(this->m_j);
+
+   if(this->m_j & 1)  /* half of the times */
+      {
+      Lik_pos_base = 0;
+      }
+   else if(this->m_j & 2) /* one quarter of the times */
+      {
+      Lik_pos_base = this->m_outer_summands;
+      }
+   else if( this->m_j & 4) /* one eighth of the times */
+      {
+      Lik_pos_base = this->m_outer_summands * 2;
+      }
+   else if( this->m_j & 8) /* one sixteenth of the times */
+      {
+      Lik_pos_base = this->m_outer_summands * 3;
+      }
+   else if( this->m_j & 16) /* ... */
+      {
+      Lik_pos_base = this->m_outer_summands * 4;
+      }
+   else
+      {
+      gf2m delta_offs = 5;
+      diff = this->m_j_gray ^ new_j_gray;
+      while(((static_cast<gf2m>(1) << delta_offs) & diff) == 0)
+         {
+         delta_offs++;
+
+         }
+      Lik_pos_base = delta_offs * this->m_outer_summands;
+      }
+   this->m_j_gray = new_j_gray;
+
+   i = 0;
+   for(; i < this->m_outer_summands; i++)
+      {
+      this->m_Aij[i] ^= this->m_Lik[Lik_pos_base + i];
+      }
+
+   }
 
-}
 void gf2m_decomp_rootfind_state::calc_LiK(const polyn_gf2m & sigma)
-{
-  std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = sigma.get_sp_field();
-  u32bit i, k, d;
-  d = sigma.get_degree();
-  for(k = 0; k < sp_field->get_extension_degree(); k++)
-  {
-    u32bit Lik_pos_base = k * this->m_outer_summands;
-    gf2m alpha_l_k_tt2_ttj[4];
-    alpha_l_k_tt2_ttj[0] = sp_field->gf_l_from_n(static_cast<gf2m>(1) << k);
-    alpha_l_k_tt2_ttj[1] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[0], alpha_l_k_tt2_ttj[0]);
-    alpha_l_k_tt2_ttj[2] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[1],alpha_l_k_tt2_ttj[1] );
-
-    alpha_l_k_tt2_ttj[3] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[2], alpha_l_k_tt2_ttj[2]);
-    for(i = 0; i < this->m_outer_summands; i++)
-    {
-      u32bit j;
-      u32bit five_i = 5*i;
-      u32bit Lik_pos = Lik_pos_base + i;
-      this->m_Lik[Lik_pos] = 0;
-      for(j = 0; j <= 3; j++)
+   {
+   std::shared_ptr<GF2m_Field> sp_field = sigma.get_sp_field();
+   u32bit i, k, d;
+   d = sigma.get_degree();
+   for(k = 0; k < sp_field->get_extension_degree(); k++)
       {
-        gf2m f, x;
-        u32bit f_ind = five_i + (static_cast<u32bit>(1) << j);
-        if(f_ind > d)
-        {
-          break;
-        }
-        f = sigma.get_coef( f_ind);
-
-        x = sp_field->gf_mul_zrz(alpha_l_k_tt2_ttj[j], f);
-        this->m_Lik[Lik_pos] ^= x;
+      u32bit Lik_pos_base = k * this->m_outer_summands;
+      gf2m alpha_l_k_tt2_ttj[4];
+      alpha_l_k_tt2_ttj[0] = sp_field->gf_l_from_n(static_cast<gf2m>(1) << k);
+      alpha_l_k_tt2_ttj[1] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[0], alpha_l_k_tt2_ttj[0]);
+      alpha_l_k_tt2_ttj[2] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[1],alpha_l_k_tt2_ttj[1] );
+
+      alpha_l_k_tt2_ttj[3] = sp_field->gf_mul_rrr(alpha_l_k_tt2_ttj[2], alpha_l_k_tt2_ttj[2]);
+      for(i = 0; i < this->m_outer_summands; i++)
+         {
+         u32bit j;
+         u32bit five_i = 5*i;
+         u32bit Lik_pos = Lik_pos_base + i;
+         this->m_Lik[Lik_pos] = 0;
+         for(j = 0; j <= 3; j++)
+            {
+            gf2m f, x;
+            u32bit f_ind = five_i + (static_cast<u32bit>(1) << j);
+            if(f_ind > d)
+               {
+               break;
+               }
+            f = sigma.get_coef( f_ind);
+
+            x = sp_field->gf_mul_zrz(alpha_l_k_tt2_ttj[j], f);
+            this->m_Lik[Lik_pos] ^= x;
+            }
+         }
       }
-    }
-  }
-}
+   }
 
 gf2m gf2m_decomp_rootfind_state::calc_Fxj_j_neq_0( const polyn_gf2m & sigma, gf2m j_gray)
-{
-  //needs the A_{ij} to compute F(x)_j
-  gf2m sum = 0;
-  u32bit i;
-  std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = sigma.get_sp_field();
-  gf2m xl_j_tt_5i, xl_j_tt_5,  xl_gray_tt_3;
-  gf2m jl_gray;
-  jl_gray = sp_field->gf_l_from_n(j_gray);
-  xl_j_tt_5 = sp_field->gf_square_rr(jl_gray);
-  xl_gray_tt_3 = sp_field->gf_mul_rrr(xl_j_tt_5, jl_gray);
-  xl_j_tt_5 = sp_field->gf_mul_rrr(xl_j_tt_5, xl_gray_tt_3);
-
-
-  sum = sp_field->gf_mul_nrr(xl_gray_tt_3, this->m_sigma_3_l);
-  sum &= this->m_sigma_3_neq_0_mask;
-  /* here, we rely on compiler to be unable to optimize
+   {
+   //needs the A_{ij} to compute F(x)_j
+   gf2m sum = 0;
+   u32bit i;
+   std::shared_ptr<GF2m_Field> sp_field = sigma.get_sp_field();
+   gf2m xl_j_tt_5i, xl_j_tt_5,  xl_gray_tt_3;
+   const gf2m jl_gray = sp_field->gf_l_from_n(j_gray);
+   xl_j_tt_5 = sp_field->gf_square_rr(jl_gray);
+   xl_gray_tt_3 = sp_field->gf_mul_rrr(xl_j_tt_5, jl_gray);
+   xl_j_tt_5 = sp_field->gf_mul_rrr(xl_j_tt_5, xl_gray_tt_3);
+
+
+   sum = sp_field->gf_mul_nrr(xl_gray_tt_3, this->m_sigma_3_l);
+   sum &= this->m_sigma_3_neq_0_mask;
+   /* here, we rely on compiler to be unable to optimize
    * for the state->sigma_3_neq_0_mask value
    */
-  /* treat i = 0 special: */
-  sum ^= this->m_Aij[0];
-  /* treat i = 1 special also */
-  if(this->m_outer_summands > 1)
-  {
-    gf2m x;
-    xl_j_tt_5i = xl_j_tt_5;
-    x = sp_field->gf_mul_zrz(xl_j_tt_5, this->m_Aij[1]); /* x_j^{5i} A_i^j */
-    sum ^= x;
-  }
-  for(i = 2; i < this->m_outer_summands; i++)
-  {
-    gf2m x;
-    xl_j_tt_5i = sp_field->gf_mul_rrr(xl_j_tt_5i, xl_j_tt_5);
-    // now x_j_tt_5i lives up to its name
-    x = sp_field->gf_mul_zrz(xl_j_tt_5i, this->m_Aij[i]); /* x_j^{5i} A_i^(j) */
-    sum ^= x;
-  }
-  return sum;
-}
-
+   /* treat i = 0 special: */
+   sum ^= this->m_Aij[0];
+   /* treat i = 1 special also */
+   if(this->m_outer_summands > 1)
+      {
+      gf2m x;
+      xl_j_tt_5i = xl_j_tt_5;
+      x = sp_field->gf_mul_zrz(xl_j_tt_5, this->m_Aij[1]); /* x_j^{5i} A_i^j */
+      sum ^= x;
+      }
+   for(i = 2; i < this->m_outer_summands; i++)
+      {
+      gf2m x;
+      xl_j_tt_5i = sp_field->gf_mul_rrr(xl_j_tt_5i, xl_j_tt_5);
+      // now x_j_tt_5i lives up to its name
+      x = sp_field->gf_mul_zrz(xl_j_tt_5i, this->m_Aij[i]); /* x_j^{5i} A_i^(j) */
+      sum ^= x;
+      }
+   return sum;
+   }
 
+secure_vector<gf2m> gf2m_decomp_rootfind_state::find_roots(const polyn_gf2m & sigma)
+   {
+   secure_vector<gf2m> result(sigma.get_degree());
+   u32bit root_pos = 0;
 
+   this->calc_Ai_zero(sigma);
+   this->calc_LiK(sigma);
+   do
+      {
+      gf2m eval_result;
+      if(this->m_j_gray == 0)
+         {
+         eval_result = sigma.get_coef( 0);
+         }
+      else
+         {
+         eval_result = this->calc_Fxj_j_neq_0(sigma, this->m_j_gray);
+         }
+
+      if(eval_result == 0)
+         {
+
+         result[root_pos] = this->m_j_gray;
+         root_pos++;
+
+         }
+      if(this->m_j + static_cast<u32bit>(1) == this->get_code_length())
+         {
+         break;
+         }
+      this->calc_next_Aij();
+      }while(1);
+
+   // side channel / fault attack countermeasure:
+   root_pos = patch_root_array(result.data(), result.size(), root_pos);
+   result.resize(root_pos);
+   return result;
+   }
 
-secure_vector<gf2m> gf2m_decomp_rootfind_state::find_roots(const polyn_gf2m & sigma)
-{
-
-  secure_vector<gf2m> result(sigma.get_degree());
-  u32bit root_pos = 0;
-
-  this->calc_Ai_zero(sigma);
-  this->calc_LiK(sigma);
-  do
-  {
-    gf2m eval_result;
-    if(this->m_j_gray == 0)
-    {
-      eval_result = sigma.get_coef( 0);
-    }
-    else
-    {
-      eval_result = this->calc_Fxj_j_neq_0(sigma, this->m_j_gray);
-    }
-
-    if(eval_result == 0)
-    {
-
-      result[root_pos] = this->m_j_gray;
-      root_pos++;
-
-    }
-    if(this->m_j + static_cast<u32bit>(1) == this->get_code_length())
-    {
-      break;
-    }
-    this->calc_next_Aij();
-  }while(1);
-
-  // side channel / fault attack countermeasure:
-  root_pos = patch_root_array(result.data(), result.size(), root_pos);
-  result.resize(root_pos);
- return result;
-}
 } // end namespace Botan
diff --git a/src/lib/pubkey/mce/gf2m_rootfind_dcmp.h b/src/lib/pubkey/mce/gf2m_rootfind_dcmp.h
deleted file mode 100644
index 5914ad3ae..000000000
--- a/src/lib/pubkey/mce/gf2m_rootfind_dcmp.h
+++ /dev/null
@@ -1,24 +0,0 @@
-/**
- * (C) 2014 cryptosource GmbH
- * (C) 2014 Falko Strenzke [email protected]
- *
- * Botan is released under the Simplified BSD License (see license.txt)
- */
-
-#ifndef BOTAN_GF2M_ROOTFIND_DCMP_H__
-#define BOTAN_GF2M_ROOTFIND_DCMP_H__
-
-#include <botan/polyn_gf2m.h>
-
-namespace Botan {
-
-/**
-* Find the roots of a polynomial over GF(2^m) using the method by Federenko
-* et al.
-*/
-secure_vector<gf2m> find_roots_gf2m_decomp(const polyn_gf2m & polyn,
-                                           u32bit code_length);
-
-}
-
-#endif
diff --git a/src/lib/pubkey/mce/gf2m_small_m.cpp b/src/lib/pubkey/mce/gf2m_small_m.cpp
index 3de748939..11da30962 100644
--- a/src/lib/pubkey/mce/gf2m_small_m.cpp
+++ b/src/lib/pubkey/mce/gf2m_small_m.cpp
@@ -9,14 +9,11 @@
 */
 
 #include <botan/gf2m_small_m.h>
-#include <botan/code_based_util.h>
 #include <string>
 #include <stdexcept>
 
 namespace Botan {
 
-namespace gf2m_small_m {
-
 #define MAX_EXT_DEG 16
 
 namespace {
@@ -41,78 +38,94 @@ unsigned int prim_poly[MAX_EXT_DEG + 1] = {
    0210013		/* extension degree 16 */
 };
 
-}
-
-u32bit encode_gf2m(gf2m to_enc, byte* mem)
+std::vector<gf2m> gf_exp_table(size_t deg, gf2m prime_poly)
    {
-   mem[0] = to_enc >> 8;
-   mem[1] = to_enc & 0xFF;
-   return sizeof(to_enc);
+   // construct the table gf_exp[i]=alpha^i
+
+   std::vector<gf2m> tab((1 << deg) + 1);
+
+   tab[0] = 1;
+   for(size_t i = 1; i < tab.size(); ++i)
+      {
+      const bool overflow = tab[i - 1] >> (deg - 1);
+      tab[i] = (tab[i-1] << 1) ^ (overflow ? prime_poly : 0);
+      }
+
+   return tab;
    }
 
-gf2m decode_gf2m(const byte* mem)
+const std::vector<gf2m>& exp_table(size_t deg)
    {
-   gf2m result;
-   result = mem[0] << 8;
-   result |= mem[1];
-   return result;
+   static std::vector<gf2m> tabs[MAX_EXT_DEG + 1];
+
+   if(deg < 2 || deg > MAX_EXT_DEG)
+      throw std::runtime_error("GF2m_Field does not support degree " + std::to_string(deg));
+
+   if(tabs[deg].empty())
+      tabs[deg] = gf_exp_table(deg, prim_poly[deg]);
+
+   return tabs[deg];
    }
 
-// construct the table gf_exp[i]=alpha^i
-void Gf2m_Field::init_exp()
+std::vector<gf2m> gf_log_table(size_t deg, const std::vector<gf2m>& exp)
    {
-   m_gf_exp_table.resize(1 << get_extension_degree());
+   std::vector<gf2m> tab(1 << deg);
 
-   m_gf_exp_table[0] = 1;
-   for(size_t i = 1; i < gf_ord(); ++i)
+   tab[0] = (1 << deg) - 1; // log of 0 is the order by convention
+   for (size_t i = 0; i < tab.size(); ++i)
       {
-      m_gf_exp_table[i] = m_gf_exp_table[i - 1] << 1;
-      if (m_gf_exp_table[i - 1] & (1 << (get_extension_degree()-1)))
-         {
-         m_gf_exp_table[i] ^= prim_poly[get_extension_degree()];
-         }
+      tab[exp[i]] = i;
       }
-
-   // hack for the multiplication
-   m_gf_exp_table[gf_ord()] = 1;
+   return tab;
    }
 
-// construct the table gf_log[alpha^i]=i
-void Gf2m_Field::init_log()
+const std::vector<gf2m>& log_table(size_t deg)
    {
-   m_gf_log_table.resize(1 << get_extension_degree());
+   static std::vector<gf2m> tabs[MAX_EXT_DEG + 1];
 
-   m_gf_log_table[0] = gf_ord(); // log of 0 par convention
-   for (size_t i = 0; i < gf_ord() ; ++i)
-      {
-      m_gf_log_table[m_gf_exp_table[i]] = i;
-      }
+   if(deg < 2 || deg > MAX_EXT_DEG)
+      throw std::runtime_error("GF2m_Field does not support degree " + std::to_string(deg));
+
+   if(tabs[deg].empty())
+      tabs[deg] = gf_log_table(deg, exp_table(deg));
+
+   return tabs[deg];
    }
 
+}
 
-Gf2m_Field::Gf2m_Field(size_t extdeg)
+u32bit encode_gf2m(gf2m to_enc, byte* mem)
    {
-   if(extdeg < 2 || extdeg > MAX_EXT_DEG)
-      throw std::runtime_error("Gf2m_Field does not support degree " + std::to_string(extdeg));
+   mem[0] = to_enc >> 8;
+   mem[1] = to_enc & 0xFF;
+   return sizeof(to_enc);
+   }
 
-   m_gf_extension_degree = extdeg;
-   m_gf_cardinality = 1 << extdeg;
-   m_gf_multiplicative_order = m_gf_cardinality - 1;
+gf2m decode_gf2m(const byte* mem)
+   {
+   gf2m result;
+   result = mem[0] << 8;
+   result |= mem[1];
+   return result;
+   }
 
-   init_exp();
-   init_log();
+GF2m_Field::GF2m_Field(size_t extdeg) : m_gf_extension_degree(extdeg),
+                                        m_gf_multiplicative_order((1 << extdeg) - 1),
+                                        m_gf_log_table(log_table(m_gf_extension_degree)),
+                                        m_gf_exp_table(exp_table(m_gf_extension_degree))
+   {
    }
 
-gf2m Gf2m_Field::gf_div(gf2m x, gf2m y)
+gf2m GF2m_Field::gf_div(gf2m x, gf2m y) const
    {
-   s32bit sub_res = static_cast<s32bit>(m_gf_log_table[x]) - static_cast<s32bit>( m_gf_log_table[y]);
-   s32bit modq_res = static_cast<s32bit>(_gf_modq_1(sub_res));
-   s32bit div_res = static_cast<s32bit>(x) ? static_cast<s32bit>(m_gf_exp_table[modq_res]) : 0;
+   const s32bit sub_res = static_cast<s32bit>(gf_log(x) - static_cast<s32bit>(gf_log(y)));
+   const s32bit modq_res = static_cast<s32bit>(_gf_modq_1(sub_res));
+   const s32bit div_res = static_cast<s32bit>(x) ? static_cast<s32bit>(gf_exp(modq_res)) : 0;
    return static_cast<gf2m>(div_res);
    }
 
 // we suppose i >= 0. Par convention 0^0 = 1
-gf2m Gf2m_Field::gf_pow(gf2m x, int i)
+gf2m GF2m_Field::gf_pow(gf2m x, int i) const
    {
    if (i == 0)
       return 1;
@@ -123,13 +136,11 @@ gf2m Gf2m_Field::gf_pow(gf2m x, int i)
       // i mod (q-1)
       while (i >> get_extension_degree())
          i = (i & (gf_ord())) + (i >> get_extension_degree());
-      i *= m_gf_log_table[x];
+      i *= gf_log(x);
       while (i >> get_extension_degree())
          i = (i & (gf_ord())) + (i >> get_extension_degree());
-      return m_gf_exp_table[i];
+      return gf_exp(i);
       }
    }
 
 }
-
-}
diff --git a/src/lib/pubkey/mce/gf2m_small_m.h b/src/lib/pubkey/mce/gf2m_small_m.h
index 223dfd511..6a8de4424 100644
--- a/src/lib/pubkey/mce/gf2m_small_m.h
+++ b/src/lib/pubkey/mce/gf2m_small_m.h
@@ -17,213 +17,199 @@
 
 namespace Botan {
 
-namespace gf2m_small_m {
-
 typedef u16bit gf2m;
 
-class Gf2m_Field
+/**
+* GF(2^m) field for m = [2...16]
+*/
+class BOTAN_DLL GF2m_Field
    {
    public:
-      Gf2m_Field(size_t extdeg);
+      GF2m_Field(size_t extdeg);
 
-      gf2m gf_mul(gf2m x, gf2m y)
+      gf2m gf_mul(gf2m x, gf2m y) const
          {
          return ((x) ? gf_mul_fast(x, y) : 0);
          }
 
-      gf2m gf_square(gf2m x)
+      gf2m gf_square(gf2m x) const
          {
-         return ((x) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] << 1)] : 0);
+         return ((x) ? gf_exp(_gf_modq_1(gf_log(x) << 1)) : 0);
          }
 
-      gf2m square_rr(gf2m x)
+      gf2m square_rr(gf2m x) const
          {
          return _gf_modq_1(x << 1);
          }
 
-      // naming convention of GF(2^m) field operations:
-      // l logarithmic, unreduced
-      // r logarithmic, reduced
-      // n normal, non-zero
-      // z normal, might be zero
-      //
-      inline gf2m gf_mul_lll(gf2m a, gf2m b);
-      inline gf2m gf_mul_rrr(gf2m a, gf2m b);
-      inline gf2m gf_mul_nrr(gf2m a, gf2m b);
-      inline gf2m gf_mul_rrn(gf2m a, gf2m y);
-      inline gf2m gf_mul_lnn(gf2m x, gf2m y);
-      inline gf2m gf_mul_rnn(gf2m x, gf2m y);
-      inline gf2m gf_mul_nrn(gf2m a, gf2m y);
-      inline gf2m gf_mul_rnr(gf2m y, gf2m a);
-      inline gf2m gf_mul_zrz(gf2m a, gf2m y);
-      inline gf2m gf_mul_zzr(gf2m a, gf2m y);
-      inline gf2m gf_mul_nnr(gf2m y, gf2m a);
-      inline gf2m gf_sqrt(gf2m x) ;
-      gf2m gf_div(gf2m x, gf2m y);
-      inline gf2m gf_div_rnn(gf2m x, gf2m y);
-      inline gf2m gf_div_rnr(gf2m x, gf2m b);
-      inline gf2m gf_div_nrr(gf2m a, gf2m b);
-      inline gf2m gf_div_zzr(gf2m x, gf2m b);
-      inline gf2m gf_inv(gf2m x);
-      inline gf2m gf_inv_rn(gf2m x);
-      inline gf2m gf_square_ln(gf2m x);
-      inline gf2m gf_square_rr(gf2m a) ;
-      inline gf2m gf_l_from_n(gf2m x);
+      gf2m gf_mul_fast(gf2m x, gf2m y) const
+         {
+         return ((y) ? gf_exp(_gf_modq_1(gf_log(x) + gf_log(y))) : 0);
+         }
 
-      inline gf2m gf_mul_fast(gf2m a, gf2m b);
+      /*
+      naming convention of GF(2^m) field operations:
+        l logarithmic, unreduced
+        r logarithmic, reduced
+        n normal, non-zero
+        z normal, might be zero
+      */
 
-      gf2m gf_exp(gf2m i)
+      gf2m gf_mul_lll(gf2m a, gf2m b) const
          {
-         return m_gf_exp_table[i]; /* alpha^i */
+         return (a + b);
          }
 
-      gf2m gf_log(gf2m i)
+      gf2m gf_mul_rrr(gf2m a, gf2m b) const
          {
-         return m_gf_log_table[i]; /* return i when x=alpha^i */
+         return (_gf_modq_1(gf_mul_lll(a, b)));
          }
 
-      inline gf2m gf_ord() const
+      gf2m gf_mul_nrr(gf2m a, gf2m b) const
          {
-         return m_gf_multiplicative_order;
+         return (gf_exp(gf_mul_rrr(a, b)));
          }
 
-      inline gf2m get_extension_degree() const
+      gf2m gf_mul_rrn(gf2m a, gf2m y) const
          {
-         return m_gf_extension_degree;
+         return _gf_modq_1(gf_mul_lll(a, gf_log(y)));
          }
 
-      inline gf2m get_cardinality() const
+      gf2m gf_mul_rnr(gf2m y, gf2m a) const
          {
-         return m_gf_cardinality;
+         return gf_mul_rrn(a, y);
          }
 
-      gf2m gf_pow(gf2m x, int i) ;
+      gf2m gf_mul_lnn(gf2m x, gf2m y) const
+         {
+         return (gf_log(x) + gf_log(y));
+         }
 
-   private:
-      gf2m m_gf_extension_degree, m_gf_cardinality, m_gf_multiplicative_order;
-      std::vector<gf2m> m_gf_log_table;
-      std::vector<gf2m> m_gf_exp_table;
+      gf2m gf_mul_rnn(gf2m x, gf2m y) const
+         {
+         return _gf_modq_1(gf_mul_lnn(x, y));
+         }
 
-      inline gf2m _gf_modq_1(s32bit d);
-      void init_log();
-      void init_exp();
-   };
+      gf2m gf_mul_nrn(gf2m a, gf2m y) const
+         {
+         return gf_exp(_gf_modq_1((a) + gf_log(y)));
+         }
 
-gf2m Gf2m_Field::_gf_modq_1(s32bit d)
-   {
-   return  (((d) & gf_ord()) + ((d) >> m_gf_extension_degree));
-   }
+      /**
+      * zero operand allowed
+      */
+      gf2m gf_mul_zrz(gf2m a, gf2m y) const
+         {
+         return ( (y == 0) ? 0 : gf_mul_nrn(a, y) );
+         }
 
-gf2m Gf2m_Field::gf_mul_fast(gf2m x, gf2m y)
-   {
-   return ((y) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] + m_gf_log_table[y])] : 0);
-   }
+      gf2m gf_mul_zzr(gf2m a, gf2m y) const
+         {
+         return gf_mul_zrz(y, a);
+         }
 
-gf2m Gf2m_Field::gf_mul_lll(gf2m a, gf2m b)
-   {
-   return  (a + b);
-   }
+      /**
+      * non-zero operand
+      */
+      gf2m gf_mul_nnr(gf2m y, gf2m a) const
+         {
+         return gf_mul_nrn(a, y);
+         }
 
-gf2m Gf2m_Field::gf_mul_rrr(gf2m a, gf2m b)
-   {
-   return (_gf_modq_1(gf_mul_lll(a, b)));
-   }
+      gf2m gf_sqrt(gf2m x) const
+         {
+         return ((x) ? gf_exp(_gf_modq_1(gf_log(x) << (get_extension_degree()-1))) : 0);
+         }
 
-gf2m Gf2m_Field::gf_mul_nrr(gf2m a, gf2m b)
-   {
-   return (gf_exp(gf_mul_rrr(a, b)));
-   }
+      gf2m gf_div_rnn(gf2m x, gf2m y) const
+         {
+         return _gf_modq_1(gf_log(x) - gf_log(y));
+         }
 
-gf2m Gf2m_Field::gf_mul_rrn(gf2m a, gf2m y)
-   {
-   return _gf_modq_1(gf_mul_lll(a, gf_log(y)));
-   }
+      gf2m gf_div_rnr(gf2m x, gf2m b) const
+         {
+         return _gf_modq_1(gf_log(x) - b);
+         }
 
-gf2m Gf2m_Field::gf_mul_rnr(gf2m y, gf2m a)
-   {
-   return gf_mul_rrn(a, y);
-   }
+      gf2m gf_div_nrr(gf2m a, gf2m b) const
+         {
+         return gf_exp(_gf_modq_1(a - b));
+         }
 
-gf2m Gf2m_Field::gf_mul_lnn(gf2m x, gf2m y)
-   {
-   return (m_gf_log_table[x] + m_gf_log_table[y]);
-   }
-gf2m Gf2m_Field::gf_mul_rnn(gf2m x, gf2m y)
-   {
-   return _gf_modq_1(gf_mul_lnn(x, y));
-   }
+      gf2m gf_div_zzr(gf2m x, gf2m b) const
+         {
+         return ((x) ? gf_exp(_gf_modq_1(gf_log(x) - b)) : 0);
+         }
 
-gf2m Gf2m_Field::gf_mul_nrn(gf2m a, gf2m y)
-   {
-   return m_gf_exp_table[_gf_modq_1((a) + m_gf_log_table[y])];
-   }
+      gf2m gf_inv(gf2m x) const
+         {
+         return gf_exp(gf_ord() - gf_log(x));
+         }
 
-/**
-* zero operand allowed
-*/
-gf2m Gf2m_Field::gf_mul_zrz(gf2m a, gf2m y)
-   {
-   return ( (y == 0) ? 0 : gf_mul_nrn(a, y) );
-   }
+      gf2m gf_inv_rn(gf2m x) const
+         {
+         return (gf_ord() - gf_log(x));
+         }
 
-gf2m Gf2m_Field::gf_mul_zzr(gf2m a, gf2m y)
-   {
-   return gf_mul_zrz(y, a);
-   }
-/**
-* non-zero operand
-*/
-gf2m Gf2m_Field::gf_mul_nnr(gf2m y, gf2m a)
-   {
-   return gf_mul_nrn( a, y);
-   }
+      gf2m gf_square_ln(gf2m x) const
+         {
+         return gf_log(x) << 1;
+         }
 
-gf2m Gf2m_Field::gf_sqrt(gf2m x)
-   {
-   return ((x) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] << (m_gf_extension_degree-1))] : 0);
-   }
+      gf2m gf_square_rr(gf2m a) const
+         {
+         return a << 1;
+         }
 
-gf2m Gf2m_Field::gf_div_rnn(gf2m x, gf2m y)
-   {
-   return _gf_modq_1(m_gf_log_table[x] - m_gf_log_table[y]);
-   }
-gf2m Gf2m_Field::gf_div_rnr(gf2m x, gf2m b)
-   {
-   return _gf_modq_1(m_gf_log_table[x] - b);
-   }
-gf2m Gf2m_Field::gf_div_nrr(gf2m a, gf2m b)
-   {
-   return m_gf_exp_table[_gf_modq_1(a - b)];
-   }
+      gf2m gf_l_from_n(gf2m x) const
+         {
+         return gf_log(x);
+         }
 
-gf2m Gf2m_Field::gf_div_zzr(gf2m x, gf2m b)
-   {
-   return ((x) ? m_gf_exp_table[_gf_modq_1(m_gf_log_table[x] - b)] : 0);
-   }
+      gf2m gf_div(gf2m x, gf2m y) const;
 
-gf2m Gf2m_Field::gf_inv(gf2m x)
-   {
-   return m_gf_exp_table[gf_ord() - m_gf_log_table[x]];
-   }
-gf2m Gf2m_Field::gf_inv_rn(gf2m x)
-   {
-   return (gf_ord() - m_gf_log_table[x]);
-   }
+      gf2m gf_pow(gf2m x, int i) const;
 
-gf2m Gf2m_Field::gf_square_ln(gf2m x)
-   {
-   return m_gf_log_table[x] << 1;
-   }
+      gf2m gf_exp(gf2m i) const
+         {
+         return m_gf_exp_table.at(i); /* alpha^i */
+         }
 
-gf2m Gf2m_Field::gf_square_rr(gf2m a)
-   {
-   return a << 1;
-   }
+      gf2m gf_log(gf2m i) const
+         {
+         return m_gf_log_table.at(i); /* return i when x=alpha^i */
+         }
 
-gf2m Gf2m_Field::gf_l_from_n(gf2m x)
-   {
-   return m_gf_log_table[x];
-   }
+      gf2m gf_ord() const
+         {
+         return m_gf_multiplicative_order;
+         }
+
+      gf2m get_extension_degree() const
+         {
+         return m_gf_extension_degree;
+         }
+
+      gf2m get_cardinality() const
+         {
+         return static_cast<gf2m>(1 << get_extension_degree());
+         }
+
+   private:
+      gf2m _gf_modq_1(s32bit d) const
+         {
+         /* residual modulo q-1
+         when -q < d < 0, we get (q-1+d)
+         when 0 <= d < q, we get (d)
+         when q <= d < 2q-1, we get (d-q+1)
+         */
+         return (((d) & gf_ord()) + ((d) >> get_extension_degree()));
+         }
+
+      gf2m m_gf_extension_degree, m_gf_multiplicative_order;
+      const std::vector<gf2m>& m_gf_log_table;
+      const std::vector<gf2m>& m_gf_exp_table;
+   };
 
 u32bit encode_gf2m(gf2m to_enc, byte* mem);
 
@@ -231,6 +217,4 @@ gf2m decode_gf2m(const byte* mem);
 
 }
 
-}
-
 #endif
diff --git a/src/lib/pubkey/mce/goppa_code.cpp b/src/lib/pubkey/mce/goppa_code.cpp
index 175508eac..637b8175a 100644
--- a/src/lib/pubkey/mce/goppa_code.cpp
+++ b/src/lib/pubkey/mce/goppa_code.cpp
@@ -9,10 +9,8 @@
  *
  */
 
-#include <botan/goppa_code.h>
-
-#include <botan/gf2m_rootfind_dcmp.h>
-#include <botan/code_based_util.h>
+#include <botan/internal/mce_internal.h>
+#include <botan/internal/code_based_util.h>
 
 namespace Botan {
 
@@ -48,7 +46,7 @@ secure_vector<gf2m> goppa_decode(const polyn_gf2m & syndrom_polyn,
    u32bit code_length = Linv.size();
    u32bit t = g.get_degree();
 
-   std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = g.get_sp_field();
+   std::shared_ptr<GF2m_Field> sp_field = g.get_sp_field();
 
    std::pair<polyn_gf2m, polyn_gf2m> h__aux = polyn_gf2m::eea_with_coefficients( syndrom_polyn, g, 1);
    polyn_gf2m & h = h__aux.first;
@@ -125,6 +123,37 @@ secure_vector<gf2m> goppa_decode(const polyn_gf2m & syndrom_polyn,
    }
 }
 
+void mceliece_decrypt(secure_vector<byte>& plaintext_out,
+                      secure_vector<byte>& error_mask_out,
+                      const secure_vector<byte>& ciphertext,
+                      const McEliece_PrivateKey& key)
+   {
+   mceliece_decrypt(plaintext_out, error_mask_out, ciphertext.data(), ciphertext.size(), key);
+   }
+
+void mceliece_decrypt(
+   secure_vector<byte>& plaintext,
+   secure_vector<byte> & error_mask,
+   const byte ciphertext[],
+   size_t ciphertext_len,
+   const McEliece_PrivateKey & key)
+   {
+   secure_vector<gf2m> error_pos;
+   plaintext = mceliece_decrypt(error_pos, ciphertext, ciphertext_len, key);
+
+   const size_t code_length = key.get_code_length();
+   secure_vector<byte> result((code_length+7)/8);
+   for(auto&& pos : error_pos)
+      {
+      if(pos > code_length)
+         {
+         throw std::invalid_argument("error position larger than code size");
+         }
+      result[pos / 8] |= (1 << (pos % 8));
+      }
+
+   error_mask = result;
+   }
 
 /**
 * @param p_err_pos_len must point to the available length of err_pos on input, the
@@ -154,30 +183,27 @@ secure_vector<byte> mceliece_decrypt(
       throw Invalid_Argument("mce-decryption: wrong length of cleartext buffer");
       }
 
-
    secure_vector<u32bit> syndrome_vec(bit_size_to_32bit_size(codimension));
-   matrix_arr_mul(
-      key.get_H_coeffs(),
-      key.get_code_length(),
-      bit_size_to_32bit_size(codimension),
-      ciphertext,
-      syndrome_vec.data(), syndrome_vec.size() );
+   matrix_arr_mul(key.get_H_coeffs(),
+                  key.get_code_length(),
+                  bit_size_to_32bit_size(codimension),
+                  ciphertext,
+                  syndrome_vec.data(), syndrome_vec.size());
+
    secure_vector<byte> syndrome_byte_vec(bit_size_to_byte_size(codimension));
    u32bit syndrome_byte_vec_size = syndrome_byte_vec.size();
    for(u32bit i = 0; i < syndrome_byte_vec_size; i++)
       {
       syndrome_byte_vec[i] = syndrome_vec[i/4] >> (8* (i % 4));
       }
-   syndrome_polyn = polyn_gf2m(t-1, syndrome_byte_vec.data(), bit_size_to_byte_size(codimension), key.get_goppa_polyn().get_sp_field());
-
 
+   syndrome_polyn = polyn_gf2m(t-1, syndrome_byte_vec.data(), bit_size_to_byte_size(codimension), key.get_goppa_polyn().get_sp_field());
 
    syndrome_polyn.get_degree();
    error_pos = goppa_decode(syndrome_polyn, key.get_goppa_polyn(), key.get_sqrtmod(), key.get_Linv());
 
    u32bit nb_err = error_pos.size();
 
-
    secure_vector<byte> cleartext(cleartext_len);
    copy_mem(cleartext.data(), ciphertext, cleartext_len);
 
@@ -192,6 +218,7 @@ secure_vector<byte> mceliece_decrypt(
          }
       cleartext[current / 8] ^= (1 << (current % 8));
       }
+
    if(unused_pt_bits)
       {
       cleartext[cleartext_len - 1] &= unused_pt_bits_mask;
diff --git a/src/lib/pubkey/mce/goppa_code.h b/src/lib/pubkey/mce/goppa_code.h
deleted file mode 100644
index 377cd9b3d..000000000
--- a/src/lib/pubkey/mce/goppa_code.h
+++ /dev/null
@@ -1,32 +0,0 @@
-/**
- * (C) Copyright Projet SECRET, INRIA, Rocquencourt
- * (C) Bhaskar Biswas and  Nicolas Sendrier
- *
- * (C) 2014 cryptosource GmbH
- * (C) 2014 Falko Strenzke [email protected]
- *
- * Botan is released under the Simplified BSD License (see license.txt)
- *
- */
-
-#ifndef BOTAN_MCE_GOPPA_CODE_H__
-#define BOTAN_MCE_GOPPA_CODE_H__
-
-#include <botan/polyn_gf2m.h>
-#include <botan/mceliece_key.h>
-
-namespace Botan {
-
-std::vector<byte> mceliece_encrypt(const secure_vector<byte>& cleartext,
-                                   const std::vector<byte>& public_matrix,
-                                   const secure_vector<gf2m> & err_pos,
-                                   u32bit code_length);
-
-secure_vector<byte> mceliece_decrypt(secure_vector<gf2m> & error_pos,
-                                     const byte *ciphertext,
-                                     u32bit ciphertext_len,
-                                     const McEliece_PrivateKey& key);
-
-}
-
-#endif
diff --git a/src/lib/pubkey/mce/info.txt b/src/lib/pubkey/mce/info.txt
index c06e23b8e..1e9b848dd 100644
--- a/src/lib/pubkey/mce/info.txt
+++ b/src/lib/pubkey/mce/info.txt
@@ -1,17 +1,17 @@
-define MCELIECE 20141124
+define MCELIECE 20150922
 
 <header:public>
-code_based_util.h
-gf2m_rootfind_dcmp.h
-gf2m_small_m.h
-goppa_code.h
 mce_kem.h
 mceliece.h
-mceliece_key.h
 polyn_gf2m.h
+gf2m_small_m.h
 </header:public>
 
 <header:internal>
-binary_matrix.h
-code_based_key_gen.h
+code_based_util.h
+mce_internal.h
 </header:internal>
+
+<requires>
+sha2_64
+</requires>
diff --git a/src/lib/pubkey/mce/mce_internal.h b/src/lib/pubkey/mce/mce_internal.h
new file mode 100644
index 000000000..d35479080
--- /dev/null
+++ b/src/lib/pubkey/mce/mce_internal.h
@@ -0,0 +1,52 @@
+/**
+ * (C) Copyright Projet SECRET, INRIA, Rocquencourt
+ * (C) Bhaskar Biswas and  Nicolas Sendrier
+ *
+ * (C) 2014 cryptosource GmbH
+ * (C) 2014 Falko Strenzke [email protected]
+ *
+ * Botan is released under the Simplified BSD License (see license.txt)
+ *
+ */
+
+#ifndef BOTAN_MCELIECE_INTERNAL_H__
+#define BOTAN_MCELIECE_INTERNAL_H__
+
+#include <botan/secmem.h>
+#include <botan/types.h>
+#include <botan/pk_ops.h>
+#include <botan/mceliece.h>
+
+namespace Botan {
+
+void mceliece_decrypt(secure_vector<byte>& plaintext_out,
+                      secure_vector<byte>& error_mask_out,
+                      const byte ciphertext[],
+                      size_t ciphertext_len,
+                      const McEliece_PrivateKey& key);
+
+void mceliece_decrypt(secure_vector<byte>& plaintext_out,
+                      secure_vector<byte>& error_mask_out,
+                      const secure_vector<byte>& ciphertext,
+                      const McEliece_PrivateKey& key);
+
+secure_vector<byte> mceliece_decrypt(
+   secure_vector<gf2m> & error_pos,
+   const byte *ciphertext, u32bit ciphertext_len,
+   const McEliece_PrivateKey & key);
+
+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);
+
+McEliece_PrivateKey generate_mceliece_key(RandomNumberGenerator &rng,
+                                          u32bit ext_deg,
+                                          u32bit code_length,
+                                          u32bit t);
+
+}
+
+
+#endif
diff --git a/src/lib/pubkey/mce/mce_kem.cpp b/src/lib/pubkey/mce/mce_kem.cpp
index b24c42f85..dede67731 100644
--- a/src/lib/pubkey/mce/mce_kem.cpp
+++ b/src/lib/pubkey/mce/mce_kem.cpp
@@ -7,56 +7,42 @@
  */
 
 #include <botan/mce_kem.h>
+#include <botan/internal/mce_internal.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())
+   m_key(public_key)
    {
    }
 
 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.data(), plaintext.size());
+   const secure_vector<byte> plaintext = m_key.random_plaintext_element(rng);
 
-   // 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();
+   secure_vector<byte> ciphertext, error_mask;
+   mceliece_encrypt(ciphertext, error_mask, plaintext, m_key, rng);
 
    SHA_512 hash;
-   hash.update(message_and_error_input);
+   hash.update(plaintext);
+   hash.update(error_mask);
    secure_vector<byte> sym_key = hash.final();
-   secure_vector<byte> ciphertext = m_raw_pub_op.encrypt(message_and_error_input.data(),
-                                                         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)
-   {
-   }
+McEliece_KEM_Decryptor::McEliece_KEM_Decryptor(const McEliece_PrivateKey& key) : m_key(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, msg_len);
+   secure_vector<byte> plaintext, error_mask;
+   mceliece_decrypt(plaintext, error_mask, msg, msg_len, m_key);
 
    SHA_512 hash;
-   hash.update(message_and_error);
+   hash.update(plaintext);
+   hash.update(error_mask);
 
    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
index 7a8d2f7ff..cd899d568 100644
--- a/src/lib/pubkey/mce/mce_kem.h
+++ b/src/lib/pubkey/mce/mce_kem.h
@@ -25,7 +25,7 @@ class BOTAN_DLL McEliece_KEM_Encryptor
       std::pair<secure_vector<byte>, secure_vector<byte>> encrypt(RandomNumberGenerator& rng);
 
    private:
-      McEliece_Public_Operation m_raw_pub_op;
+      const McEliece_PublicKey& m_key;
    };
 
 class BOTAN_DLL McEliece_KEM_Decryptor
@@ -45,10 +45,10 @@ class BOTAN_DLL McEliece_KEM_Decryptor
       secure_vector<Botan::byte> decrypt_vec(const std::vector<byte, Alloc>& v)
          {
          return decrypt(v.data(), v.size());
-
          }
+
    private:
-      McEliece_Private_Operation m_raw_priv_op;
+      const McEliece_PrivateKey& m_key;
   };
 }
 
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);
    }
 
 }
diff --git a/src/lib/pubkey/mce/mceliece.h b/src/lib/pubkey/mce/mceliece.h
index c5f02470f..ead326230 100644
--- a/src/lib/pubkey/mce/mceliece.h
+++ b/src/lib/pubkey/mce/mceliece.h
@@ -9,141 +9,128 @@
  *
  */
 
-#ifndef BOTAN_MCELIECE_H__
-#define BOTAN_MCELIECE_H__
+#ifndef BOTAN_MCELIECE_KEY_H__
+#define BOTAN_MCELIECE_KEY_H__
 
-#include <botan/secmem.h>
-#include <botan/types.h>
-#include <botan/pk_ops.h>
-#include <botan/mceliece_key.h>
-
-#define MASK_LOG2_BYTE ((1 << 3) - 1)
-#define _BITP_TO_BYTEP(__bit_pos) (__bit_pos >> 3)
-#define _BITP_TO_BYTEOFFS(__bit_pos) (__bit_pos & MASK_LOG2_BYTE)
+#include <botan/pk_keys.h>
+#include <botan/polyn_gf2m.h>
+#include <botan/exceptn.h>
 
 namespace Botan {
 
-secure_vector<gf2m> BOTAN_DLL create_random_error_positions(unsigned code_length, unsigned error_weight, RandomNumberGenerator& rng);
-
-class mceliece_message_parts
+class BOTAN_DLL McEliece_PublicKey : public virtual Public_Key
    {
    public:
+      McEliece_PublicKey(const std::vector<byte>& key_bits);
 
-      mceliece_message_parts(const secure_vector<gf2m>& err_pos, const byte* message, u32bit message_length, u32bit code_length) :
-         m_error_vector(error_vector_from_error_positions(err_pos.data(), err_pos.size(), code_length)),
-         m_code_length(code_length)
-         {
-         m_message_word.resize(message_length);
-         copy_mem(m_message_word.data(), message, message_length);
-         }
-
-      mceliece_message_parts(const secure_vector<gf2m>& err_pos, const secure_vector<byte>& message, unsigned code_length) :
-         m_error_vector(error_vector_from_error_positions(err_pos.data(), err_pos.size(), code_length)),
-         m_message_word(message),
-         m_code_length(code_length)
-         {}
-
-      static secure_vector<byte> error_vector_from_error_positions(const gf2m* err_pos, size_t err_pos_len, size_t code_length)
-         {
-         secure_vector<byte> result((code_length+7)/8);
-         for(unsigned i = 0; i < err_pos_len; i++)
-            {
-            u16bit pos = err_pos[i];
-            u32bit byte_pos = _BITP_TO_BYTEP(pos);
-            if(byte_pos > result.size())
-               {
-               throw Invalid_Argument("error position larger than code size");
-               }
-            result[byte_pos] |= (1 << _BITP_TO_BYTEOFFS(pos));
-            }
-         return result;
-         }
-
-      mceliece_message_parts(const byte* message_concat_errors, size_t message_concat_errors_len, unsigned code_length) :
-         m_code_length(code_length)
-         {
-         size_t err_vec_len = (code_length+7)/8;
-         if(message_concat_errors_len < err_vec_len )
-            {
-            throw Invalid_Argument("cannot split McEliece message parts");
-            }
-         size_t err_vec_start_pos = message_concat_errors_len - err_vec_len;
-         m_message_word = secure_vector<byte>(err_vec_start_pos);
-         copy_mem(m_message_word.data(), message_concat_errors, err_vec_start_pos);
-         m_error_vector = secure_vector<byte>(err_vec_len);
-         copy_mem(m_error_vector.data(), &message_concat_errors[err_vec_start_pos], err_vec_len);
-         }
-
-      secure_vector<byte> get_concat() const
-         {
-         secure_vector<byte> result(m_error_vector.size() + m_message_word.size());
-         copy_mem(result.data(), m_message_word.data(), m_message_word.size());
-         copy_mem(&result[m_message_word.size()], m_error_vector.data(), m_error_vector.size());
-         return result;
-         }
-
-      secure_vector<gf2m> get_error_positions() const
-         {
-         secure_vector<gf2m> result;
-         for(unsigned i = 0; i < m_code_length; i++)
-            {
-            if(i >= m_code_length)
-               {
-               throw Invalid_Argument("index out of range in get_error_positions()");
-               }
-            if((m_error_vector[_BITP_TO_BYTEP(i)] >> _BITP_TO_BYTEOFFS(i)) & 1)
-               {
-               result.push_back(i);
-               }
-            }
-         return result;
-         }
-
-      secure_vector<byte> get_error_vector() const { return m_error_vector; }
-      secure_vector<byte> get_message_word() const { return m_message_word; }
-   private:
-      secure_vector<byte> m_error_vector;
-      secure_vector<byte> m_message_word;
-      unsigned m_code_length;
-   };
+      McEliece_PublicKey(std::vector<byte> const& pub_matrix, u32bit the_t, u32bit the_code_length) :
+         m_public_matrix(pub_matrix),
+         m_t(the_t),
+         m_code_length(the_code_length)
+            {}
 
-class BOTAN_DLL McEliece_Private_Operation : public PK_Ops::Decryption
-   {
-   public:
-      McEliece_Private_Operation(const McEliece_PrivateKey& mce_key);
+      McEliece_PublicKey(const McEliece_PublicKey& other);
 
-      size_t max_input_bits() const override { return m_priv_key.max_input_bits();  }
+      secure_vector<byte> random_plaintext_element(RandomNumberGenerator& rng) const;
 
-      secure_vector<byte> decrypt(const byte msg[], size_t msg_len) override;
+      std::string algo_name() const override { return "McEliece"; }
 
-      McEliece_PrivateKey const& get_key() const { return m_priv_key; }
+      /**
+      * Get the maximum number of bits allowed to be fed to this key.
+      * @result the maximum number of input bits
+      */
+      size_t max_input_bits() const override { return get_message_word_bit_length(); }
 
-   private:
-      const McEliece_PrivateKey m_priv_key;
+      AlgorithmIdentifier algorithm_identifier() const override;
+
+      size_t estimated_strength() const override;
+
+      std::vector<byte> x509_subject_public_key() const override;
+
+      bool check_key(RandomNumberGenerator&, bool) const override
+         { return true; }
+
+      u32bit get_t() const { return m_t; }
+      u32bit get_code_length() const { return m_code_length; }
+      u32bit get_message_word_bit_length() const;
+      const std::vector<byte>& get_public_matrix() const { return m_public_matrix; }
+
+      bool operator==(const McEliece_PublicKey& other) const;
+      bool operator!=(const McEliece_PublicKey& other) const { return !(*this == other); }
+
+   protected:
+      McEliece_PublicKey() {}
+
+      std::vector<byte> m_public_matrix;
+      u32bit m_t;
+      u32bit m_code_length;
    };
 
-class BOTAN_DLL McEliece_Public_Operation : public PK_Ops::Encryption
+class BOTAN_DLL McEliece_PrivateKey : public virtual McEliece_PublicKey,
+                                      public virtual Private_Key
    {
    public:
-      McEliece_Public_Operation(const McEliece_PublicKey& public_key, u32bit code_length);
+      /**
+      * Get the maximum number of bits allowed to be fed to this key.
+      * @result the maximum number of input bits
+      */
+      size_t max_input_bits() const override { return m_Linv.size(); }
+
+      /**
+      Generate a McEliece key pair
+
+      Suggested parameters for a given security level (SL)
+
+      SL=80 n=1632 t=33 - 59 KB pubkey 140 KB privkey
+      SL=107 n=2480 t=45 - 128 KB pubkey 300 KB privkey
+      SL=128 n=2960 t=57 - 195 KB pubkey 459 KB privkey
+      SL=147 n=3408 t=67 - 265 KB pubkey 622 KB privkey
+      SL=191 n=4624 t=95 - 516 KB pubkey 1234 KB privkey
+      SL=256 n=6624 t=115 - 942 KB pubkey 2184 KB privkey
+      */
+      McEliece_PrivateKey(RandomNumberGenerator& rng, size_t code_length, size_t t);
+
+      McEliece_PrivateKey(const secure_vector<byte>& key_bits);
+
+      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 );
+
+      bool check_key(RandomNumberGenerator& rng, bool strong) const override;
 
-      size_t max_input_bits() const override { return m_pub_key.max_input_bits(); }
-      secure_vector<byte> encrypt(const byte msg[], size_t msg_len, RandomNumberGenerator&) override;
+      polyn_gf2m const& get_goppa_polyn() const { return m_g; }
+      std::vector<u32bit> const& get_H_coeffs() const { return m_coeffs; }
+      std::vector<gf2m> const& get_Linv() const { return m_Linv; }
+      std::vector<polyn_gf2m> const& get_sqrtmod() const { return m_sqrtmod; }
 
-      McEliece_PublicKey const& get_key() const { return m_pub_key; }
+      inline u32bit get_dimension() const { return m_dimension; }
+
+      inline u32bit get_codimension() const { return m_codimension; }
+
+      secure_vector<byte> pkcs8_private_key() const override;
+
+      bool operator==(const McEliece_PrivateKey & other) const;
+
+      bool operator!=(const McEliece_PrivateKey& other) const { return !(*this == other); }
 
    private:
-      McEliece_PublicKey m_pub_key;
-      u32bit m_code_length;
+      polyn_gf2m m_g;
+      std::vector<polyn_gf2m> m_sqrtmod;
+      std::vector<gf2m> m_Linv;
+      std::vector<u32bit> m_coeffs;
+
+      u32bit m_codimension;
+      u32bit m_dimension;
    };
 
 /**
 * Estimate work factor for McEliece
 * @return estimated security level for these key parameters
 */
-BOTAN_DLL size_t mceliece_work_factor(size_t code_size, size_t k, size_t t);
+BOTAN_DLL size_t mceliece_work_factor(size_t code_size, size_t t);
 
 }
 
-
 #endif
diff --git a/src/lib/pubkey/mce/mceliece_key.cpp b/src/lib/pubkey/mce/mceliece_key.cpp
index 8cda0af89..8edbbf88a 100644
--- a/src/lib/pubkey/mce/mceliece_key.cpp
+++ b/src/lib/pubkey/mce/mceliece_key.cpp
@@ -9,15 +9,12 @@
  *
  */
 
-#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/code_based_util.h>
+#include <botan/internal/mce_internal.h>
+#include <botan/internal/bit_ops.h>
+#include <botan/internal/code_based_util.h>
 #include <botan/der_enc.h>
 #include <botan/ber_dec.h>
-#include <botan/workfactor.h>
 
 namespace Botan {
 
@@ -42,12 +39,29 @@ McEliece_PrivateKey::McEliece_PrivateKey(RandomNumberGenerator& rng, size_t code
    *this = generate_mceliece_key(rng, ext_deg, code_length, t);
    }
 
-unsigned McEliece_PublicKey::get_message_word_bit_length() const
+u32bit McEliece_PublicKey::get_message_word_bit_length() const
    {
    u32bit codimension = ceil_log2(m_code_length) * m_t;
    return m_code_length - codimension;
    }
 
+secure_vector<byte> McEliece_PublicKey::random_plaintext_element(RandomNumberGenerator& rng) const
+   {
+   const size_t bits = get_message_word_bit_length();
+
+   secure_vector<byte> plaintext((bits+7)/8);
+   rng.randomize(plaintext.data(), plaintext.size());
+
+   // unset unused bits in the last plaintext byte
+   if(u32bit used = bits % 8)
+      {
+      const byte mask = (1 << used) - 1;
+      plaintext[plaintext.size() - 1] &= mask;
+      }
+
+   return plaintext;
+   }
+
 AlgorithmIdentifier McEliece_PublicKey::algorithm_identifier() const
    {
    return AlgorithmIdentifier(get_oid(), std::vector<byte>());
@@ -55,16 +69,15 @@ AlgorithmIdentifier McEliece_PublicKey::algorithm_identifier() const
 
 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());
+   return 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_unlocked();
    }
 
 McEliece_PublicKey::McEliece_PublicKey(const McEliece_PublicKey & other) :
@@ -76,9 +89,7 @@ McEliece_PublicKey::McEliece_PublicKey(const McEliece_PublicKey & other) :
 
 size_t McEliece_PublicKey::estimated_strength() const
    {
-   const u32bit ext_deg = ceil_log2(m_code_length);
-   const size_t k = m_code_length - ext_deg * m_t;
-   return mceliece_work_factor(m_code_length, k, m_t);
+   return mceliece_work_factor(m_code_length, m_t);
    }
 
 McEliece_PublicKey::McEliece_PublicKey(const std::vector<byte>& key_bits)
@@ -135,19 +146,20 @@ secure_vector<byte> McEliece_PrivateKey::pkcs8_private_key() const
 
 bool McEliece_PrivateKey::check_key(RandomNumberGenerator& rng, bool) const
    {
-   McEliece_Private_Operation priv_op(*this);
-   McEliece_Public_Operation pub_op(*this, get_code_length());
+   const secure_vector<byte> plaintext = this->random_plaintext_element(rng);
 
-   secure_vector<byte> plaintext((this->get_message_word_bit_length()+7)/8);
-   rng.randomize(plaintext.data(), plaintext.size() - 1);
-   const secure_vector<gf2m> err_pos = create_random_error_positions(this->get_code_length(), this->get_t(), rng);
+   secure_vector<byte> ciphertext;
+   secure_vector<byte> errors;
+   mceliece_encrypt(ciphertext, errors, plaintext, *this, rng);
 
-   mceliece_message_parts parts(err_pos, plaintext, this->get_code_length());
-   secure_vector<byte> message_and_error_input = parts.get_concat();
-   secure_vector<byte> ciphertext = pub_op.encrypt(message_and_error_input.data(), message_and_error_input.size(), rng);
-   secure_vector<byte> message_and_error_output = priv_op.decrypt(ciphertext.data(), ciphertext.size());
+   secure_vector<byte> plaintext_out;
+   secure_vector<byte> errors_out;
+   mceliece_decrypt(plaintext_out, errors_out, ciphertext, *this);
 
-   return (message_and_error_input == message_and_error_output);
+   if(errors != errors_out || plaintext != plaintext_out)
+      return false;
+
+   return true;
    }
 
 McEliece_PrivateKey::McEliece_PrivateKey(const secure_vector<byte>& key_bits)
@@ -172,7 +184,7 @@ McEliece_PrivateKey::McEliece_PrivateKey(const secure_vector<byte>& key_bits)
    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));
+   std::shared_ptr<GF2m_Field> sp_field(new GF2m_Field(ext_deg));
    m_g = polyn_gf2m(g_enc, sp_field);
    if(m_g.get_degree() != static_cast<int>(t))
       {
@@ -231,7 +243,6 @@ McEliece_PrivateKey::McEliece_PrivateKey(const secure_vector<byte>& key_bits)
 
    }
 
-
 bool McEliece_PrivateKey::operator==(const McEliece_PrivateKey & other) const
    {
    if(*static_cast<const McEliece_PublicKey*>(this) != *static_cast<const McEliece_PublicKey*>(&other))
diff --git a/src/lib/pubkey/mce/mceliece_key.h b/src/lib/pubkey/mce/mceliece_key.h
deleted file mode 100644
index 65ab04f16..000000000
--- a/src/lib/pubkey/mce/mceliece_key.h
+++ /dev/null
@@ -1,126 +0,0 @@
-/**
- * (C) Copyright Projet SECRET, INRIA, Rocquencourt
- * (C) Bhaskar Biswas and  Nicolas Sendrier
- *
- * (C) 2014 cryptosource GmbH
- * (C) 2014 Falko Strenzke [email protected]
- *
- * Botan is released under the Simplified BSD License (see license.txt)
- *
- */
-
-#ifndef BOTAN_MCELIECE_KEY_H__
-#define BOTAN_MCELIECE_KEY_H__
-
-#include <botan/exceptn.h>
-#include <botan/pk_keys.h>
-#include <botan/polyn_gf2m.h>
-
-namespace Botan {
-
-class BOTAN_DLL McEliece_PublicKey : public virtual Public_Key
-   {
-   public:
-
-      McEliece_PublicKey(const std::vector<byte>& key_bits);
-
-      McEliece_PublicKey(std::vector<byte> const& pub_matrix, u32bit the_t, u32bit the_code_length) :
-         m_public_matrix(pub_matrix),
-         m_t(the_t),
-         m_code_length(the_code_length)
-            {}
-
-      McEliece_PublicKey(const McEliece_PublicKey & other);
-
-      std::string algo_name() const override { return "McEliece"; }
-
-      /**
-      * Get the maximum number of bits allowed to be fed to this key.
-      * This is the bitlength of the order of the base point.
-      * @result the maximum number of input bits
-      */
-      size_t max_input_bits() const override
-         {
-         return get_message_word_bit_length();
-         };
-
-      AlgorithmIdentifier algorithm_identifier() const override;
-
-      size_t estimated_strength() const override;
-
-      std::vector<byte> x509_subject_public_key() const override;
-
-      bool check_key(RandomNumberGenerator&, bool) const override
-         { return true; }
-
-      u32bit get_t() const { return m_t; }
-      u32bit get_code_length() const { return m_code_length; }
-      u32bit get_message_word_bit_length() const;
-      std::vector<byte> const& get_public_matrix() const { return m_public_matrix; }
-
-      bool operator==(const McEliece_PublicKey& other) const;
-      bool operator!=(const McEliece_PublicKey& other) const { return !(*this == other); }
-
-   protected:
-      McEliece_PublicKey() {}
-
-      std::vector<byte> m_public_matrix;
-      u32bit m_t;
-      u32bit m_code_length;
-   };
-
-class BOTAN_DLL McEliece_PrivateKey : public virtual McEliece_PublicKey,
-                                      public virtual Private_Key
-   {
-   public:
-      /**
-      * Get the maximum number of bits allowed to be fed to this key.
-      * This is the bitlength of the order of the base point.
-      * @result the maximum number of input bits
-      */
-      size_t max_input_bits() const override {
-      return m_Linv.size();
-      };
-
-      McEliece_PrivateKey(const secure_vector<byte>& key_bits);
-
-      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_PrivateKey(RandomNumberGenerator& rng, size_t code_length, size_t t);
-      bool check_key(RandomNumberGenerator& rng, bool strong) const override;
-
-      polyn_gf2m const& get_goppa_polyn() const { return m_g; };
-      std::vector<u32bit> const& get_H_coeffs() const { return m_coeffs; };
-      std::vector<gf2m> const& get_Linv() const { return m_Linv; };
-      std::vector<polyn_gf2m> const& get_sqrtmod() const { return m_sqrtmod; };
-
-      inline u32bit get_dimension() const
-         { return m_dimension; };
-
-      inline u32bit get_codimension() const
-         { return m_codimension; };
-
-
-      secure_vector<byte> pkcs8_private_key() const override;
-
-      bool operator==(const McEliece_PrivateKey & other) const;
-
-      bool operator!=(const McEliece_PrivateKey& other) const { return !(*this == other); };
-
-   private:
-      polyn_gf2m m_g;
-      std::vector<polyn_gf2m> m_sqrtmod;
-      std::vector<gf2m> m_Linv;
-      std::vector<u32bit> m_coeffs;
-
-      u32bit m_codimension;
-      u32bit m_dimension;
-   };
-
-}
-
-#endif
diff --git a/src/lib/pubkey/mce/polyn_gf2m.cpp b/src/lib/pubkey/mce/polyn_gf2m.cpp
index 9b3366757..9133f9174 100644
--- a/src/lib/pubkey/mce/polyn_gf2m.cpp
+++ b/src/lib/pubkey/mce/polyn_gf2m.cpp
@@ -10,15 +10,13 @@
  */
 
 #include <botan/polyn_gf2m.h>
-#include <botan/gf2m_rootfind_dcmp.h>
-#include <botan/code_based_util.h>
-#include <botan/gf2m_small_m.h>
+#include <botan/internal/code_based_util.h>
 #include <botan/internal/bit_ops.h>
+#include <botan/rng.h>
+#include <botan/exceptn.h>
 
 namespace Botan {
 
-using namespace Botan::gf2m_small_m;
-
 namespace {
 
 gf2m generate_gf2m_mask(gf2m a)
@@ -40,8 +38,6 @@ unsigned nlz_16bit(u16bit x)
    }
 }
 
-using namespace Botan::gf2m_small_m;
-
 int polyn_gf2m::calc_degree_secure() const
    {
    int i = this->coeff.size() - 1;
@@ -86,7 +82,7 @@ polyn_gf2m::polyn_gf2m(polyn_gf2m const& other)
     msp_field(other.msp_field)
    { }
 
-polyn_gf2m::polyn_gf2m(   int d, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field)
+polyn_gf2m::polyn_gf2m(   int d, std::shared_ptr<GF2m_Field> sp_field)
    :m_deg(-1),
     coeff(d+1),
     msp_field(sp_field)
@@ -115,7 +111,7 @@ void polyn_gf2m::realloc(u32bit new_size)
    this->coeff = secure_vector<gf2m>(new_size);
    }
 
-polyn_gf2m::polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field)
+polyn_gf2m::polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<GF2m_Field> sp_field)
    :msp_field(sp_field)
    {
    if(mem_len % sizeof(gf2m))
@@ -128,7 +124,7 @@ polyn_gf2m::polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<gf2m_sma
    this->m_deg = -1;
    for(u32bit i = 0; i < size; i++)
       {
-      this->coeff[i] = gf2m_small_m::decode_gf2m(mem);
+      this->coeff[i] = decode_gf2m(mem);
       mem += sizeof(this->coeff[0]);
       }
    for(u32bit i = 0; i < size; i++)
@@ -142,13 +138,13 @@ polyn_gf2m::polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<gf2m_sma
    }
 
 
-polyn_gf2m::polyn_gf2m( std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field )
+polyn_gf2m::polyn_gf2m( std::shared_ptr<GF2m_Field> sp_field )
    : m_deg(-1),
      coeff(1),
      msp_field(sp_field)
    {}
 
-polyn_gf2m::polyn_gf2m(int degree, const unsigned  char* mem, u32bit mem_byte_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field)
+polyn_gf2m::polyn_gf2m(int degree, const unsigned  char* mem, u32bit mem_byte_len, std::shared_ptr<GF2m_Field> sp_field)
    :msp_field(sp_field)
    {
    u32bit j, k, l;
@@ -229,7 +225,7 @@ int polyn_gf2m::get_degree() const
    }
 
 
-static gf2m eval_aux(const gf2m * /*restrict*/ coeff, gf2m a, int d, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field)
+static gf2m eval_aux(const gf2m * /*restrict*/ coeff, gf2m a, int d, std::shared_ptr<GF2m_Field> sp_field)
    {
    gf2m b;
    b = coeff[d--];
@@ -255,7 +251,7 @@ gf2m polyn_gf2m::eval(gf2m a)
 void polyn_gf2m::remainder(polyn_gf2m &p, const polyn_gf2m & g)
    {
    int i, j, d;
-   std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field;
+   std::shared_ptr<GF2m_Field> msp_field = g.msp_field;
    d = p.get_degree() - g.get_degree();
    if (d >= 0) {
    gf2m la = msp_field->gf_inv_rn(g.get_lead_coef());
@@ -314,7 +310,7 @@ polyn_gf2m polyn_gf2m::sqmod( const std::vector<polyn_gf2m> & sq, int d)
    {
    int i, j;
    gf2m la;
-   std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field = this->msp_field;
+   std::shared_ptr<GF2m_Field> sp_field = this->msp_field;
 
    polyn_gf2m result(d - 1, sp_field);
    // terms of low degree
@@ -438,7 +434,7 @@ void polyn_gf2m::patchup_deg_secure( u32bit trgt_deg, volatile gf2m patch_elem)
 std::pair<polyn_gf2m, polyn_gf2m> polyn_gf2m::eea_with_coefficients( const polyn_gf2m & p, const polyn_gf2m & g, int break_deg)
    {
 
-   std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field;
+   std::shared_ptr<GF2m_Field> msp_field = g.msp_field;
    int i, j, dr, du, delta;
    gf2m a;
    polyn_gf2m aux;
@@ -625,7 +621,7 @@ std::pair<polyn_gf2m, polyn_gf2m> polyn_gf2m::eea_with_coefficients( const polyn
    return std::make_pair(u1,r1); // coefficients u,v
    }
 
-polyn_gf2m::polyn_gf2m(int t, Botan::RandomNumberGenerator& rng, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field)
+polyn_gf2m::polyn_gf2m(int t, Botan::RandomNumberGenerator& rng, std::shared_ptr<GF2m_Field> sp_field)
    :m_deg(t),
     coeff(t+1),
     msp_field(sp_field)
@@ -655,7 +651,7 @@ void polyn_gf2m::poly_shiftmod( const polyn_gf2m & g)
       {
       throw Invalid_Argument("shiftmod cannot be called on polynomials of degree 0 or less");
       }
-   std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field;
+   std::shared_ptr<GF2m_Field> msp_field = g.msp_field;
 
    t = g.get_degree();
    a = msp_field->gf_div(this->coeff[t-1], g.coeff[t]);
@@ -670,7 +666,7 @@ std::vector<polyn_gf2m> polyn_gf2m::sqrt_mod_init(const polyn_gf2m & g)
    {
    u32bit i, t;
    u32bit nb_polyn_sqrt_mat;
-   std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = g.msp_field;
+   std::shared_ptr<GF2m_Field> msp_field = g.msp_field;
    std::vector<polyn_gf2m> result;
    t = g.get_degree();
    nb_polyn_sqrt_mat = t/2;
@@ -717,7 +713,7 @@ std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<g
    gf2m a;
 
 
-   std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field = generator.msp_field;
+   std::shared_ptr<GF2m_Field> msp_field = generator.msp_field;
 
    std::vector<polyn_gf2m> result;
    t = generator.get_degree();
@@ -744,7 +740,7 @@ std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<g
    return result;
    }
 
-polyn_gf2m::polyn_gf2m(const secure_vector<byte>& encoded, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field )
+polyn_gf2m::polyn_gf2m(const secure_vector<byte>& encoded, std::shared_ptr<GF2m_Field> sp_field )
    :msp_field(sp_field)
    {
    if(encoded.size() % 2)
diff --git a/src/lib/pubkey/mce/polyn_gf2m.h b/src/lib/pubkey/mce/polyn_gf2m.h
index 6ec028a25..1c8cc5211 100644
--- a/src/lib/pubkey/mce/polyn_gf2m.h
+++ b/src/lib/pubkey/mce/polyn_gf2m.h
@@ -12,14 +12,14 @@
 #ifndef BOTAN_POLYN_GF2M_H__
 #define BOTAN_POLYN_GF2M_H__
 
+#include <botan/secmem.h>
 #include <botan/gf2m_small_m.h>
-#include <botan/rng.h>
 #include <memory>
 #include <utility>
 
 namespace Botan {
 
-using namespace gf2m_small_m;
+class RandomNumberGenerator;
 
 struct polyn_gf2m
    {
@@ -27,13 +27,13 @@ struct polyn_gf2m
       /**
       * create a zero polynomial:
       */
-      polyn_gf2m( std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field );
+      polyn_gf2m( std::shared_ptr<GF2m_Field> sp_field );
 
       polyn_gf2m()
          :m_deg(-1)
          {};
 
-      polyn_gf2m(const secure_vector<byte>& encoded, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field );
+      polyn_gf2m(const secure_vector<byte>& encoded, std::shared_ptr<GF2m_Field> sp_field );
 
       polyn_gf2m& operator=(const polyn_gf2m&) = default;
 
@@ -61,7 +61,7 @@ struct polyn_gf2m
       /**
       * create zero polynomial with reservation of space for a degree d polynomial
       */
-      polyn_gf2m(int d, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field);
+      polyn_gf2m(int d, std::shared_ptr<GF2m_Field> sp_field);
 
       polyn_gf2m(polyn_gf2m const& other);
       /**
@@ -71,9 +71,9 @@ struct polyn_gf2m
       /**
       * random irreducible polynomial of degree t
       */
-      polyn_gf2m(int t, RandomNumberGenerator& rng, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field);
+      polyn_gf2m(int t, RandomNumberGenerator& rng, std::shared_ptr<GF2m_Field> sp_field);
 
-      std::shared_ptr<gf2m_small_m::Gf2m_Field> get_sp_field() const
+      std::shared_ptr<GF2m_Field> get_sp_field() const
          { return msp_field; };
 
       gf2m& operator[](size_t i) { return coeff[i]; };
@@ -97,12 +97,12 @@ struct polyn_gf2m
       std::string to_string() const;
 
       /** decode a polynomial from memory: **/
-      polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field);
+      polyn_gf2m(const byte* mem, u32bit mem_len, std::shared_ptr<GF2m_Field> sp_field);
       // remove one! ^v!
       /**
       *  create a polynomial from memory area (encoded)
       */
-      polyn_gf2m(int degree, const unsigned  char* mem, u32bit mem_byte_len, std::shared_ptr<gf2m_small_m::Gf2m_Field> sp_field);
+      polyn_gf2m(int degree, const unsigned  char* mem, u32bit mem_byte_len, std::shared_ptr<GF2m_Field> sp_field);
 
       void encode(u32bit min_numo_coeffs, byte* mem, u32bit mem_len) const;
 
@@ -149,13 +149,19 @@ struct polyn_gf2m
    public:
       int m_deg;
       secure_vector<gf2m> coeff;
-      std::shared_ptr<gf2m_small_m::Gf2m_Field> msp_field;
+      std::shared_ptr<GF2m_Field> msp_field;
    };
 
 gf2m random_code_element(unsigned code_length, RandomNumberGenerator& rng);
 
 std::vector<polyn_gf2m> syndrome_init(polyn_gf2m const& generator, std::vector<gf2m> const& support, int n);
 
+/**
+* Find the roots of a polynomial over GF(2^m) using the method by Federenko
+* et al.
+*/
+secure_vector<gf2m> find_roots_gf2m_decomp(const polyn_gf2m & polyn, u32bit code_length);
+
 }
 
 #endif
diff --git a/src/lib/pubkey/mce/workfactor.cpp b/src/lib/pubkey/mce/workfactor.cpp
index e7cf631d4..9594c0aab 100644
--- a/src/lib/pubkey/mce/workfactor.cpp
+++ b/src/lib/pubkey/mce/workfactor.cpp
@@ -8,6 +8,7 @@
  */
 
 #include <botan/mceliece.h>
+#include <botan/internal/bit_ops.h>
 #include <cmath>
 
 namespace Botan {
@@ -91,8 +92,10 @@ double best_wf(size_t n, size_t k, size_t w, size_t p)
 
 }
 
-size_t mceliece_work_factor(size_t n, size_t k, size_t t)
+size_t mceliece_work_factor(size_t n, size_t t)
    {
+   const size_t k = n - ceil_log2(n) * t;
+
    double min = cout_total(n, k, t, 0, 0); // correspond a p=1
    for(size_t p = 0; p != t / 2; ++p)
       {
diff --git a/src/lib/pubkey/mceies/mceies.cpp b/src/lib/pubkey/mceies/mceies.cpp
index 58dde2e27..d4d956a54 100644
--- a/src/lib/pubkey/mceies/mceies.cpp
+++ b/src/lib/pubkey/mceies/mceies.cpp
@@ -31,9 +31,10 @@ secure_vector<byte> aead_key(const secure_vector<byte>& mk,
 
 secure_vector<byte>
 mceies_encrypt(const McEliece_PublicKey& pubkey,
-               const secure_vector<byte>& pt,
-               byte ad[], size_t ad_len,
-               RandomNumberGenerator& rng)
+               const byte pt[], size_t pt_len,
+               const byte ad[], size_t ad_len,
+               RandomNumberGenerator& rng,
+               const std::string& algo)
    {
    McEliece_KEM_Encryptor kem_op(pubkey);
 
@@ -45,7 +46,6 @@ mceies_encrypt(const McEliece_PublicKey& pubkey,
 
    BOTAN_ASSERT(mce_ciphertext.size() == mce_code_bytes, "Unexpected size");
 
-   const std::string algo = "AES-256/OCB";
    std::unique_ptr<AEAD_Mode> aead(get_aead(algo, ENCRYPTION));
    if(!aead)
       throw std::runtime_error("mce_encrypt unable to create AEAD instance '" + algo + "'");
@@ -57,10 +57,10 @@ mceies_encrypt(const McEliece_PublicKey& pubkey,
 
    const secure_vector<byte> nonce = rng.random_vec(nonce_len);
 
-   secure_vector<byte> msg(mce_ciphertext.size() + nonce.size() + pt.size());
+   secure_vector<byte> msg(mce_ciphertext.size() + nonce.size() + pt_len);
    copy_mem(msg.data(), mce_ciphertext.data(), mce_ciphertext.size());
    copy_mem(msg.data() + mce_ciphertext.size(), nonce.data(), nonce.size());
-   copy_mem(msg.data() + mce_ciphertext.size() + nonce.size(), pt.data(), pt.size());
+   copy_mem(msg.data() + mce_ciphertext.size() + nonce.size(), pt, pt_len);
 
    aead->start(nonce);
    aead->finish(msg, mce_ciphertext.size() + nonce.size());
@@ -69,8 +69,9 @@ mceies_encrypt(const McEliece_PublicKey& pubkey,
 
 secure_vector<byte>
 mceies_decrypt(const McEliece_PrivateKey& privkey,
-               const secure_vector<byte>& ct,
-               byte ad[], size_t ad_len)
+               const byte ct[], size_t ct_len,
+               const byte ad[], size_t ad_len,
+               const std::string& algo)
    {
    try
       {
@@ -78,23 +79,21 @@ mceies_decrypt(const McEliece_PrivateKey& privkey,
 
       const size_t mce_code_bytes = (privkey.get_code_length() + 7) / 8;
 
-
-      const std::string algo = "AES-256/OCB";
       std::unique_ptr<AEAD_Mode> aead(get_aead(algo, DECRYPTION));
       if(!aead)
          throw std::runtime_error("Unable to create AEAD instance '" + algo + "'");
 
       const size_t nonce_len = aead->default_nonce_length();
 
-      if(ct.size() < mce_code_bytes + nonce_len + aead->tag_size())
+      if(ct_len < mce_code_bytes + nonce_len + aead->tag_size())
          throw std::runtime_error("Input message too small to be valid");
 
-      const secure_vector<byte> mce_key = kem_op.decrypt(ct.data(), mce_code_bytes);
+      const secure_vector<byte> mce_key = kem_op.decrypt(ct, mce_code_bytes);
 
       aead->set_key(aead_key(mce_key, *aead));
       aead->set_associated_data(ad, ad_len);
 
-      secure_vector<byte> pt(ct.begin() + mce_code_bytes + nonce_len, ct.end());
+      secure_vector<byte> pt(ct + mce_code_bytes + nonce_len, ct + ct_len);
 
       aead->start(&ct[mce_code_bytes], nonce_len);
       aead->finish(pt, 0);
diff --git a/src/lib/pubkey/mceies/mceies.h b/src/lib/pubkey/mceies/mceies.h
index 9ead21a17..b43e2065f 100644
--- a/src/lib/pubkey/mceies/mceies.h
+++ b/src/lib/pubkey/mceies/mceies.h
@@ -23,9 +23,10 @@ class McEliece_PrivateKey;
 */
 secure_vector<byte>
 BOTAN_DLL mceies_encrypt(const McEliece_PublicKey& pubkey,
-                         const secure_vector<byte>& pt,
-                         byte ad[], size_t ad_len,
-                         RandomNumberGenerator& rng);
+                         const byte pt[], size_t pt_len,
+                         const byte ad[], size_t ad_len,
+                         RandomNumberGenerator& rng,
+                         const std::string& aead = "AES-256/OCB");
 
 /**
 * McEliece Integrated Encryption System
@@ -34,8 +35,9 @@ BOTAN_DLL mceies_encrypt(const McEliece_PublicKey& pubkey,
 */
 secure_vector<byte>
 BOTAN_DLL mceies_decrypt(const McEliece_PrivateKey& privkey,
-                         const secure_vector<byte>& ct,
-                         byte ad[], size_t ad_len);
+                         const byte ct[], size_t ct_len,
+                         const byte ad[], size_t ad_len,
+                         const std::string& aead = "AES-256/OCB");
 
 
 }
diff --git a/src/lib/pubkey/pk_algs.cpp b/src/lib/pubkey/pk_algs.cpp
index 75264d56f..689237a84 100644
--- a/src/lib/pubkey/pk_algs.cpp
+++ b/src/lib/pubkey/pk_algs.cpp
@@ -48,6 +48,10 @@
   #include <botan/curve25519.h>
 #endif
 
+#if defined(BOTAN_HAS_MCELIECE)
+  #include <botan/mceliece.h>
+#endif
+
 namespace Botan {
 
 Public_Key* make_public_key(const AlgorithmIdentifier& alg_id,
@@ -107,6 +111,11 @@ Public_Key* make_public_key(const AlgorithmIdentifier& alg_id,
       return new Curve25519_PublicKey(alg_id, key_bits);
 #endif
 
+#if defined(BOTAN_HAS_MCELIECE)
+   if(alg_name == "McEliece")
+      return new McEliece_PublicKey(unlock(key_bits));
+#endif
+
    throw Decoding_Error("Unhandled PK algorithm " + alg_name);
    }
 
@@ -168,6 +177,11 @@ Private_Key* make_private_key(const AlgorithmIdentifier& alg_id,
       return new Curve25519_PrivateKey(alg_id, key_bits, rng);
 #endif
 
+#if defined(BOTAN_HAS_MCELIECE)
+   if(alg_name == "McEliece")
+      return new McEliece_PrivateKey(key_bits);
+#endif
+
    throw Decoding_Error("Unhandled PK algorithm " + alg_name);
    }