Expose the NIST prime values and reduction operations as plain functions.

Previously they were hidden away as private functions on the CurveGFp
types. This allows directly testing the reduction functions against
other computational methods.

7 files changed, 367 insertions, 285 deletions

diff --git a/src/lib/math/ec_gfp/curve_gfp.cpp b/src/lib/math/ec_gfp/curve_gfp.cpp
index 64d45572d..96fe873af 100644
--- a/src/lib/math/ec_gfp/curve_gfp.cpp
+++ b/src/lib/math/ec_gfp/curve_gfp.cpp
@@ -1,12 +1,12 @@
 /*
 * Elliptic curves over GF(p) Montgomery Representation
-* (C) 2014 Jack Lloyd
+* (C) 2014,2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
 #include <botan/curve_gfp.h>
-#include <botan/internal/curve_nistp.h>
+#include <botan/curve_nistp.h>
 #include <botan/internal/mp_core.h>
 #include <botan/internal/mp_asmi.h>
 
@@ -115,54 +115,170 @@ void CurveGFp_Montgomery::curve_sqr(BigInt& z, const BigInt& x,
                     ws.data());
    }
 
-}
+class CurveGFp_NIST : public CurveGFp_Repr
+   {
+   public:
+      CurveGFp_NIST(size_t p_bits, const BigInt& a, const BigInt& b) :
+         m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS)
+         {
+         }
+
+      const BigInt& get_a() const override { return m_a; }
+
+      const BigInt& get_b() const override { return m_b; }
+
+      size_t get_p_words() const override { return m_p_words; }
+
+      const BigInt& get_a_rep() const override { return m_a; }
+
+      const BigInt& get_b_rep() const override { return m_b; }
+
+      void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override
+         { redc(x, ws); }
+
+      void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override
+         { redc(x, ws); }
+
+      void curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
+                     secure_vector<word>& ws) const override;
+
+      void curve_sqr(BigInt& z, const BigInt& x,
+                     secure_vector<word>& ws) const override;
+   private:
+      virtual void redc(BigInt& x, secure_vector<word>& ws) const = 0;
+
+      // Curve parameters
+      BigInt m_a, m_b;
+      size_t m_p_words; // cache of m_p.sig_words()
+   };
 
-// Default implementation
-void CurveGFp_Repr::normalize(BigInt& x, secure_vector<word>& ws, size_t bound) const
+void CurveGFp_NIST::curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
+                              secure_vector<word>& ws) const
    {
-   const BigInt& p = get_p();
-   const word* prime = p.data();
+   if(x.is_zero() || y.is_zero())
+      {
+      z = 0;
+      return;
+      }
+
    const size_t p_words = get_p_words();
+   const size_t output_size = 2*p_words + 1;
+   ws.resize(2*(p_words+2));
 
-   while(x.is_negative())
-      x += p;
+   z.grow_to(output_size);
+   z.clear();
 
-   x.grow_to(p_words + 1);
+   bigint_mul(z.mutable_data(), output_size, ws.data(),
+              x.data(), x.size(), x.sig_words(),
+              y.data(), y.size(), y.sig_words());
 
-   if(ws.size() < p_words + 1)
-      ws.resize(p_words + 1);
+   this->redc(z, ws);
+   }
 
-   for(size_t i = 0; bound == 0 || i < bound; ++i)
+void CurveGFp_NIST::curve_sqr(BigInt& z, const BigInt& x,
+                              secure_vector<word>& ws) const
+   {
+   if(x.is_zero())
       {
-      const word* xd = x.data();
-      word borrow = 0;
+      z = 0;
+      return;
+      }
+
+   const size_t p_words = get_p_words();
+   const size_t output_size = 2*p_words + 1;
 
-      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);
+   ws.resize(2*(p_words+2));
 
-      if(borrow)
-         break;
+   z.grow_to(output_size);
+   z.clear();
 
-      x.swap_reg(ws);
-      }
+   bigint_sqr(z.mutable_data(), output_size, ws.data(),
+              x.data(), x.size(), x.sig_words());
+
+   this->redc(z, ws);
    }
 
+#if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32)
+
+/**
+* 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) {}
+      const BigInt& get_p() const override { return prime_p192(); }
+   private:
+      void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p192(x, ws); }
+   };
+
+/**
+* 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) {}
+      const BigInt& get_p() const override { return prime_p224(); }
+   private:
+      void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p224(x, ws); }
+   };
+
+/**
+* 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) {}
+      const BigInt& get_p() const override { return prime_p256(); }
+   private:
+      void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p256(x, ws); }
+   };
+
+/**
+* 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) {}
+      const BigInt& get_p() const override { return prime_p384(); }
+   private:
+      void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p384(x, ws); }
+   };
+
+#endif
+
+/**
+* The NIST P-521 curve
+*/
+class CurveGFp_P521 : public CurveGFp_NIST
+   {
+   public:
+      CurveGFp_P521(const BigInt& a, const BigInt& b) : CurveGFp_NIST(521, a, b) {}
+      const BigInt& get_p() const override { return prime_p521(); }
+   private:
+      void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p521(x, ws); }
+   };
+
+}
+
 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())
