Add specialized reducers for P-192, P-224, P-256 and P-384

4 files changed, 636 insertions, 16 deletions

diff --git a/src/lib/math/ec_gfp/curve_gfp.cpp b/src/lib/math/ec_gfp/curve_gfp.cpp
index 02265b53a..cb21dd04e 100644
--- a/src/lib/math/ec_gfp/curve_gfp.cpp
+++ b/src/lib/math/ec_gfp/curve_gfp.cpp
@@ -8,6 +8,7 @@
 #include <botan/curve_gfp.h>
 #include <botan/internal/curve_nistp.h>
 #include <botan/internal/mp_core.h>
+#include <botan/internal/mp_asmi.h>
 
 namespace Botan {
 
@@ -117,25 +118,30 @@ void CurveGFp_Montgomery::curve_sqr(BigInt& z, const BigInt& x,
 }
 
 // Default implementation
-void CurveGFp_Repr::normalize(BigInt& x, secure_vector<word>& ws, size_t /*bound*/) const
+void CurveGFp_Repr::normalize(BigInt& x, secure_vector<word>& ws, size_t bound) const
    {
    const BigInt& p = get_p();
+   const word* prime = p.data();
+   const size_t p_words = get_p_words();
 
    while(x.is_negative())
       x += p;
 
-   const size_t p_words = get_p_words();
-   const word* prime = p.data();
-
    x.grow_to(p_words + 1);
 
    if(ws.size() < p_words + 1)
       ws.resize(p_words + 1);
 
-   //FIXME: take into account bound if > 0
-   while(true)
+   for(size_t i = 0; bound == 0 || i < bound; ++i)
       {
-      if(bigint_sub3(&ws[0], x.data(), p_words, prime, p_words)) // borrow?
+      const word* xd = x.data();
+      word borrow = 0;
+
+      for(size_t i = 0; i != p_words; ++i)
+         ws[i] = word_sub(xd[i], prime[i], &borrow);
+      ws[p_words] = word_sub(xd[p_words], 0, &borrow);
+
+      if(borrow)
          break;
 
       x.swap_reg(ws);
@@ -145,6 +151,17 @@ void CurveGFp_Repr::normalize(BigInt& x, secure_vector<word>& ws, size_t /*bound
 std::shared_ptr<CurveGFp_Repr>
 CurveGFp::choose_repr(const BigInt& p, const BigInt& a, const BigInt& b)
    {
+#if defined(BOTAN_HAS_CURVEGFP_NISTP_M32)
+   if(p == CurveGFp_P192::prime())
+      return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P192(a, b));
+   if(p == CurveGFp_P224::prime())
+      return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P224(a, b));
+   if(p == CurveGFp_P256::prime())
+      return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P256(a, b));
+   if(p == CurveGFp_P384::prime())
+      return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P384(a, b));
+#endif
+
    if(p == CurveGFp_P521::prime())
       return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P521(a, b));
 
diff --git a/src/lib/math/ec_gfp/curve_nistp.cpp b/src/lib/math/ec_gfp/curve_nistp.cpp
index d0ccf929a..4f99b54f0 100644
--- a/src/lib/math/ec_gfp/curve_nistp.cpp
+++ b/src/lib/math/ec_gfp/curve_nistp.cpp
@@ -1,14 +1,12 @@
 /*
 * NIST curve reduction
-* (C) 2014 Jack Lloyd
+* (C) 2014,2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
 #include <botan/internal/curve_nistp.h>
 #include <botan/internal/mp_core.h>
-#include <botan/internal/rounding.h>
-#include <botan/hex.h>
 
 namespace Botan {
 
@@ -92,4 +90,500 @@ void CurveGFp_P521::redc(BigInt& x, secure_vector<word>& ws) const
    normalize(x, ws, max_redc_subtractions());
    }
 
+#if defined(BOTAN_HAS_CURVEGFP_NISTP_M32)
+
+namespace {
+
+/**
+* Treating this MPI as a sequence of 32-bit words in big-endian
+* order, return word i (or 0 if out of range)
+*/
+inline u32bit get_u32bit(const BigInt& x, size_t i)
+   {
+#if (BOTAN_MP_WORD_BITS == 32)
+   return x.word_at(i);
+#elif (BOTAN_MP_WORD_BITS == 64)
+   return (x.word_at(i/2) >> ((i % 2)*32));
+#else
+  #error "Not implemented"
+#endif
+   }
+
+/**
+* Treating this MPI as a sequence of 32-bit words in big-endian
+* order, set word i to the value x
+*/
+inline void set_u32bit(BigInt& x, size_t i, u32bit v)
+   {
+#if (BOTAN_MP_WORD_BITS == 32)
+   x.set_word_at(i, v);
+#elif (BOTAN_MP_WORD_BITS == 64)
+   const word shift_32 = (i % 2) * 32;
+   const word w = (x.word_at(i/2) & (static_cast<word>(0xFFFFFFFF) << (32-shift_32))) | (static_cast<word>(v) << shift_32);
+   x.set_word_at(i/2, w);
+#else
+  #error "Not implemented"
+#endif
+   }
+
+}
+
+//static
+const BigInt& CurveGFp_P192::prime()
+   {
+   static const BigInt p192("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF");
+   return p192;
+   }
+
+void CurveGFp_P192::redc(BigInt& x, secure_vector<word>& ws) const
+   {
+   const u32bit X6 = get_u32bit(x, 6);
+   const u32bit X7 = get_u32bit(x, 7);
+   const u32bit X8 = get_u32bit(x, 8);
+   const u32bit X9 = get_u32bit(x, 9);
+   const u32bit X10 = get_u32bit(x, 10);
+   const u32bit X11 = get_u32bit(x, 11);
+
+   x.mask_bits(192);
+
+   u64bit S = 0;
+
+   S += get_u32bit(x, 0);
+   S += X6;
+   S += X10;
+   set_u32bit(x, 0, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 1);
+   S += X7;
+   S += X11;
+   set_u32bit(x, 1, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 2);
+   S += X6;
+   S += X8;
+   S += X10;
+   set_u32bit(x, 2, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 3);
+   S += X7;
+   S += X9;
+   S += X11;
+   set_u32bit(x, 3, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 4);
+   S += X8;
+   S += X10;
+   set_u32bit(x, 4, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 5);
+   S += X9;
+   S += X11;
+   set_u32bit(x, 5, S);
+   S >>= 32;
+
+   set_u32bit(x, 6, S);
+
+   // No underflow possible
+
+   normalize(x, ws, max_redc_subtractions());
+   }
+
+//static
+const BigInt& CurveGFp_P224::prime()
+   {
+   static const BigInt p224("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001");
+   return p224;
+   }
+
+void CurveGFp_P224::redc(BigInt& x, secure_vector<word>& ws) const
+   {
+   const u32bit X7 = get_u32bit(x, 7);
+   const u32bit X8 = get_u32bit(x, 8);
+   const u32bit X9 = get_u32bit(x, 9);
+   const u32bit X10 = get_u32bit(x, 10);
+   const u32bit X11 = get_u32bit(x, 11);
+   const u32bit X12 = get_u32bit(x, 12);
+   const u32bit X13 = get_u32bit(x, 13);
+
+   x.mask_bits(224);
+
+   // One full copy of P224 is added, so the result is always positive
+
+   int64_t S = 0;
+
+   S += get_u32bit(x, 0);
+   S += 1;
+   S -= X7;
+   S -= X11;
+   set_u32bit(x, 0, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 1);
+   S -= X8;
+   S -= X12;
+   set_u32bit(x, 1, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 2);
+   S -= X9;
+   S -= X13;
+   set_u32bit(x, 2, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 3);
+   S += 0xFFFFFFFF;
+   S += X7;
+   S += X11;
+   S -= X10;
+   set_u32bit(x, 3, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 4);
+   S += 0xFFFFFFFF;
+   S += X8;
+   S += X12;
+   S -= X11;
+   set_u32bit(x, 4, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 5);
+   S += 0xFFFFFFFF;
+   S += X9;
+   S += X13;
+   S -= X12;
+   set_u32bit(x, 5, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 6);
+   S += 0xFFFFFFFF;
+   S += X10;
+   S -= X13;
+   set_u32bit(x, 6, S);
+   S >>= 32;
+   set_u32bit(x, 7, S);
+
+   BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow");
+
+   normalize(x, ws, max_redc_subtractions());
+   }
+
+//static
+const BigInt& CurveGFp_P256::prime()
+   {
+   static const BigInt p256("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF");
+   return p256;
+   }
+
+void CurveGFp_P256::redc(BigInt& x, secure_vector<word>& ws) const
+   {
+   const u32bit X8 = get_u32bit(x, 8);
+   const u32bit X9 = get_u32bit(x, 9);
+   const u32bit X10 = get_u32bit(x, 10);
+   const u32bit X11 = get_u32bit(x, 11);
+   const u32bit X12 = get_u32bit(x, 12);
+   const u32bit X13 = get_u32bit(x, 13);
+   const u32bit X14 = get_u32bit(x, 14);
+   const u32bit X15 = get_u32bit(x, 15);
+
+   x.mask_bits(256);
+
+   int64_t S = 0;
+
+   // Adds 6 * P-256 to prevent underflow
+
+   S = get_u32bit(x, 0);
+   S += 0xFFFFFFFA;
+   S += X8;
+   S += X9;
+   S -= X11;
+   S -= X12;
+   S -= X13;
+   S -= X14;
+   set_u32bit(x, 0, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 1);
+   S += 0xFFFFFFFF;
+   S += X9;
+   S += X10;
+   S -= X12;
+   S -= X13;
+   S -= X14;
+   S -= X15;
+   set_u32bit(x, 1, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 2);
+   S += 0xFFFFFFFF;
+   S += X10;
+   S += X11;
+   S -= X13;
+   S -= X14;
+   S -= X15;
+   set_u32bit(x, 2, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 3);
+   S += 5;
+   S += X11;
+   S += X11;
+   S += X12;
+   S += X12;
+   S += X13;
+   S -= X15;
+   S -= X8;
+   S -= X9;
+   set_u32bit(x, 3, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 4);
+   S += X12;
+   S += X12;
+   S += X13;
+   S += X13;
+   S += X14;
+   S -= X9;
+   S -= X10;
+   set_u32bit(x, 4, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 5);
+   S += X13;
+   S += X13;
+   S += X14;
+   S += X14;
+   S += X15;
+   S -= X10;
+   S -= X11;
+   set_u32bit(x, 5, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 6);
+   S += 6;
+   S += X14;
+   S += X14;
+   S += X15;
+   S += X15;
+   S += X14;
+   S += X13;
+   S -= X8;
+   S -= X9;
+   set_u32bit(x, 6, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 7);
+   S += 0xFFFFFFFA;
+   S += X15;
+   S += X15;
+   S += X15;
+   S += X8;
+   S -= X10;
+   S -= X11;
+   S -= X12;
+   S -= X13;
+   set_u32bit(x, 7, S);
+   S >>= 32;
+
+   S += 5;
+   set_u32bit(x, 8, S);
+
+   BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow");
+
+   if(S >= 2)
+      {
+      BOTAN_ASSERT(S <= 10, "Expected overflow");
+      static const BigInt P256_mults[9] = {
+         2*get_p(),
+         3*get_p(),
+         4*get_p(),
+         5*get_p(),
+         6*get_p(),
+         7*get_p(),
+         8*get_p(),
+         9*get_p(),
+         10*get_p()
+      };
+      x -= P256_mults[S - 2];
+      }
+
+   normalize(x, ws, max_redc_subtractions());
+   }
+
+//static
+const BigInt& CurveGFp_P384::prime()
+   {
+   static const BigInt p384("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF");
+   return p384;
+   }
+
+void CurveGFp_P384::redc(BigInt& x, secure_vector<word>& ws) const
+   {
+   const u32bit X12 = get_u32bit(x, 12);
+   const u32bit X13 = get_u32bit(x, 13);
+   const u32bit X14 = get_u32bit(x, 14);
+   const u32bit X15 = get_u32bit(x, 15);
+   const u32bit X16 = get_u32bit(x, 16);
+   const u32bit X17 = get_u32bit(x, 17);
+   const u32bit X18 = get_u32bit(x, 18);
+   const u32bit X19 = get_u32bit(x, 19);
+   const u32bit X20 = get_u32bit(x, 20);
+   const u32bit X21 = get_u32bit(x, 21);
+   const u32bit X22 = get_u32bit(x, 22);
+   const u32bit X23 = get_u32bit(x, 23);
+
+   x.mask_bits(384);
+
+   int64_t S = 0;
+
+   // One copy of P-384 is added to prevent underflow
+   S = get_u32bit(x, 0);
+   S += 0xFFFFFFFF;
+   S += X12;
+   S += X21;
+   S += X20;
+   S -= X23;
+   set_u32bit(x, 0, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 1);
+   S += X13;
+   S += X22;
+   S += X23;
+   S -= X12;
+   S -= X20;
+   set_u32bit(x, 1, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 2);
+   S += X14;
+   S += X23;
+   S -= X13;
+   S -= X21;
+   set_u32bit(x, 2, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 3);
+   S += 0xFFFFFFFF;
+   S += X15;
+   S += X12;
+   S += X20;
+   S += X21;
+   S -= X14;
+   S -= X22;
+   S -= X23;
+   set_u32bit(x, 3, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 4);
+   S += 0xFFFFFFFE;
+   S += X21;
+   S += X21;
+   S += X16;
+   S += X13;
+   S += X12;
+   S += X20;
+   S += X22;
+   S -= X15;
+   S -= X23;
+   S -= X23;
+   set_u32bit(x, 4, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 5);
+   S += 0xFFFFFFFF;
+   S += X22;
+   S += X22;
+   S += X17;
+   S += X14;
+   S += X13;
+   S += X21;
+   S += X23;
+   S -= X16;
+   set_u32bit(x, 5, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 6);
+   S += 0xFFFFFFFF;
+   S += X23;
+   S += X23;
+   S += X18;
+   S += X15;
+   S += X14;
+   S += X22;
+   S -= X17;
+   set_u32bit(x, 6, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 7);
+   S += 0xFFFFFFFF;
+   S += X19;
+   S += X16;
+   S += X15;
+   S += X23;
+   S -= X18;
+   set_u32bit(x, 7, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 8);
+   S += 0xFFFFFFFF;
+   S += X20;
+   S += X17;
+   S += X16;
+   S -= X19;
+   set_u32bit(x, 8, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 9);
+   S += 0xFFFFFFFF;
+   S += X21;
+   S += X18;
+   S += X17;
+   S -= X20;
+   set_u32bit(x, 9, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 10);
+   S += 0xFFFFFFFF;
+   S += X22;
+   S += X19;
+   S += X18;
+   S -= X21;
+   set_u32bit(x, 10, S);
+   S >>= 32;
+
+   S += get_u32bit(x, 11);
+   S += 0xFFFFFFFF;
+   S += X23;
+   S += X20;
+   S += X19;
+   S -= X22;
+   set_u32bit(x, 11, S);
+   S >>= 32;
+   BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow");
+   set_u32bit(x, 12, S);
+
+   if(S >= 2)
+      {
+      BOTAN_ASSERT(S <= 4, "Expected overflow");
+
+      static const BigInt P384_mults[3] = {
+         2*get_p(),
+         3*get_p(),
+         4*get_p()
+      };
+
+      x -= P384_mults[S - 2];
+      }
+
+   normalize(x, ws, max_redc_subtractions());
+   }
+
+#endif
+
+
 }
diff --git a/src/lib/math/ec_gfp/curve_nistp.h b/src/lib/math/ec_gfp/curve_nistp.h
index 3a1a603c8..0bf707f58 100644
--- a/src/lib/math/ec_gfp/curve_nistp.h
+++ b/src/lib/math/ec_gfp/curve_nistp.h
@@ -52,6 +52,83 @@ class CurveGFp_NIST : public CurveGFp_Repr
       size_t m_p_words; // cache of m_p.sig_words()
    };
 
+#if (BOTAN_MP_WORD_BITS == 32) || (BOTAN_MP_WORD_BITS == 64)
+
+#define BOTAN_HAS_CURVEGFP_NISTP_M32
+
+/**
+* The NIST P-192 curve
+*/
+class CurveGFp_P192 : public CurveGFp_NIST
+   {
+   public:
+      CurveGFp_P192(const BigInt& a, const BigInt& b) : CurveGFp_NIST(192, a, b) {}
+
+      static const BigInt& prime();
+
+      const BigInt& get_p() const override { return CurveGFp_P192::prime(); }
+
+   private:
+      void redc(BigInt& x, secure_vector<word>& ws) const override;
+
+      size_t max_redc_subtractions() const override { return 3; }
+   };
+
+/**
+* The NIST P-224 curve
+*/
+class CurveGFp_P224 : public CurveGFp_NIST
+   {
+   public:
+      CurveGFp_P224(const BigInt& a, const BigInt& b) : CurveGFp_NIST(224, a, b) {}
+
+      static const BigInt& prime();
+
+      const BigInt& get_p() const override { return CurveGFp_P224::prime(); }
+   private:
+      void redc(BigInt& x, secure_vector<word>& ws) const override;
+
+      size_t max_redc_subtractions() const override { return 3; }
+   };
+
+/**
+* The NIST P-256 curve
+*/
+class CurveGFp_P256 : public CurveGFp_NIST
+   {
+   public:
+      CurveGFp_P256(const BigInt& a, const BigInt& b) : CurveGFp_NIST(256, a, b) {}
+
+      static const BigInt& prime();
+
+      const BigInt& get_p() const override { return CurveGFp_P256::prime(); }
+
+   private:
+      void redc(BigInt& x, secure_vector<word>& ws) const override;
+
+      size_t max_redc_subtractions() const override { return 10; }
+   };
+
+/**
+* The NIST P-384 curve
+*/
+class CurveGFp_P384 : public CurveGFp_NIST
+   {
+   public:
+      CurveGFp_P384(const BigInt& a, const BigInt& b) : CurveGFp_NIST(384, a, b) {}
+
+      static const BigInt& prime();
+
+      const BigInt& get_p() const override { return CurveGFp_P384::prime(); }
+
+   private:
+      void redc(BigInt& x, secure_vector<word>& ws) const override;
+
+      size_t max_redc_subtractions() const override { return 4; }
+   };
+
+#endif
+
 /**
 * The NIST P-521 curve
 */
diff --git a/src/lib/math/ec_gfp/point_gfp.cpp b/src/lib/math/ec_gfp/point_gfp.cpp
index 103bb35b5..2505e4d54 100644
--- a/src/lib/math/ec_gfp/point_gfp.cpp
+++ b/src/lib/math/ec_gfp/point_gfp.cpp
@@ -277,17 +277,16 @@ PointGFp operator*(const BigInt& scalar, const PointGFp& point)
 
    const size_t scalar_bits = scalar.bits();
 
-   PointGFp x1 = PointGFp(curve);
-   PointGFp x2 = point;
+   PointGFp x1(curve); // zero
 
    size_t bits_left = scalar_bits;
 
-   // Montgomery Ladder
+#if BOTAN_CURVE_GFP_USE_MONTGOMERY_LADDER
+
+   PointGFp x2 = point;
    while(bits_left)
       {
-      const bool bit_set = scalar.get_bit(bits_left - 1);
-
-      if(bit_set)
+      if(scalar.get_bit(bits_left - 1))
          {
          x1.add(x2, ws);
          x2.mult2(ws);
@@ -301,6 +300,39 @@ PointGFp operator*(const BigInt& scalar, const PointGFp& point)
       --bits_left;
       }
 
+#else
+   const size_t window_bits = 4;
+
+   std::vector<PointGFp> Ps(1 << window_bits);
+   Ps[0] = x1;
+   Ps[1] = point;
+
+   for(size_t i = 2; i < Ps.size(); ++i)
+      {
+      Ps[i] = Ps[i-1];
+      Ps[i].add(point, ws);
+      }
+
+   while(bits_left >= window_bits)
+      {
+      for(size_t i = 0; i != window_bits; ++i)
+         x1.mult2(ws);
+
+      const u32bit nibble = scalar.get_substring(bits_left - window_bits, window_bits);
+      x1.add(Ps[nibble], ws);
+      bits_left -= window_bits;
+      }
+
+   while(bits_left)
+      {
+      x1.mult2(ws);
+      if(scalar.get_bit(bits_left-1))
+         x1.add(point, ws);
+      --bits_left;
+      }
+
+#endif
+
    if(scalar.is_negative())
       x1.negate();