Store base point multiplies in a single std::vector

Since the point is public all the values are also, so this reduces
pressure on the mlock allocator and may (slightly) help perf through
cache read-ahead.

Downside is cache based side channels are slightly easier (vs the
data being stored in discontigious vectors). But we shouldn't rely
on that in any case. And having it be in an array makes a masked
table lookup easier to arrange.

8 files changed, 175 insertions, 30 deletions

diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index a722e0e4b..a42707e07 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -118,6 +118,17 @@ int32_t BigInt::cmp(const BigInt& other, bool check_signs) const
                      other.data(), other.sig_words());
    }
 
+void BigInt::encode_words(word out[], size_t size) const
+   {
+   const size_t words = sig_words();
+
+   if(words > size)
+      throw Encoding_Error("BigInt::encode_words value too large to encode");
+
+   clear_mem(out, size);
+   copy_mem(out, data(), words);
+   }
+
 /*
 * Return bits {offset...offset+length}
 */
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index ba17d7ede..3f0eb8523 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -537,6 +537,12 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      size_t encoded_size(Base base = Binary) const;
 
      /**
+     * Place the value into out, zero-padding up to size words
+     * Throw if *this cannot be represented in size words
+     */
+     void encode_words(word out[], size_t size) const;
+
+     /**
      * @param rng a random number generator
      * @param min the minimum value
      * @param max the maximum value
diff --git a/src/lib/pubkey/ec_group/curve_gfp.cpp b/src/lib/pubkey/ec_group/curve_gfp.cpp
index a8fdb2906..8953edba4 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.cpp
+++ b/src/lib/pubkey/ec_group/curve_gfp.cpp
@@ -1,6 +1,6 @@
 /*
 * Elliptic curves over GF(p) Montgomery Representation
-* (C) 2014,2015 Jack Lloyd
+* (C) 2014,2015,2018 Jack Lloyd
 *     2016 Matthias Gierlings
 *
 * Botan is released under the Simplified BSD License (see license.txt)
@@ -61,6 +61,12 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr
       void curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
                      secure_vector<word>& ws) const override;
 
+      void curve_mul_words(BigInt& z,
+                           const word x_words[],
+                           const size_t x_size,
+                           const BigInt& y,
+                           secure_vector<word>& ws) const override;
+
       void curve_sqr(BigInt& z, const BigInt& x,
                      secure_vector<word>& ws) const override;
    private:
@@ -129,6 +135,34 @@ void CurveGFp_Montgomery::curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
                      ws.data(), ws.size());
    }
 
+void CurveGFp_Montgomery::curve_mul_words(BigInt& z,
+                                          const word x_w[],
+                                          size_t x_size,
+                                          const BigInt& y,
+                                          secure_vector<word>& ws) const
+   {
+   if(ws.size() < get_ws_size())
+      ws.resize(get_ws_size());
+
+   const size_t output_size = 2*m_p_words + 2;
+   if(z.size() < output_size)
+      z.grow_to(output_size);
+
+   BOTAN_DEBUG_ASSERT(y.sig_words() <= m_p_words);
+
+   const size_t x_words = (x_size >= m_p_words) ? m_p_words : x_size;
+   const size_t y_words = (y.size() >= m_p_words) ? m_p_words : y.sig_words();
+
+   bigint_mul(z.mutable_data(), z.size(),
+              x_w, x_size, x_words,
+              y.data(), y.size(), y_words,
+              ws.data(), ws.size());
+
+   bigint_monty_redc(z.mutable_data(),
+                     m_p.data(), m_p_words, m_p_dash,
+                     ws.data(), ws.size());
+   }
+
 void CurveGFp_Montgomery::curve_sqr(BigInt& z, const BigInt& x,
                                     secure_vector<word>& ws) const
    {
@@ -183,6 +217,12 @@ class CurveGFp_NIST : public CurveGFp_Repr
       void curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
                      secure_vector<word>& ws) const override;
 
+      void curve_mul_words(BigInt& z,
+                           const word x_words[],
+                           const size_t x_size,
+                           const BigInt& y,
+                           secure_vector<word>& ws) const override;
+
       void curve_sqr(BigInt& z, const BigInt& x,
                      secure_vector<word>& ws) const override;
    private:
@@ -221,6 +261,30 @@ void CurveGFp_NIST::curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
    this->redc(z, ws);
    }
 
+void CurveGFp_NIST::curve_mul_words(BigInt& z,
+                                    const word x_w[],
+                                    size_t x_size,
+                                    const BigInt& y,
+                                    secure_vector<word>& ws) const
+   {
+   if(ws.size() < get_ws_size())
+      ws.resize(get_ws_size());
+
+   const size_t output_size = 2*m_p_words + 2;
+   if(z.size() < output_size)
+      z.grow_to(output_size);
+
+   const size_t x_words = (x_size >= m_p_words) ? m_p_words : x_size;
+   const size_t y_words = (y.size() >= m_p_words) ? m_p_words : y.sig_words();
+
+   bigint_mul(z.mutable_data(), z.size(),
+              x_w, x_size, x_words,
+              y.data(), y.size(), y_words,
+              ws.data(), ws.size());
+
+   this->redc(z, ws);
+   }
+
 void CurveGFp_NIST::curve_sqr(BigInt& z, const BigInt& x,
                               secure_vector<word>& ws) const
    {
diff --git a/src/lib/pubkey/ec_group/curve_gfp.h b/src/lib/pubkey/ec_group/curve_gfp.h
index 2c2d9e619..076922ceb 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.h
+++ b/src/lib/pubkey/ec_group/curve_gfp.h
@@ -49,6 +49,12 @@ class BOTAN_UNSTABLE_API CurveGFp_Repr
       virtual void curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
                              secure_vector<word>& ws) const = 0;
 
+      virtual void curve_mul_words(BigInt& z,
+                                   const word x_words[],
+                                   const size_t x_size,
+                                   const BigInt& y,
+                                   secure_vector<word>& ws) const = 0;
+
       virtual void curve_sqr(BigInt& z, const BigInt& x,
                              secure_vector<word>& ws) const = 0;
    };
@@ -135,6 +141,12 @@ class BOTAN_UNSTABLE_API CurveGFp final
          m_repr->curve_mul(z, x, y, ws);
          }
 
+      void mul(BigInt& z, const word x_w[], size_t x_size,
+               const BigInt& y, secure_vector<word>& ws) const
+         {
+         m_repr->curve_mul_words(z, x_w, x_size, y, ws);
+         }
+
       void sqr(BigInt& z, const BigInt& x, secure_vector<word>& ws) const
          {
          m_repr->curve_sqr(z, x, ws);
diff --git a/src/lib/pubkey/ec_group/point_gfp.cpp b/src/lib/pubkey/ec_group/point_gfp.cpp
index 48ae91f3c..acbda95d4 100644
--- a/src/lib/pubkey/ec_group/point_gfp.cpp
+++ b/src/lib/pubkey/ec_group/point_gfp.cpp
@@ -79,24 +79,43 @@ inline void resize_ws(std::vector<BigInt>& ws_bn, size_t cap_size)
          ws_bn[i].get_word_vector().resize(cap_size);
    }
 
+inline bool all_zeros(const word x[], size_t len)
+   {
+   word z = 0;
+   for(size_t i = 0; i != len; ++i)
+      z |= x[i];
+   return (z == 0);
+   }
 
 }
 
-void PointGFp::add_affine(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
+void PointGFp::add_affine(const PointGFp& rhs, std::vector<BigInt>& workspace)
    {
-   if(rhs.is_zero())
+   BOTAN_DEBUG_ASSERT(rhs.is_affine());
+
+   const size_t p_words = m_curve.get_p_words();
+   add_affine(rhs.m_coord_x.data(), std::min(p_words, rhs.m_coord_x.size()),
+              rhs.m_coord_y.data(), std::min(p_words, rhs.m_coord_y.size()),
+              workspace);
+   }
+
+void PointGFp::add_affine(const word x_words[], size_t x_size,
+                          const word y_words[], size_t y_size,
+                          std::vector<BigInt>& ws_bn)
+   {
+   if(all_zeros(x_words, x_size) && all_zeros(y_words, y_size))
       return;
 
    if(is_zero())
       {
-      m_coord_x = rhs.m_coord_x;
-      m_coord_y = rhs.m_coord_y;
-      m_coord_z = rhs.m_coord_z;
+      // 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());
       return;
       }
 
-   //BOTAN_ASSERT(rhs.is_affine(), "PointGFp::add_affine requires arg be affine point");
-
    resize_ws(ws_bn, m_curve.get_ws_size());
 
    secure_vector<word>& ws = ws_bn[0].get_word_vector();
@@ -115,10 +134,10 @@ void PointGFp::add_affine(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
    const BigInt& p = m_curve.get_p();
 
    m_curve.sqr(T3, m_coord_z, ws); // z1^2
-   m_curve.mul(T4, rhs.m_coord_x, T3, ws); // x2*z1^2
+   m_curve.mul(T4, x_words, x_size, T3, ws); // x2*z1^2
 
    m_curve.mul(T2, m_coord_z, T3, ws); // z1^3
-   m_curve.mul(T0, rhs.m_coord_y, T2, ws); // y2*z1^3
+   m_curve.mul(T0, y_words, y_size, T2, ws); // y2*z1^3
 
    T4 -= m_coord_x; // x2*z1^2 - x1*z2^2
    if(T4.is_negative())
diff --git a/src/lib/pubkey/ec_group/point_gfp.h b/src/lib/pubkey/ec_group/point_gfp.h
index aa7e5b2c0..80c198c62 100644
--- a/src/lib/pubkey/ec_group/point_gfp.h
+++ b/src/lib/pubkey/ec_group/point_gfp.h
@@ -148,6 +148,10 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final
       */
       BigInt get_affine_y() const;
 