+#if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32)
+   if(p == prime_p192())
       return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P192(a, b));
-   if(p == CurveGFp_P224::prime())
+   if(p == prime_p224())
       return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P224(a, b));
-   if(p == CurveGFp_P256::prime())
+   if(p == prime_p256())
       return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P256(a, b));
-   if(p == CurveGFp_P384::prime())
+   if(p == prime_p384())
       return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P384(a, b));
 #endif
 
-   if(p == CurveGFp_P521::prime())
+   if(p == prime_p521())
       return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P521(a, b));
 
    return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_Montgomery(p, a, b));
diff --git a/src/lib/math/ec_gfp/curve_gfp.h b/src/lib/math/ec_gfp/curve_gfp.h
index 68fe93274..dde9f633e 100644
--- a/src/lib/math/ec_gfp/curve_gfp.h
+++ b/src/lib/math/ec_gfp/curve_gfp.h
@@ -45,10 +45,6 @@ class CurveGFp_Repr
 
       virtual void curve_sqr(BigInt& z, const BigInt& x,
                              secure_vector<word>& ws) const = 0;
-
-      virtual void normalize(BigInt& x,
-                             secure_vector<word>& ws,
-                             size_t bound) const;
    };
 
 /**
@@ -141,16 +137,6 @@ class BOTAN_DLL CurveGFp
          return z;
          }
 
-      /**
-      * Adjust x to be in [0,p)
-      * @param bound if greater than zero, assume that no more than bound
-      *        additions or subtractions are required to move x into range.
-      */
-      void normalize(BigInt& x, secure_vector<word>& ws, size_t bound = 0) const
-         {
-         m_repr->normalize(x, ws, bound);
-         }
-
       void swap(CurveGFp& other)
          {
          std::swap(m_repr, other.m_repr);
diff --git a/src/lib/math/ec_gfp/curve_nistp.cpp b/src/lib/math/ec_gfp/curve_nistp.cpp
index 002cf2d47..bbc11ff21 100644
--- a/src/lib/math/ec_gfp/curve_nistp.cpp
+++ b/src/lib/math/ec_gfp/curve_nistp.cpp
@@ -1,63 +1,51 @@
 /*
-* NIST curve reduction
+* NIST prime reductions
 * (C) 2014,2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
-#include <botan/internal/curve_nistp.h>
+#include <botan/curve_nistp.h>
 #include <botan/internal/mp_core.h>
+#include <botan/internal/mp_asmi.h>
 
 namespace Botan {
 
-void CurveGFp_NIST::curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
-                              secure_vector<word>& ws) const
-   {
-   if(x.is_zero() || y.is_zero())
-      {
-      z = 0;
-      return;
-      }
+namespace {
 
-   const size_t p_words = get_p_words();
-   const size_t output_size = 2*p_words + 1;
-   ws.resize(2*(p_words+2));
+void normalize(const BigInt& p, BigInt& x, secure_vector<word>& ws, size_t bound)
+   {
+   const word* prime = p.data();
+   const size_t p_words = p.sig_words();
 
-   z.grow_to(output_size);
-   z.clear();
+   while(x.is_negative())
+      x += p;
 
-   bigint_mul(z.mutable_data(), output_size, ws.data(),
-              x.data(), x.size(), x.sig_words(),
-              y.data(), y.size(), y.sig_words());
+   // TODO: provide a high level function for this compare-and-sub operation
+   x.grow_to(p_words + 1);
 
-   this->redc(z, ws);
-   }
+   if(ws.size() < p_words + 1)
+      ws.resize(p_words + 1);
 
-void CurveGFp_NIST::curve_sqr(BigInt& z, const BigInt& x,
-                              secure_vector<word>& ws) const
-   {
-   if(x.is_zero())
+   for(size_t i = 0; bound == 0 || i < bound; ++i)
       {
-      z = 0;
-      return;
-      }
-
-   const size_t p_words = get_p_words();
-   const size_t output_size = 2*p_words + 1;
-
-   ws.resize(2*(p_words+2));
+      const word* xd = x.data();
+      word borrow = 0;
 
-   z.grow_to(output_size);
-   z.clear();
+      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);
 
-   bigint_sqr(z.mutable_data(), output_size, ws.data(),
-              x.data(), x.size(), x.sig_words());
+      if(borrow)
+         break;
 
-   this->redc(z, ws);
+      x.swap_reg(ws);
+      }
    }
 
-//static
-const BigInt& CurveGFp_P521::prime()
+}
+
+const BigInt& prime_p521()
    {
    static const BigInt p521("0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
                                "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
@@ -65,12 +53,11 @@ const BigInt& CurveGFp_P521::prime()
    return p521;
    }
 
-void CurveGFp_P521::redc(BigInt& x, secure_vector<word>& ws) const
+void redc_p521(BigInt& x, secure_vector<word>& ws)
    {
-   const size_t p_words = get_p_words();
-
-   const size_t shift_words = 521 / MP_WORD_BITS,
-                shift_bits  = 521 % MP_WORD_BITS;
+   const size_t p_full_words = 521 / MP_WORD_BITS;
+   const size_t p_top_bits = 521 % MP_WORD_BITS;
+   const size_t p_words = p_full_words + 1;
 
    const size_t x_sw = x.sig_words();
 
@@ -81,16 +68,16 @@ void CurveGFp_P521::redc(BigInt& x, secure_vector<word>& ws) const
       ws.resize(p_words + 1);
 
    clear_mem(ws.data(), ws.size());
-   bigint_shr2(ws.data(), x.data(), x_sw, shift_words, shift_bits);
+   bigint_shr2(ws.data(), x.data(), x_sw, p_full_words, p_top_bits);
 
    x.mask_bits(521);
 
    bigint_add3(x.mutable_data(), x.data(), p_words, ws.data(), p_words);
 
-   normalize(x, ws, max_redc_subtractions());
+   normalize(prime_p521(), x, ws, 1);
    }
 
-#if defined(BOTAN_HAS_CURVEGFP_NISTP_M32)
+#if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32)
 
 namespace {
 
@@ -130,14 +117,13 @@ inline void set_u32bit(BigInt& x, size_t i, T v_in)
 
 }
 
-//static
-const BigInt& CurveGFp_P192::prime()
+const BigInt& prime_p192()
    {
    static const BigInt p192("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF");
    return p192;
    }
 
-void CurveGFp_P192::redc(BigInt& x, secure_vector<word>& ws) const
+void redc_p192(BigInt& x, secure_vector<word>& ws)
    {
    const u32bit X6 = get_u32bit(x, 6);
    const u32bit X7 = get_u32bit(x, 7);
@@ -192,17 +178,16 @@ void CurveGFp_P192::redc(BigInt& x, secure_vector<word>& ws) const
 
    // No underflow possible
 
-   normalize(x, ws, max_redc_subtractions());
+   normalize(prime_p192(), x, ws, 3);
    }
 
-//static
-const BigInt& CurveGFp_P224::prime()
+const BigInt& prime_p224()
    {
    static const BigInt p224("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001");
    return p224;
    }
 
-void CurveGFp_P224::redc(BigInt& x, secure_vector<word>& ws) const
+void redc_p224(BigInt& x, secure_vector<word>& ws)
    {
    const u32bit X7 = get_u32bit(x, 7);
    const u32bit X8 = get_u32bit(x, 8);
@@ -271,17 +256,16 @@ void CurveGFp_P224::redc(BigInt& x, secure_vector<word>& ws) const
 
    BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow");
 
-   normalize(x, ws, max_redc_subtractions());
+   normalize(prime_p224(), x, ws, 3);
    }
 
-//static
-const BigInt& CurveGFp_P256::prime()
+const BigInt& prime_p256()
    {
    static const BigInt p256("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF");
    return p256;
    }
 
-void CurveGFp_P256::redc(BigInt& x, secure_vector<word>& ws) const
+void redc_p256(BigInt& x, secure_vector<word>& ws)
    {
    const u32bit X8 = get_u32bit(x, 8);
    const u32bit X9 = get_u32bit(x, 9);
@@ -396,34 +380,35 @@ void CurveGFp_P256::redc(BigInt& x, secure_vector<word>& ws) const
 
    BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow");
 
+   #if 0
    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()
+         2*CurveGFp_P256::prime(),
+         3*CurveGFp_P256::prime(),
+         4*CurveGFp_P256::prime(),
+         5*CurveGFp_P256::prime(),
+         6*CurveGFp_P256::prime(),
+         7*CurveGFp_P256::prime(),
+         8*CurveGFp_P256::prime(),
+         9*CurveGFp_P256::prime(),
+         10*CurveGFp_P256::prime()
       };
       x -= P256_mults[S - 2];
       }
+   #endif
 
-   normalize(x, ws, max_redc_subtractions());
+   normalize(prime_p256(), x, ws, 10);
    }
 
-//static
-const BigInt& CurveGFp_P384::prime()
+const BigInt& prime_p384()
    {
    static const BigInt p384("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF");
    return p384;
    }
 
-void CurveGFp_P384::redc(BigInt& x, secure_vector<word>& ws) const
+void redc_p384(BigInt& x, secure_vector<word>& ws)
    {
    const u32bit X12 = get_u32bit(x, 12);
    const u32bit X13 = get_u32bit(x, 13);
@@ -569,20 +554,22 @@ void CurveGFp_P384::redc(BigInt& x, secure_vector<word>& ws) const
    BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow");
    set_u32bit(x, 12, S);
 
+   #if 0
    if(S >= 2)
       {
       BOTAN_ASSERT(S <= 4, "Expected overflow");
 
       static const BigInt P384_mults[3] = {
-         2*get_p(),
-         3*get_p(),
-         4*get_p()
+         2*CurveGFp_P384::prime(),
+         3*CurveGFp_P384::prime(),
+         4*CurveGFp_P384::prime()
       };
 
       x -= P384_mults[S - 2];
       }
+   #endif
 
-   normalize(x, ws, max_redc_subtractions());
+   normalize(prime_p384(), x, ws, 4);
    }
 
 #endif
diff --git a/src/lib/math/ec_gfp/curve_nistp.h b/src/lib/math/ec_gfp/curve_nistp.h
index 0bf707f58..e7af69964 100644
--- a/src/lib/math/ec_gfp/curve_nistp.h
+++ b/src/lib/math/ec_gfp/curve_nistp.h
@@ -1,152 +1,46 @@
 /*
-* NIST elliptic curves over GF(p)
-* (C) 2014 Jack Lloyd
+* Arithmetic operations specialized for NIST ECC primes
+* (C) 2014,2015 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
-#ifndef BOTAN_GFP_CURVE_NIST_H__
-#define BOTAN_GFP_CURVE_NIST_H__
+#ifndef BOTAN_NIST_PRIMES_H__
+#define BOTAN_NIST_PRIMES_H__
 
-#include <botan/curve_gfp.h>
-#include <memory>
+#include <botan/bigint.h>
 
 namespace Botan {
 
-class CurveGFp_NIST : public CurveGFp_Repr
-   {
-   public:
-      CurveGFp_NIST(size_t p_bits, const BigInt& a, const BigInt& b) :
-         m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS)
-         {
-         }
-
-      size_t get_p_words() const override { return m_p_words; }
-
-      const BigInt& get_a() const override { return m_a; }
-
-      const BigInt& get_b() const override { return m_b; }
-
-      const BigInt& get_a_rep() const override { return m_a; }
-
-      const BigInt& get_b_rep() const override { return m_b; }
-
-      void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override
-         { redc(x, ws); }
-
-      void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override
-         { redc(x, ws); }
-
-      void curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
-                     secure_vector<word>& ws) const override;
-
-      void curve_sqr(BigInt& z, const BigInt& x,
-                     secure_vector<word>& ws) const override;
-   private:
-      virtual void redc(BigInt& x, secure_vector<word>& ws) const = 0;
-
-      virtual size_t max_redc_subtractions() const = 0;
-
-      // Curve parameters
-      BigInt m_a, m_b;
-      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
+* NIST Prime reduction functions.
+*
+* Reduces the value in place
+*
+* ws is a workspace function which is used as a temporary,
+* and will be resized as needed.
 */
-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;
+BOTAN_DLL const BigInt& prime_p521();
+BOTAN_DLL void redc_p521(BigInt& x, secure_vector<word>& ws);
 
-      size_t max_redc_subtractions() const override { return 10; }
-   };
+#if (BOTAN_MP_WORD_BITS == 32) || (BOTAN_MP_WORD_BITS == 64)
 
