Merge GH #1538 Minor ECC optimizations

7 files changed, 105 insertions, 21 deletions

diff --git a/src/lib/pubkey/ec_group/curve_gfp.cpp b/src/lib/pubkey/ec_group/curve_gfp.cpp
index 9f614ac61..e76636589 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.cpp
+++ b/src/lib/pubkey/ec_group/curve_gfp.cpp
@@ -52,6 +52,8 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr
 
       const BigInt& get_b_rep() const override { return m_b_r; }
 
+      const BigInt& get_1_rep() const override { return m_r; }
+
       bool is_one(const BigInt& x) const override { return x == m_r; }
 
       size_t get_p_words() const override { return m_p_words; }
@@ -197,7 +199,7 @@ 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)
+         m_1(1), m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS)
          {
          // All Solinas prime curves are assumed a == -3
          }
@@ -209,6 +211,8 @@ class CurveGFp_NIST : public CurveGFp_Repr
 
       const BigInt& get_b() const override { return m_b; }
 
+      const BigInt& get_1_rep() const override { return m_1; }
+
       size_t get_p_words() const override { return m_p_words; }
 
       size_t get_ws_size() const override { return 2*m_p_words + 4; }
@@ -242,6 +246,7 @@ class CurveGFp_NIST : public CurveGFp_Repr
       virtual void redc(BigInt& x, secure_vector<word>& ws) const = 0;
 
       // Curve parameters
+      BigInt m_1;
       BigInt m_a, m_b;
       size_t m_p_words; // cache of m_p.sig_words()
    };
diff --git a/src/lib/pubkey/ec_group/curve_gfp.h b/src/lib/pubkey/ec_group/curve_gfp.h
index 3a17c6678..865bb68f8 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.h
+++ b/src/lib/pubkey/ec_group/curve_gfp.h
@@ -44,6 +44,11 @@ class BOTAN_UNSTABLE_API CurveGFp_Repr
       */
       virtual const BigInt& get_b_rep() const = 0;
 
+      /*
+      * Returns to_curve_rep(1)
+      */
+      virtual const BigInt& get_1_rep() const = 0;
+
       virtual BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const = 0;
 
       virtual void to_curve_rep(BigInt& x, secure_vector<word>& ws) const = 0;
@@ -120,6 +125,8 @@ class BOTAN_UNSTABLE_API CurveGFp final
 
       const BigInt& get_b_rep() const { return m_repr->get_b_rep(); }
 
+      const BigInt& get_1_rep() const { return m_repr->get_1_rep(); }
+
       bool a_is_minus_3() const { return m_repr->a_is_minus_3(); }
       bool a_is_zero() const { return m_repr->a_is_zero(); }
 
diff --git a/src/lib/pubkey/ec_group/ec_group.cpp b/src/lib/pubkey/ec_group/ec_group.cpp
index d5a94c90c..fc512b733 100644
--- a/src/lib/pubkey/ec_group/ec_group.cpp
+++ b/src/lib/pubkey/ec_group/ec_group.cpp
@@ -528,7 +528,7 @@ PointGFp EC_Group::blinded_var_point_multiply(const PointGFp& point,
                                               std::vector<BigInt>& ws) const
    {
    PointGFp_Var_Point_Precompute mul(point);
-   mul.randomize_repr(rng);
+   mul.randomize_repr(rng, ws);
    return mul.mul(k, rng, get_order(), ws);
    }
 
diff --git a/src/lib/pubkey/ec_group/point_gfp.cpp b/src/lib/pubkey/ec_group/point_gfp.cpp
index 860459252..c65b4ac16 100644
--- a/src/lib/pubkey/ec_group/point_gfp.cpp
+++ b/src/lib/pubkey/ec_group/point_gfp.cpp
@@ -111,8 +111,7 @@ void PointGFp::add_affine(const word x_words[], size_t x_size,
       // FIXME avoid the copy here
       m_coord_x = BigInt(x_words, x_size);
       m_coord_y = BigInt(y_words, y_size);
-      m_coord_z = 1;
-      m_curve.to_rep(m_coord_z, ws_bn[0].get_word_vector());
+      m_coord_z = m_curve.get_1_rep();
       return;
       }
 