+      const BigInt& get_x() const { return m_coord_x; }
+      const BigInt& get_y() const { return m_coord_y; }
+      const BigInt& get_z() const { return m_coord_z; }
+
       /**
       * Force this point to affine coordinates
       */
@@ -211,6 +215,10 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final
       */
       void add_affine(const PointGFp& other, std::vector<BigInt>& workspace);
 
+      void add_affine(const word x_words[], size_t x_size,
+                      const word y_words[], size_t y_size,
+                      std::vector<BigInt>& workspace);
+
       /**
       * Point doubling
       * @param workspace temp space, at least WORKSPACE_SIZE elements
diff --git a/src/lib/pubkey/ec_group/point_mul.cpp b/src/lib/pubkey/ec_group/point_mul.cpp
index adddaaa37..d42a5d5e8 100644
--- a/src/lib/pubkey/ec_group/point_mul.cpp
+++ b/src/lib/pubkey/ec_group/point_mul.cpp
@@ -38,8 +38,10 @@ PointGFp Blinded_Point_Multiply::blinded_multiply(const BigInt& scalar,
    return m_point_mul->mul(scalar, rng, m_order, m_ws);
    }
 
-
-PointGFp_Base_Point_Precompute::PointGFp_Base_Point_Precompute(const PointGFp& base)
+PointGFp_Base_Point_Precompute::PointGFp_Base_Point_Precompute(const PointGFp& base) :
+   m_base_point(base),
+   m_p_words(base.get_curve().get_p().size()),
+   m_T_size(base.get_curve().get_p().bits() + PointGFp_SCALAR_BLINDING_BITS + 1)
    {
    std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
 
@@ -52,25 +54,37 @@ PointGFp_Base_Point_Precompute::PointGFp_Base_Point_Precompute(const PointGFp& b
    */
    const size_t T_bits = round_up(p_bits + PointGFp_SCALAR_BLINDING_BITS + 1, 2) / 2;
 