-/**
-* 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) {}
+#define BOTAN_HAS_NIST_PRIME_REDUCERS_W32
 
-      static const BigInt& prime();
+BOTAN_DLL const BigInt& prime_p384();
+BOTAN_DLL void redc_p384(BigInt& x, secure_vector<word>& ws);
 
-      const BigInt& get_p() const override { return CurveGFp_P384::prime(); }
+BOTAN_DLL const BigInt& prime_p256();
+BOTAN_DLL void redc_p256(BigInt& x, secure_vector<word>& ws);
 
-   private:
-      void redc(BigInt& x, secure_vector<word>& ws) const override;
+BOTAN_DLL const BigInt& prime_p224();
+BOTAN_DLL void redc_p224(BigInt& x, secure_vector<word>& ws);
 
-      size_t max_redc_subtractions() const override { return 4; }
-   };
+BOTAN_DLL const BigInt& prime_p192();
+BOTAN_DLL void redc_p192(BigInt& x, secure_vector<word>& ws);
 
 #endif
 
-/**
-* The NIST P-521 curve
-*/
-class CurveGFp_P521 : public CurveGFp_NIST
-   {
-   public:
-      CurveGFp_P521(const BigInt& a, const BigInt& b) : CurveGFp_NIST(521, a, b) {}
-
-      static const BigInt& prime();
-
-      const BigInt& get_p() const override { return CurveGFp_P521::prime(); }
-
-   private:
-      void redc(BigInt& x, secure_vector<word>& ws) const override;
-
-      size_t max_redc_subtractions() const override { return 1; }
-   };
-
 }
 
 #endif
