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

8 files changed, 674 insertions, 55 deletions

diff --git a/src/build-data/buildh.in b/src/build-data/buildh.in
index fdb141ffb..02f2731d6 100644
--- a/src/build-data/buildh.in
+++ b/src/build-data/buildh.in
@@ -50,6 +50,12 @@ otherwise does a byte at a time write via a volatile pointer.
 */
 #define BOTAN_USE_VOLATILE_MEMSET_FOR_ZERO 1
 
+/*
+* If enabled the ECC implementation will use Montgomery ladder
+* instead of a fixed window implementation.
+*/
+#define BOTAN_CURVE_GFP_USE_MONTGOMERY_LADDER 0
+
 /* PK key consistency checking toggles */
 #define BOTAN_PUBLIC_KEY_STRONG_CHECKS_ON_LOAD 1
 #define BOTAN_PRIVATE_KEY_STRONG_CHECKS_ON_LOAD 0
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index 6acd04f00..b5a8e0dd5 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -1,6 +1,6 @@
 /*
 * BigInt Base
-* (C) 1999-2011,2012 Jack Lloyd
+* (C) 1999-2011,2012,2014 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -93,15 +93,6 @@ BigInt::BigInt(RandomNumberGenerator& rng, size_t bits)
    }
 
 /*
-* Grow the internal storage
-*/
-void BigInt::grow_to(size_t n)
-   {
-   if(n > size())
-      m_reg.resize(round_up<size_t>(n, 8));
-   }
-
-/*
 * Comparison Function
 */
 s32bit BigInt::cmp(const BigInt& other, bool check_signs) const
@@ -155,8 +146,8 @@ u32bit BigInt::to_u32bit() const
       throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
 
    u32bit out = 0;
-   for(u32bit j = 0; j != 4; ++j)
-      out = (out << 8) | byte_at(3-j);
+   for(size_t i = 0; i != 4; ++i)
+      out = (out << 8) | byte_at(3-i);
    return out;
    }
 
@@ -183,30 +174,6 @@ void BigInt::clear_bit(size_t n)
    }
 
 /*
-* Clear all but the lowest n bits
-*/
-void BigInt::mask_bits(size_t n)
-   {
-   if(n == 0) { clear(); return; }
-
-   const size_t top_word = n / MP_WORD_BITS;
-   const word mask = (static_cast<word>(1) << (n % MP_WORD_BITS)) - 1;
-
-   if(top_word < size())
-      clear_mem(&m_reg[top_word+1], size() - (top_word + 1));
-
-   m_reg[top_word] &= mask;
-   }
-
-/*
-* Count how many bytes are being used
-*/
-size_t BigInt::bytes() const
-   {
-   return (bits() + 7) / 8;
-   }
-
-/*
 * Count how many bits are being used
 */
 size_t BigInt::bits() const
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 4993f5d0c..269a74259 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -269,7 +269,19 @@ class BOTAN_DLL BigInt
      * Clear all but the lowest n bits
      * @param n amount of bits to keep
      */
-     void mask_bits(size_t n);
+     void mask_bits(size_t n)
+        {
+        if(n == 0) { clear(); return; }
+
+        const size_t top_word = n / BOTAN_MP_WORD_BITS;
+        const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1;
+
+        if(top_word < size())
+           {
+           clear_mem(&m_reg[top_word+1], size() - (top_word + 1));
+           m_reg[top_word] &= mask;
+           }
+        }
 
      /**
      * Return bit value at specified position
@@ -315,6 +327,12 @@ class BOTAN_DLL BigInt
      word word_at(size_t n) const
         { return ((n < size()) ? m_reg[n] : 0); }
 
+     void set_word_at(size_t i, word w)
+        {
+        grow_to(i + 1);
+        m_reg[i] = w;
+        }
+
      /**
      * Tests if the sign of the integer is negative
      * @result true, iff the integer has a negative sign
@@ -378,7 +396,7 @@ class BOTAN_DLL BigInt
      * Give byte length of the integer
      * @result byte length of the represented integer value
      */
-     size_t bytes() const;
+     size_t bytes() const { return (bits() + 7) / 8; }
 
      /**
      * Get the bit length of the integer
@@ -398,11 +416,18 @@ class BOTAN_DLL BigInt
      */
      const word* data() const { return &m_reg[0]; }
 
+     secure_vector<word>& get_word_vector() { return m_reg; }
+     const secure_vector<word>& get_word_vector() const { return m_reg; }
+
      /**
      * Increase internal register buffer to at least n words
      * @param n new size of register
      */
-     void grow_to(size_t n);
+     void grow_to(size_t n)
+        {
+        if(n > size())
+           m_reg.resize(n + (8 - n % 8));
+        }
 
      /**
      * Fill BigInt with a random number with size of bitsize
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();
 
diff --git a/src/lib/utils/types.h b/src/lib/utils/types.h
index 4427038a6..d1de9e2a6 100644
--- a/src/lib/utils/types.h
+++ b/src/lib/utils/types.h
@@ -24,6 +24,7 @@ using ::uint16_t;
 using ::uint32_t;
 using ::uint64_t;
 using ::int32_t;
+using ::int64_t;
 
 using ::size_t;