@@ -284,6 +283,25 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
    m_curve.mul(m_coord_z, T0, T4, ws);
    }
 
+void PointGFp::mult2i(size_t iterations, std::vector<BigInt>& ws_bn)
+   {
+   if(iterations == 0)
+      return;
+
+   if(m_coord_y.is_zero())
+      {
+      *this = PointGFp(m_curve); // setting myself to zero
+      return;
+      }
+
+   /*
+   TODO we can save 2 squarings per iteration by computing
+   a*Z^4 using values cached from previous iteration
+   */
+   for(size_t i = 0; i != iterations; ++i)
+      mult2(ws_bn);
+   }
+
 // *this *= 2
 void PointGFp::mult2(std::vector<BigInt>& ws_bn)
    {
@@ -301,7 +319,7 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
    secure_vector<word>& ws = ws_bn[0].get_word_vector();
    BigInt& T0 = ws_bn[1];
    BigInt& T1 = ws_bn[2];
-   BigInt& T2 = ws_bn[6];
+   BigInt& T2 = ws_bn[3];
    BigInt& T3 = ws_bn[4];
    BigInt& T4 = ws_bn[5];
 
@@ -459,13 +477,11 @@ void PointGFp::force_all_affine(std::vector<PointGFp>& points,
    */
 
    const CurveGFp& curve = points[0].m_curve;
+   const BigInt& rep_1 = curve.get_1_rep();
 
    if(ws.size() < curve.get_ws_size())
       ws.resize(curve.get_ws_size());
 
-   BigInt rep_1 = 1;
-   curve.to_rep(rep_1, ws);
-
    std::vector<BigInt> c(points.size());
    c[0] = points[0].m_coord_z;
 
@@ -512,8 +528,7 @@ void PointGFp::force_affine()
    const BigInt z3_inv = m_curve.mul_to_tmp(z_inv, z2_inv, ws);
    m_coord_x = m_curve.mul_to_tmp(m_coord_x, z2_inv, ws);
    m_coord_y = m_curve.mul_to_tmp(m_coord_y, z3_inv, ws);
-   m_coord_z = 1;
-   m_curve.to_rep(m_coord_z, ws);
+   m_coord_z = m_curve.get_1_rep();
    }
 
 bool PointGFp::is_affine() const
diff --git a/src/lib/pubkey/ec_group/point_gfp.h b/src/lib/pubkey/ec_group/point_gfp.h
index 2a9948fde..271d7383a 100644
--- a/src/lib/pubkey/ec_group/point_gfp.h
+++ b/src/lib/pubkey/ec_group/point_gfp.h
@@ -152,6 +152,13 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final
       const BigInt& get_y() const { return m_coord_y; }
       const BigInt& get_z() const { return m_coord_z; }
 
+      void swap_coords(BigInt& new_x, BigInt& new_y, BigInt& new_z)
+         {
+         m_coord_x.swap(new_x);
+         m_coord_y.swap(new_y);
+         m_coord_z.swap(new_z);
+         }
+
       /**
       * Force this point to affine coordinates
       */
@@ -236,6 +243,13 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final
       void mult2(std::vector<BigInt>& workspace);
 
       /**
+      * Repeated point doubling
+      * @param i number of doublings to perform
+      * @param workspace temp space, at least WORKSPACE_SIZE elements
+      */
+      void mult2i(size_t i, std::vector<BigInt>& workspace);
+
+      /**
       * Point addition
       * @param other the point to add to *this
       * @param workspace temp space, at least WORKSPACE_SIZE elements
@@ -249,6 +263,18 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final
          }
 
       /**
+      * Point doubling
+      * @param workspace temp space, at least WORKSPACE_SIZE elements
+      * @return *this doubled
+      */
+      PointGFp double_of(std::vector<BigInt>& workspace) const
+         {
+         PointGFp x = (*this);
+         x.mult2(workspace);
+         return x;
+         }
+
+      /**
       * Return the zero (aka infinite) point associated with this curve
       */
       PointGFp zero() const { return PointGFp(m_curve); }
diff --git a/src/lib/pubkey/ec_group/point_mul.cpp b/src/lib/pubkey/ec_group/point_mul.cpp
index d052b837c..17087a6ed 100644
--- a/src/lib/pubkey/ec_group/point_mul.cpp
+++ b/src/lib/pubkey/ec_group/point_mul.cpp
@@ -140,22 +140,54 @@ PointGFp_Var_Point_Precompute::PointGFp_Var_Point_Precompute(const PointGFp& poi
    {
    m_window_bits = 4;
 
+   std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
+
    m_U.resize(1U << m_window_bits);
    m_U[0] = point.zero();
    m_U[1] = point;
 
-   std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
-   for(size_t i = 2; i < m_U.size(); ++i)
+   for(size_t i = 2; i < m_U.size(); i += 2)
       {
-      m_U[i] = m_U[i-1];
-      m_U[i].add(point, ws);
+      m_U[i] = m_U[i/2].double_of(ws);
+      m_U[i+1] = m_U[i].plus(point, ws);
       }
    }
 
-void PointGFp_Var_Point_Precompute::randomize_repr(RandomNumberGenerator& rng)
+void PointGFp_Var_Point_Precompute::randomize_repr(RandomNumberGenerator& rng,
+                                                   std::vector<BigInt>& ws_bn)
    {
+   if(BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS <= 1)
+      return;
+
+   if(ws_bn.size() < 7)
+      ws_bn.resize(7);
+
+   BigInt& mask = ws_bn[0];
+   BigInt& mask2 = ws_bn[1];
+   BigInt& mask3 = ws_bn[2];
+   BigInt& new_x = ws_bn[3];
+   BigInt& new_y = ws_bn[4];
+   BigInt& new_z = ws_bn[5];
+   secure_vector<word>& ws = ws_bn[6].get_word_vector();
+
+   const CurveGFp& curve = m_U[0].get_curve();
+
+   // Skipping zero point since it can't be randomized
    for(size_t i = 1; i != m_U.size(); ++i)
-      m_U[i].randomize_repr(rng);
+      {
+      mask.randomize(rng, BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS, false);
+      // Easy way of ensuring mask != 0
+      mask.set_bit(0);
+
+      curve.sqr(mask2, mask, ws);
+      curve.mul(mask3, mask, mask2, ws);
+
+      curve.mul(new_x, m_U[i].get_x(), mask2, ws);
+      curve.mul(new_y, m_U[i].get_y(), mask3, ws);
+      curve.mul(new_z, m_U[i].get_z(), mask, ws);
+
+      m_U[i].swap_coords(new_x, new_y, new_z);
+      }
    }
 
 PointGFp PointGFp_Var_Point_Precompute::mul(const BigInt& k,
@@ -193,8 +225,7 @@ PointGFp PointGFp_Var_Point_Precompute::mul(const BigInt& k,
 
       while(windows)
          {
-         for(size_t i = 0; i != m_window_bits; ++i)
-            R.mult2(ws);
+         R.mult2i(m_window_bits, ws);
 
          const uint32_t inner_nibble = scalar.get_substring((windows-1)*m_window_bits, m_window_bits);
          // cache side channel here, we are relying on blinding...
@@ -261,8 +292,7 @@ PointGFp PointGFp_Multi_Point_Precompute::multi_exp(const BigInt& z1,
       {
       if(i > 0)
          {
-         H.mult2(ws);
-         H.mult2(ws);
+         H.mult2i(2, ws);
          }
 
       const uint8_t z1_b = z1.get_substring(z_bits - i - 2, 2);
diff --git a/src/lib/pubkey/ec_group/point_mul.h b/src/lib/pubkey/ec_group/point_mul.h
index cfce05d5c..da1d3b744 100644
--- a/src/lib/pubkey/ec_group/point_mul.h
+++ b/src/lib/pubkey/ec_group/point_mul.h
@@ -43,7 +43,8 @@ class PointGFp_Var_Point_Precompute
    public:
       PointGFp_Var_Point_Precompute(const PointGFp& point);
 
-      void randomize_repr(RandomNumberGenerator& rng);
+      void randomize_repr(RandomNumberGenerator& rng,
+                          std::vector<BigInt>& ws);
 
       PointGFp mul(const BigInt& k,
                    RandomNumberGenerator& rng,