diff --git a/src/lib/math/ec_gfp/info.txt b/src/lib/math/ec_gfp/info.txt
index 9af40c752..060551562 100644
--- a/src/lib/math/ec_gfp/info.txt
+++ b/src/lib/math/ec_gfp/info.txt
@@ -2,15 +2,6 @@ define EC_CURVE_GFP 20131128
 
 load_on auto
 
-<header:public>
-curve_gfp.h
-point_gfp.h
-</header:public>
-
-<header:internal>
-curve_nistp.h
-</header:internal>
-
 <requires>
 numbertheory
 </requires>
diff --git a/src/lib/math/numbertheory/info.txt b/src/lib/math/numbertheory/info.txt
index e39a236cb..49f7ab2fb 100644
--- a/src/lib/math/numbertheory/info.txt
+++ b/src/lib/math/numbertheory/info.txt
@@ -12,20 +12,6 @@ reducer.h
 def_powm.h
 </header:internal>
 
-<source>
-dsa_gen.cpp
-jacobi.cpp
-make_prm.cpp
-mp_numth.cpp
-numthry.cpp
-pow_mod.cpp
-powm_fw.cpp
-powm_mnt.cpp
-primes.cpp
-reducer.cpp
-ressol.cpp
-</source>
-
 <requires>
 bigint
 hash
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index 748f26ce9..dabe5746e 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -21,27 +21,43 @@
 #include <botan/bigint.h>
 #include <botan/exceptn.h>
 #include <botan/numthry.h>