-   m_T.resize(3*T_bits);
+   std::vector<PointGFp> T(3*T_bits);
+   T.resize(3*T_bits);
 
-   m_T[0] = base;
-   m_T[1] = m_T[0];
-   m_T[1].mult2(ws);
-   m_T[2] = m_T[1];
-   m_T[2].add(m_T[0], ws);
+   T[0] = base;
+   T[1] = T[0];
+   T[1].mult2(ws);
+   T[2] = T[1];
+   T[2].add(T[0], ws);
 
    for(size_t i = 1; i != T_bits; ++i)
       {
-      m_T[3*i+0] = m_T[3*i - 2];
-      m_T[3*i+0].mult2(ws);
-      m_T[3*i+1] = m_T[3*i+0];
-      m_T[3*i+1].mult2(ws);
-      m_T[3*i+2] = m_T[3*i+1];
-      m_T[3*i+2].add(m_T[3*i+0], ws);
+      T[3*i+0] = T[3*i - 2];
+      T[3*i+0].mult2(ws);
+      T[3*i+1] = T[3*i+0];
+      T[3*i+1].mult2(ws);
+      T[3*i+2] = T[3*i+1];
+      T[3*i+2].add(T[3*i+0], ws);
       }
 
-   PointGFp::force_all_affine(m_T, ws[0].get_word_vector());
+   PointGFp::force_all_affine(T, ws[0].get_word_vector());
+
+   m_W.resize(T.size() * 2 * m_p_words);
+
+   word* p = &m_W[0];
+   for(size_t i = 0; i != T.size(); ++i)
+      {
+      T[i].get_x().encode_words(p, m_p_words);
+      p += m_p_words;
+      T[i].get_y().encode_words(p, m_p_words);
+      p += m_p_words;
+      }
    }
 
 PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k,
