Improve memory handling for PointGFp

5 files changed, 83 insertions, 63 deletions

diff --git a/src/lib/pubkey/ec_group/curve_gfp.cpp b/src/lib/pubkey/ec_group/curve_gfp.cpp
index e17812ca4..131f69c70 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.cpp
+++ b/src/lib/pubkey/ec_group/curve_gfp.cpp
@@ -50,6 +50,8 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr
 
       size_t get_p_words() const override { return m_p_words; }
 
+      size_t get_ws_size() const override { return 2*m_p_words + 4; }
+
       BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
 
       void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override;
@@ -102,12 +104,12 @@ void CurveGFp_Montgomery::curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
       return;
       }
 
-   const size_t output_size = 2*m_p_words + 2;
-   ws.resize(2*(m_p_words+2));
+   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);
-   z.clear();
 
    bigint_mul(z.mutable_data(), z.size(),
               x.data(), x.size(), x.sig_words(),
@@ -131,13 +133,13 @@ void CurveGFp_Montgomery::curve_sqr(BigInt& z, const BigInt& x,
    const size_t x_sw = x.sig_words();
    BOTAN_ASSERT(x_sw <= m_p_words, "Input in range");
 
-   const size_t output_size = 2*m_p_words + 2;
+   if(ws.size() < get_ws_size())
+      ws.resize(get_ws_size());
 
-   ws.resize(2*(m_p_words+2));
+   const size_t output_size = 2*m_p_words + 2;
 
    if(z.size() < output_size)
       z.grow_to(output_size);
-   z.clear();
 
    bigint_sqr(z.mutable_data(), z.size(),
               x.data(), x.size(), x_sw,
@@ -162,6 +164,8 @@ class CurveGFp_NIST : public CurveGFp_Repr
 
       size_t get_p_words() const override { return m_p_words; }
 
+      size_t get_ws_size() const override { return 2*m_p_words + 4; }
+
       const BigInt& get_a_rep() const override { return m_a; }
 
       const BigInt& get_b_rep() const override { return m_b; }
@@ -205,14 +209,12 @@ void CurveGFp_NIST::curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
       return;
       }
 
-   const size_t p_words = get_p_words();
-   const size_t output_size = 2*p_words + 2;
-
-   ws.resize(2*(p_words+2));
+   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);
-   z.clear();
 
    bigint_mul(z.mutable_data(), z.size(),
               x.data(), x.size(), x.sig_words(),
@@ -231,14 +233,12 @@ void CurveGFp_NIST::curve_sqr(BigInt& z, const BigInt& x,
       return;
       }
 
-   const size_t p_words = get_p_words();
-   const size_t output_size = 2*p_words + 2;
-
-   ws.resize(2*(p_words+2));
+   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);
-   z.clear();
 
    bigint_sqr(z.mutable_data(), output_size,
               x.data(), x.size(), x.sig_words(),
diff --git a/src/lib/pubkey/ec_group/curve_gfp.h b/src/lib/pubkey/ec_group/curve_gfp.h
index d9649474b..2c2d9e619 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.h
+++ b/src/lib/pubkey/ec_group/curve_gfp.h
@@ -26,6 +26,8 @@ class BOTAN_UNSTABLE_API CurveGFp_Repr
 
       virtual size_t get_p_words() const = 0;
 
+      virtual size_t get_ws_size() const = 0;
+
       virtual bool is_one(const BigInt& x) const = 0;
 
       /*
@@ -96,6 +98,8 @@ class BOTAN_UNSTABLE_API CurveGFp final
 
       size_t get_p_words() const { return m_repr->get_p_words(); }
 
+      size_t get_ws_size() const { return m_repr->get_ws_size(); }
+
       const BigInt& get_a_rep() const { return m_repr->get_a_rep(); }
 
       const BigInt& get_b_rep() const { return m_repr->get_b_rep(); }
diff --git a/src/lib/pubkey/ec_group/point_gfp.cpp b/src/lib/pubkey/ec_group/point_gfp.cpp
index 587b2a842..6b22f4d01 100644
--- a/src/lib/pubkey/ec_group/point_gfp.cpp
+++ b/src/lib/pubkey/ec_group/point_gfp.cpp
@@ -20,7 +20,7 @@ PointGFp::PointGFp(const CurveGFp& curve) :
    m_coord_y(1),
    m_coord_z(0)
    {
-   secure_vector<word> monty_ws;
+   secure_vector<word> monty_ws(m_curve.get_ws_size());
    m_curve.to_rep(m_coord_x, monty_ws);
    m_curve.to_rep(m_coord_y, monty_ws);
    m_curve.to_rep(m_coord_z, monty_ws);
@@ -37,7 +37,7 @@ PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) :
    if(y <= 0 || y >= curve.get_p())
       throw Invalid_Argument("Invalid PointGFp affine y");
 
-   secure_vector<word> monty_ws;
+   secure_vector<word> monty_ws(m_curve.get_ws_size());
    m_curve.to_rep(m_coord_x, monty_ws);
    m_curve.to_rep(m_coord_y, monty_ws);
    m_curve.to_rep(m_coord_z, monty_ws);
@@ -45,24 +45,43 @@ PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) :
 
 void PointGFp::randomize_repr(RandomNumberGenerator& rng)
    {
+   secure_vector<word> ws(m_curve.get_ws_size());
+   randomize_repr(rng, ws);
+   }
+
+void PointGFp::randomize_repr(RandomNumberGenerator& rng, secure_vector<word>& ws)
+   {
    if(BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS > 1)
       {
       BigInt mask;
       while(mask.is_zero())
          mask.randomize(rng, BOTAN_POINTGFP_RANDOMIZE_BLINDING_BITS, false);
 
-      secure_vector<word> monty_ws;
-
-      m_curve.to_rep(mask, monty_ws);
-      const BigInt mask2 = m_curve.mul_to_tmp(mask, mask, monty_ws);
-      const BigInt mask3 = m_curve.mul_to_tmp(mask2, mask, monty_ws);
+      //m_curve.to_rep(mask, ws);
+      const BigInt mask2 = m_curve.sqr_to_tmp(mask, ws);
+      const BigInt mask3 = m_curve.mul_to_tmp(mask2, mask, ws);
 
-      m_coord_x = m_curve.mul_to_tmp(m_coord_x, mask2, monty_ws);
-      m_coord_y = m_curve.mul_to_tmp(m_coord_y, mask3, monty_ws);
-      m_coord_z = m_curve.mul_to_tmp(m_coord_z, mask, monty_ws);
+      m_coord_x = m_curve.mul_to_tmp(m_coord_x, mask2, ws);
+      m_coord_y = m_curve.mul_to_tmp(m_coord_y, mask3, ws);
+      m_coord_z = m_curve.mul_to_tmp(m_coord_z, mask, ws);
       }
    }
 
+namespace {
+
+inline void resize_ws(std::vector<BigInt>& ws_bn, size_t cap_size)
+   {
+   BOTAN_ASSERT(ws_bn.size() >= PointGFp::WORKSPACE_SIZE,
+                "Expected size for PointGFp workspace");
+
+   for(size_t i = 0; i != ws_bn.size(); ++i)
+      if(ws_bn[i].size() < cap_size)
+         ws_bn[i].get_word_vector().resize(cap_size);
+   }
+
+
+}
+
 void PointGFp::add_affine(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
    {
    if(rhs.is_zero())
@@ -78,14 +97,7 @@ void PointGFp::add_affine(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
 
    //BOTAN_ASSERT(rhs.is_affine(), "PointGFp::add_affine requires arg be affine point");
 
-   const BigInt& p = m_curve.get_p();
-
-   const size_t cap_size = 2*m_curve.get_p_words() + 2;
-
-   BOTAN_ASSERT(ws_bn.size() >= WORKSPACE_SIZE, "Expected size for PointGFp::add workspace");
-
-   for(size_t i = 0; i != ws_bn.size(); ++i)
-      ws_bn[i].ensure_capacity(cap_size);
+   resize_ws(ws_bn, m_curve.get_ws_size());
 
    secure_vector<word>& ws = ws_bn[0].get_word_vector();
 
@@ -100,6 +112,8 @@ void PointGFp::add_affine(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
    simplified with Z2 = 1
    */
 
+   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
 
@@ -172,14 +186,7 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
       return;
       }
 
-   const BigInt& p = m_curve.get_p();
-
-   const size_t cap_size = 2*m_curve.get_p_words() + 2;
-
-   BOTAN_ASSERT(ws_bn.size() >= WORKSPACE_SIZE, "Expected size for PointGFp::add workspace");
-
-   for(size_t i = 0; i != ws_bn.size(); ++i)
-      ws_bn[i].ensure_capacity(cap_size);
+   resize_ws(ws_bn, m_curve.get_ws_size());
 
    secure_vector<word>& ws = ws_bn[0].get_word_vector();
 
@@ -194,6 +201,8 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
    https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
    */
 
+   const BigInt& p = m_curve.get_p();
+
    m_curve.sqr(T0, rhs.m_coord_z, ws); // z2^2
    m_curve.mul(T1, m_coord_x, T0, ws); // x1*z2^2
    m_curve.mul(T3, rhs.m_coord_z, T0, ws); // z2^3
@@ -268,13 +277,7 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
       return;
       }
 