+#include <botan/reducer.h>
+
+#if defined(BOTAN_HAS_EC_CURVE_GFP)
+#include <botan/curve_nistp.h>
+#endif
 
 using namespace Botan;
 
 namespace {
 
-void test_failure(const char* function, const char* file, int line,
-                  const std::string& what_failed)
+class Test_State
    {
-   std::cout << "FAIL " << function << " " << file << ":" << line << " "
-             << what_failed << std::endl;
-   }
+   public:
+      void started(const std::string& /*msg*/) { m_tests_run++; }
+
+      void test_ran(const char* msg);
+
+      void failure(const char* test, const std::string& what_failed)
+         {
+         std::cout << "FAIL " << test << " " << what_failed << "\n";
+         m_tests_failed++;
+         }
+
+      size_t ran() const { return m_tests_run; }
+      size_t failed() const { return m_tests_failed; }
+   private:
+      size_t m_tests_run = 0, m_tests_failed = 0;
+   };
 
 #define BOTAN_CONFIRM_NOTHROW(block) do {                              \
    try { block }                                                        \
    catch(std::exception& e) {                                           \
-      test_failure(BOTAN_CURRENT_FUNCTION, __FILE__, __LINE__, e.what());   \
-      ++tests_failed;                                                   \
+      _test.failure(BOTAN_CURRENT_FUNCTION, e.what());  \
    } } while(0)                                                         \
 
 #define BOTAN_TEST(lhs, rhs, msg) do {                                     \
