Add an implementation of McEliece encryption based on HyMES

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

3 files changed, 56 insertions, 13 deletions

diff --git a/src/lib/utils/bit_ops.h b/src/lib/utils/bit_ops.h
index 0072fde71..75a7584ad 100644
--- a/src/lib/utils/bit_ops.h
+++ b/src/lib/utils/bit_ops.h
@@ -1,6 +1,10 @@
 /*
 * Bit/Word Operations
 * (C) 1999-2008 Jack Lloyd
+* (C) Copyright Projet SECRET, INRIA, Rocquencourt
+* (C) Bhaskar Biswas and  Nicolas Sendrier
+* (C) 2014 cryptosource GmbH
+* (C) 2014 Falko Strenzke [email protected]
 *
 * Distributed under the terms of the Botan license
 */
@@ -98,6 +102,24 @@ inline size_t ctz(T n)
    return 8*sizeof(T);
    }
 
+template<typename T>
+size_t ceil_log2(T x)
+   {
+   if(x >> (sizeof(T)*8-1))
+      return sizeof(T)*8;
+
+   size_t result = 0;
+   T compare = 1;
+
+   while(compare < x)
+      {
+      compare <<= 1;
+      result++;
+      }
+
+   return result;
+   }
+
 }
 
 #endif
diff --git a/src/lib/utils/ta_utils.cpp b/src/lib/utils/ta_utils.cpp
index 86cf25969..9a2c0df49 100644
--- a/src/lib/utils/ta_utils.cpp
+++ b/src/lib/utils/ta_utils.cpp
@@ -22,30 +22,42 @@ namespace TA_CM {
 * anywhere.
 */
 
-u32bit gen_mask_u32bit(u32bit in)
+namespace {
+
+template<typename T>
+T expand_mask(T x)
+   {
+   volatile T r = x;
+   for(size_t i = 1; i != sizeof(T) * 8; i *= 2)
+      r |= r >> i;
+   r &= 1;
+   r = ~(r - 1);
+   return r;
+   }
+
+}
+
+u32bit expand_mask_u32bit(u32bit in)
+   {
+   return expand_mask<u32bit>(in);
+   }
+
+u16bit expand_mask_u16bit(u16bit in)
    {
-   volatile u32bit result = in;
-   result |= result >> 1;
-   result |= result >> 2;
-   result |= result >> 4;
-   result |= result >> 8;
-   result |= result >> 16;
-   result &= 1;
-   result = ~(result - 1);
-   return result;
+   return expand_mask<u16bit>(in);
    }
 
 u32bit max_32(u32bit a, u32bit b)
    {
    const u32bit a_larger = b - a; /* negative if a larger */
-   const u32bit mask = gen_mask_u32bit(a_larger >> 31);
+   const u32bit mask = expand_mask<u32bit>(a_larger >> 31);
    return (a & mask) | (b & ~mask);
    }
 
 u32bit min_32(u32bit a, u32bit b)
    {
    const u32bit a_larger = b - a; /* negative if a larger */
-   const u32bit mask = gen_mask_u32bit(a_larger >> 31);
+   const u32bit mask = expand_mask<u32bit>(a_larger >> 31);
    return (a & ~mask) | (b & mask);
    }
 
diff --git a/src/lib/utils/ta_utils.h b/src/lib/utils/ta_utils.h
index 36ee551cc..866a4cc37 100644
--- a/src/lib/utils/ta_utils.h
+++ b/src/lib/utils/ta_utils.h
@@ -21,7 +21,16 @@ namespace TA_CM {
 * @param in an integer
 * @return 0 if in == 0 else 0xFFFFFFFF
 */
-u32bit gen_mask_u32bit(u32bit in);
+u32bit expand_mask_u32bit(u32bit in);
+
+
+/**
+ * Expand an input to a bit mask depending on it being being zero or
+ * non-zero
+ * @ param in the input
+ * @return the mask 0xFFFF if tst is non-zero and 0 otherwise
+ */
+u16bit expand_mask_u16bit(u16bit in);
 
 /**
 * Branch-free maximum