-   const size_t cap_size = 2*m_curve.get_p_words() + 2;
-
-   BOTAN_ASSERT(ws_bn.size() >= WORKSPACE_SIZE, "Expected size for PointGFp::add workspace");
-   for(size_t i = 0; i != ws_bn.size(); ++i)
-      ws_bn[i].ensure_capacity(cap_size);
-
-   const BigInt& p = m_curve.get_p();
+   resize_ws(ws_bn, m_curve.get_ws_size());
 
    secure_vector<word>& ws = ws_bn[0].get_word_vector();
    BigInt& T0 = ws_bn[1];
@@ -286,6 +289,7 @@ void PointGFp::mult2(std::vector<BigInt>& ws_bn)
    /*
    https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-1986-cc
    */
+   const BigInt& p = m_curve.get_p();
 
    m_curve.sqr(T0, m_coord_y, ws);
 
@@ -443,7 +447,8 @@ PointGFp operator*(const BigInt& scalar, const PointGFp& point)
    }
 
 //static
-void PointGFp::force_all_affine(std::vector<PointGFp>& points)
+void PointGFp::force_all_affine(std::vector<PointGFp>& points,
+                                secure_vector<word>& ws)
    {
    if(points.size() <= 1)
       {
@@ -461,9 +466,11 @@ void PointGFp::force_all_affine(std::vector<PointGFp>& points)
    TODO is it really necessary to save all k points in c?
    */
 
-   secure_vector<word> ws;
-
    const CurveGFp& curve = points[0].m_curve;
+
+   if(ws.size() < curve.get_ws_size())
+      ws.resize(curve.get_ws_size());
+
    BigInt rep_1 = 1;
    curve.to_rep(rep_1, ws);
 
@@ -477,23 +484,25 @@ void PointGFp::force_all_affine(std::vector<PointGFp>& points)
 
    BigInt s_inv = curve.invert_element(c[c.size()-1], ws);
 
+   BigInt z_inv, z2_inv, z3_inv;
+
    for(size_t i = points.size() - 1; i != 0; i--)
       {
       PointGFp& point = points[i];
 
-      const BigInt z_inv = curve.mul_to_tmp(s_inv, c[i-1], ws);
+      curve.mul(z_inv, s_inv, c[i-1], ws);
 
       s_inv = curve.mul_to_tmp(s_inv, point.m_coord_z, ws);
 
-      const BigInt z2_inv = curve.sqr_to_tmp(z_inv, ws);
-      const BigInt z3_inv = curve.mul_to_tmp(z_inv, z2_inv, ws);
+      curve.sqr(z2_inv, z_inv, ws);
+      curve.mul(z3_inv, z2_inv, z_inv, ws);
       point.m_coord_x = curve.mul_to_tmp(point.m_coord_x, z2_inv, ws);
       point.m_coord_y = curve.mul_to_tmp(point.m_coord_y, z3_inv, ws);
       point.m_coord_z = rep_1;
       }
 
-   const BigInt z2_inv = curve.sqr_to_tmp(s_inv, ws);
-   const BigInt z3_inv = curve.mul_to_tmp(s_inv, z2_inv, ws);
+   curve.sqr(z2_inv, s_inv, ws);
+   curve.mul(z3_inv, z2_inv, s_inv, ws);
    points[0].m_coord_x = curve.mul_to_tmp(points[0].m_coord_x, z2_inv, ws);
    points[0].m_coord_y = curve.mul_to_tmp(points[0].m_coord_y, z3_inv, ws);
    points[0].m_coord_z = rep_1;
@@ -530,11 +539,11 @@ BigInt PointGFp::get_affine_x() const
    if(is_affine())
       return m_curve.from_rep(m_coord_x, monty_ws);
 
-   const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
-   const BigInt z2_inv = m_curve.invert_element(z2, monty_ws);
+   BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
+   z2 = m_curve.invert_element(z2, monty_ws);
 
    BigInt r;
-   m_curve.mul(r, m_coord_x, z2_inv, monty_ws);
+   m_curve.mul(r, m_coord_x, z2, monty_ws);
    m_curve.from_rep(r, monty_ws);
    return r;
    }
diff --git a/src/lib/pubkey/ec_group/point_gfp.h b/src/lib/pubkey/ec_group/point_gfp.h
index 81e34c634..20018fa2f 100644
--- a/src/lib/pubkey/ec_group/point_gfp.h
+++ b/src/lib/pubkey/ec_group/point_gfp.h
@@ -156,7 +156,8 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final
       /**
       * Force all points on the list to affine coordinates
       */
-      static void force_all_affine(std::vector<PointGFp>& points);
+      static void force_all_affine(std::vector<PointGFp>& points,
+                                   secure_vector<word>& ws);
 
       bool is_affine() const;
 
@@ -187,6 +188,12 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final
       void randomize_repr(RandomNumberGenerator& rng);
 
       /**
+      * Randomize the point representation
+      * The actual value (get_affine_x, get_affine_y) does not change
+      */
+      void randomize_repr(RandomNumberGenerator& rng, secure_vector<word>& ws);
+
+      /**
       * Equality operator
       */
       bool operator==(const PointGFp& other) const;
diff --git a/src/lib/pubkey/ec_group/point_mul.cpp b/src/lib/pubkey/ec_group/point_mul.cpp
index 51d083ad2..bd9b0ca82 100644
--- a/src/lib/pubkey/ec_group/point_mul.cpp
+++ b/src/lib/pubkey/ec_group/point_mul.cpp
@@ -53,7 +53,7 @@ PointGFp_Base_Point_Precompute::PointGFp_Base_Point_Precompute(const PointGFp& b
       m_T[i].mult2(ws);
       }
 
-   PointGFp::force_all_affine(m_T);
+   PointGFp::force_all_affine(m_T, ws[0].get_word_vector());
    }
 
 PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k,
@@ -83,7 +83,7 @@ PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k,
       //if(i % 4 == 3)
       if(i == 4)
          {
-         R.randomize_repr(rng);
+         R.randomize_repr(rng, ws[0].get_word_vector());
          }
 
       if(scalar.get_bit(i))