-   ++tests_run;                                                            \
+   _test.started(msg);                                                  \
    BOTAN_CONFIRM_NOTHROW({                                              \
       const auto lhs_val = lhs;                                         \
       const auto rhs_val = rhs;                                         \
@@ -52,19 +68,19 @@ void test_failure(const char* function, const char* file, int line,
          fmt << "expr '" << #lhs << " == " << #rhs << "' false, "       \
              << "actually " << lhs_val << " " << rhs_val                \
              << " (" << msg << ")";                                     \
-         test_failure(BOTAN_CURRENT_FUNCTION, __FILE__, __LINE__, fmt.str()); \
-         ++tests_failed;                                                \
+         _test.failure(BOTAN_CURRENT_FUNCTION, fmt.str()); \
          }                                                              \
       });                                                               \
    } while(0)
 
-#define BOTAN_TEST_CASE(name, block) size_t test_ ## name() {              \
-   size_t tests_run = 0, tests_failed = 0;                                 \
+#define BOTAN_TEST_CASE(name, descr, block) size_t test_ ## name() {     \
+   Test_State _test;                                                    \
    BOTAN_CONFIRM_NOTHROW(block);                                           \
-   return tests_failed;                                                    \
+   test_report(descr, _test.ran(), _test.failed());                     \
+   return _test.failed();                                   \
    }
 