@@ -87,14 +101,14 @@ PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k,
 
    size_t windows = round_up(scalar.bits(), 2) / 2;
 
-   BOTAN_ASSERT(windows <= m_T.size() / 3,
+   BOTAN_ASSERT(windows <= m_W.size() / (3*2*m_p_words),
                 "Precomputed sufficient values for scalar mult");
 
+   PointGFp R = m_base_point.zero();
+
    if(ws.size() < PointGFp::WORKSPACE_SIZE)
       ws.resize(PointGFp::WORKSPACE_SIZE);
 
-   PointGFp R = m_T[0].zero();
-
    for(size_t i = 0; i != windows; ++i)
       {
       if(i == 4)
@@ -105,7 +119,11 @@ PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k,
       const uint32_t w = scalar.get_substring(2*i, 2);
 
       if(w > 0)
-         R.add_affine(m_T[3*i + w - 1], ws);
+         {
+         const size_t idx = (3*i + w - 1)*2*m_p_words;
+         R.add_affine(&m_W[idx], m_p_words,
+                      &m_W[idx + m_p_words], m_p_words, ws);
+         }
       }
 
    BOTAN_DEBUG_ASSERT(R.on_the_curve());
diff --git a/src/lib/pubkey/ec_group/point_mul.h b/src/lib/pubkey/ec_group/point_mul.h
index 9a19f90d4..64672d9a4 100644
--- a/src/lib/pubkey/ec_group/point_mul.h
+++ b/src/lib/pubkey/ec_group/point_mul.h
@@ -23,7 +23,14 @@ class PointGFp_Base_Point_Precompute
                    const BigInt& group_order,
                    std::vector<BigInt>& ws) const;
    private:
-      std::vector<PointGFp> m_T;
+      const PointGFp& m_base_point;
+      const size_t m_p_words;
+      const size_t m_T_size;
+
+      /*
+      * This is a table of T_size * 3*p_word words
+      */
+      std::vector<word> m_W;
    };
 
 class PointGFp_Var_Point_Precompute