Cache p.sig_words() in curve object

Avoid using Barett reduction in core operations; seems to help perf.

3 files changed, 68 insertions, 27 deletions

diff --git a/src/math/numbertheory/curve_gfp.h b/src/math/numbertheory/curve_gfp.h
index a7be8987c..0a91fc52d 100644
--- a/src/math/numbertheory/curve_gfp.h
+++ b/src/math/numbertheory/curve_gfp.h
@@ -44,6 +44,8 @@ class BOTAN_DLL CurveGFp
          p_dash = (((r * r_inv) - 1) / p).word_at(0);
 
          a_r = reducer_p.multiply(a, r);
+
+         p_words = p.sig_words();
          }
 
       // CurveGFp(const CurveGFp& other) = default;
@@ -87,6 +89,11 @@ class BOTAN_DLL CurveGFp
       */
       word get_p_dash() const { return p_dash; }
 
+      /**
+      * @return p.sig_words()
+      */
+      u32bit get_p_words() const { return p_words; }
+
       const Modular_Reducer& mod_p() const { return reducer_p; }
 
       /**
@@ -114,6 +121,8 @@ class BOTAN_DLL CurveGFp
       // Curve parameters
       BigInt p, a, b;
 
+      u32bit p_words; // cache of p.sig_words()
+
       // Montgomery parameters
       BigInt r, r_inv, a_r;
       word p_dash;
diff --git a/src/math/numbertheory/point_gfp.cpp b/src/math/numbertheory/point_gfp.cpp
index 2e4f99796..0148d9b3e 100644
--- a/src/math/numbertheory/point_gfp.cpp
+++ b/src/math/numbertheory/point_gfp.cpp
@@ -32,14 +32,13 @@ PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) :
    }
 
 BigInt PointGFp::monty_mult(const BigInt& a, const BigInt& b,
-                            MemoryRegion<word>& workspace)
+                            MemoryRegion<word>& workspace) const
    {
    if(a.is_zero() || b.is_zero())
       return 0;
 
    const BigInt& p = curve.get_p();
-   const u32bit p_size = p.sig_words();
-
+   const u32bit p_size = curve.get_p_words();
    const word p_dash = curve.get_p_dash();
 
    workspace.clear();
@@ -59,14 +58,13 @@ BigInt PointGFp::monty_mult(const BigInt& a, const BigInt& b,
    }
 
 BigInt PointGFp::monty_sqr(const BigInt& x,
-                           MemoryRegion<word>& workspace)
+                           MemoryRegion<word>& workspace) const
    {
    if(x.is_zero())
       return 0;
 
    const BigInt& p = curve.get_p();
-   const u32bit p_size = p.sig_words();
-
+   const u32bit p_size = curve.get_p_words();
    const word p_dash = curve.get_p_dash();
 
    workspace.clear();
@@ -97,11 +95,11 @@ void PointGFp::add(const PointGFp& rhs,
    else if(rhs.is_zero())
       return;
 
+   const BigInt& p = curve.get_p();
+
    MemoryRegion<word>& ws = workspace.ws_monty;
    std::vector<BigInt>& ws_bn = workspace.ws_bn;
 
-   const Modular_Reducer& mod_p = curve.mod_p();
-
    BigInt& rhs_z2 = ws_bn[0];
    BigInt& U1 = ws_bn[1];
    BigInt& S1 = ws_bn[2];
@@ -125,9 +123,13 @@ void PointGFp::add(const PointGFp& rhs,
    U2 = monty_mult(rhs.coord_x, lhs_z2, ws);
    S2 = monty_mult(rhs.coord_y, monty_mult(coord_z, lhs_z2, ws), ws);
 
-   H = mod_p.reduce(U2 - U1);
+   H = U2 - U1;
+   if(H.is_negative())
+      H += p;
 
-   r = mod_p.reduce(S2 - S1);
+   r = S2 - S1;
+   if(r.is_negative())
+      r += p;
 
    if(H.is_zero())
       {
@@ -147,15 +149,17 @@ void PointGFp::add(const PointGFp& rhs,
 
    U2 = monty_mult(U1, U2, ws);
 
-   x = mod_p.reduce(monty_sqr(r, ws) - S2 - U2*2);
+   x = monty_sqr(r, ws) - S2 - U2*2;
+   while(x.is_negative())
+      x += p;
 
    U2 -= x;
    if(U2.is_negative())
-      U2 += curve.get_p();
+      U2 += p;
 
    y = monty_mult(r, U2, ws) - monty_mult(S1, S2, ws);
    if(y.is_negative())
-      y += curve.get_p();
+      y += p;
 
    z = monty_mult(monty_mult(coord_z, rhs.coord_z, ws), H, ws);
 
@@ -167,7 +171,7 @@ void PointGFp::add(const PointGFp& rhs,
 // arithmetic operators
 PointGFp& PointGFp::operator+=(const PointGFp& rhs)
    {
-   Workspace ws(curve.get_p().sig_words());
+   Workspace ws(curve.get_p_words());
    add(rhs, ws);
    return *this;
    }
@@ -186,7 +190,7 @@ PointGFp& PointGFp::operator-=(const PointGFp& rhs)
 
 PointGFp& PointGFp::operator*=(const BigInt& scalar)
    {
-   Workspace ws(curve.get_p().sig_words());
+   Workspace ws(curve.get_p_words());
 
    if(scalar.abs() <= 2) // special cases for small values
       {
@@ -257,11 +261,11 @@ void PointGFp::mult2(Workspace& workspace)
       return;
       }
 
+   const BigInt& p = curve.get_p();
+
    MemoryRegion<word>& ws = workspace.ws_monty;
    std::vector<BigInt>& ws_bn = workspace.ws_bn;
 
-   const Modular_Reducer& mod_p = curve.mod_p();
-
    BigInt& y_2 = ws_bn[0];
    BigInt& S = ws_bn[1];
    BigInt& z4 = ws_bn[2];
@@ -274,29 +278,37 @@ void PointGFp::mult2(Workspace& workspace)
 
    y_2 = monty_sqr(coord_y, ws);
 
-   S = mod_p.reduce(4 * monty_mult(coord_x, y_2, ws));
+   S = 4 * monty_mult(coord_x, y_2, ws);
+   while(S >= p)
+      S -= p;
 
    z4 = monty_sqr(monty_sqr(coord_z, ws), ws);
 
    a_z4 = monty_mult(curve.get_a_r(), z4, ws);
 
-   M = mod_p.reduce(a_z4 + 3 * monty_sqr(coord_x, ws));
+   M = 3 * monty_sqr(coord_x, ws) + a_z4;
+   while(M >= p)
+      M -= p;
 
-   x = mod_p.reduce(monty_sqr(M, ws) - 2*S);
+   x = monty_sqr(M, ws) - 2*S;
+   while(x.is_negative())
+      x += p;
 
-   U = mod_p.reduce(monty_sqr(y_2, ws) << 3);
+   U = 8 * monty_sqr(y_2, ws);
+   while(U >= p)
+      U -= p;
 
    S -= x;
    while(S.is_negative())
-      S += curve.get_p();
+      S += p;
 
    y = monty_mult(M, S, ws) - U;
    if(y.is_negative())
-      y += curve.get_p();
+      y += p;
 
    z = 2 * monty_mult(coord_y, coord_z, ws);
-   if(z >= curve.get_p())
-      z -= curve.get_p();
+   if(z >= p)
+      z -= p;
 
    coord_x = x;
    coord_y = y;
@@ -310,11 +322,21 @@ BigInt PointGFp::get_affine_x() const
 
    const Modular_Reducer& mod_p = curve.mod_p();
 
+#if 1
    BigInt x = mod_p.multiply(curve.get_r_inv(), coord_x);
    BigInt z = mod_p.multiply(curve.get_r_inv(), coord_z);
 
    BigInt z2 = mod_p.square(z);
    return mod_p.multiply(x, inverse_mod(z2, curve.get_p()));
+#else
+
+   SecureVector<word> ws(2 * (curve.get_p_words() + 2));
+
+   BigInt z2 = monty_sqr(coord_z, ws);
+   z2 = inverse_mod(z2, curve.get_p());
+   z2 = mod_p.multiply(z2, curve.get_r());
+   return monty_mult(coord_x, z2, ws);
+#endif
    }
 
 BigInt PointGFp::get_affine_y() const
@@ -324,11 +346,21 @@ BigInt PointGFp::get_affine_y() const
 
    const Modular_Reducer& mod_p = curve.mod_p();
 
+#if 1
    BigInt y = mod_p.multiply(curve.get_r_inv(), coord_y);
    BigInt z = mod_p.multiply(curve.get_r_inv(), coord_z);
 
    BigInt z3 = mod_p.cube(z);
    return mod_p.multiply(y, inverse_mod(z3, curve.get_p()));
+#else
+
+   SecureVector<word> ws(2 * (curve.get_p_words() + 2));
+
+   BigInt z3 = monty_mult(coord_z, monty_sqr(coord_z, ws), ws);
+   z3 = inverse_mod(z3, curve.get_p());
+   z3 = mod_p.multiply(z3, curve.get_r());
+   return monty_mult(coord_y, z3, ws);
+#endif
    }
 
 void PointGFp::check_invariants() const
diff --git a/src/math/numbertheory/point_gfp.h b/src/math/numbertheory/point_gfp.h
index c7da6995c..f5cb11157 100644
--- a/src/math/numbertheory/point_gfp.h
+++ b/src/math/numbertheory/point_gfp.h
@@ -158,7 +158,7 @@ class BOTAN_DLL PointGFp
       * @param workspace temp space
       */
       BigInt monty_mult(const BigInt& x, const BigInt& y,
-                        MemoryRegion<word>& workspace);
+                        MemoryRegion<word>& workspace) const;
 
       /**
       * Montgomery squaring/reduction
@@ -166,7 +166,7 @@ class BOTAN_DLL PointGFp
       * @param workspace temp space
       */
       BigInt monty_sqr(const BigInt& x,
-                       MemoryRegion<word>& workspace);
+                       MemoryRegion<word>& workspace) const;
 
       /**
       * Point addition