-BOTAN_TEST_CASE(bigint_to_u32bit, {
+BOTAN_TEST_CASE(bigint_to_u32bit, "BigInt to_u32bit", {
    for(size_t i = 0; i != 32; ++i)
       {
       const u32bit in = 1 << i;
@@ -72,6 +88,100 @@ BOTAN_TEST_CASE(bigint_to_u32bit, {
       }
    });
 
+BigInt test_integer(RandomNumberGenerator& rng, size_t bits)
+   {
+   /*
+   Produces integers with long runs of ones and zeros, for testing for
+   carry handling problems.
+   */
+   BigInt x = 0;
+
+   auto flip_prob = [](size_t i) {
+      if(i % 64 == 0)
+         return .5;
+      if(i % 32 == 0)
+         return .4;
+      if(i % 8 == 0)
+         return .05;
+      return .01;
+   };
+
+   bool active = rng.next_byte() % 2;
+   for(size_t i = 0; i != bits; ++i)
+      {
+      x <<= 1;
+      x += static_cast<int>(active);
+
+      const double prob = flip_prob(i);
+      const double sample = double(rng.next_byte() % 100) / 100.0; // biased
+
+      if(sample < prob)
+         active = !active;
+      }
+
+   //std::cout << std::hex << x << "\n";
+   return x;
+   }
+
+#if defined(BOTAN_HAS_EC_CURVE_GFP)
+
+void nist_redc_test(Test_State& _test,
+                    const std::string& prime_name,
+                    const BigInt& p,
+                    std::function<void (BigInt&, secure_vector<word>&)> redc_fn)
+   {
+   auto& rng = test_rng();
+   const size_t trials = 100;
+   const size_t p_bits = p.bits();
+
+   Modular_Reducer p_redc(p);
+   secure_vector<word> ws;
+
+   for(size_t i = 0; i != trials; ++i)
+      {
+      const BigInt x = test_integer(rng, 2*p_bits);
+
+      // TODO: time and report all three approaches
+      const BigInt v1 = x % p;
+      const BigInt v2 = p_redc.reduce(x);
+
+      BigInt v3 = x;
+      redc_fn(v3, ws);
+
+      BOTAN_TEST(v1, v2, "reference");
+      BOTAN_TEST(v2, v3, "specialized");
+
+      if(v1 != v2 || v2 != v3)
+         std::cout << "Prime " << prime_name << " input " << x << "\n";
+      }
+   }
+
+#if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32)
+
+BOTAN_TEST_CASE(bigint_redc_p192, "P-192 reduction", {
+   nist_redc_test(_test, "P-192", prime_p192(), redc_p192);
+   });
+
+BOTAN_TEST_CASE(bigint_redc_p224, "P-224 reduction", {
+   nist_redc_test(_test, "P-224", prime_p224(), redc_p224);
+   });
+
+BOTAN_TEST_CASE(bigint_redc_p256, "P-256 reduction", {
+   nist_redc_test(_test, "P-256", prime_p256(), redc_p256);
+   });
+
+BOTAN_TEST_CASE(bigint_redc_p384, "P-384 reduction", {
+   nist_redc_test(_test, "P-384", prime_p384(), redc_p384);
+   });
+
+#endif
+
+BOTAN_TEST_CASE(bigint_redc_p521, "P-521 reduction", {
+   nist_redc_test(_test, "P-521", prime_p521(), redc_p521);
+   });
+
+#endif
+
 void strip_comments(std::string& line)
    {
    if(line.find('#') != std::string::npos)
@@ -349,8 +459,6 @@ size_t test_bigint()
    bool first = true;
    size_t counter = 0;
 
-   total_errors += test_bigint_to_u32bit();
-
    auto& rng = test_rng();
 
    while(!test_data.eof())
@@ -429,6 +537,20 @@ size_t test_bigint()
                    << std::dec << alg_count << std::endl;
       }
 
+   total_errors += test_bigint_to_u32bit();
+
+#if defined(BOTAN_HAS_EC_CURVE_GFP)
+
+#if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32)
+   total_errors += test_bigint_redc_p192();
+   total_errors += test_bigint_redc_p224();
+   total_errors += test_bigint_redc_p256();
+   total_errors += test_bigint_redc_p384();
+ #endif
+
+   total_errors += test_bigint_redc_p521();
+#endif
+
    return total_errors;
    }