Merge GH #1478 Add mixed (J+A) point addition, faster scalar mults

16 files changed, 466 insertions, 173 deletions

diff --git a/src/build-data/buildh.in b/src/build-data/buildh.in
index 06ae5b598..fcdd8e6d6 100644
--- a/src/build-data/buildh.in
+++ b/src/build-data/buildh.in
@@ -124,12 +124,6 @@
 #define BOTAN_USE_VOLATILE_MEMSET_FOR_ZERO 1
 
 /*
-* If enabled the ECC implementation will use scalar blinding with order.bits()/2
-* bit long masks.
-*/
-#define BOTAN_POINTGFP_USE_SCALAR_BLINDING 1
-
-/*
 * Set number of bits used to generate mask for blinding the
 * representation of an ECC point. Set to zero to disable this
 * side-channel countermeasure.
diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index d1a4f4946..3a752a3d3 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -1291,28 +1291,35 @@ class Speed final : public Command
             {
             const Botan::EC_Group group(group_name);
 
-            std::unique_ptr<Timer> mult_timer = make_timer(group_name + " scalar mult");
-            std::unique_ptr<Timer> blinded_mult_timer = make_timer(group_name + " blinded scalar mult");
+            std::unique_ptr<Timer> mult_timer = make_timer(group_name + " Montgomery ladder");
+            std::unique_ptr<Timer> blinded_mult_timer = make_timer(group_name + " blinded comb");
+            std::unique_ptr<Timer> blinded_var_mult_timer = make_timer(group_name + " blinded window");
 
-            const Botan::BigInt scalar(rng(), group.get_p_bits());
             const Botan::PointGFp& base_point = group.get_base_point();
 
-            const Botan::PointGFp_Blinded_Multiplier scalar_mult(base_point);
-
             std::vector<Botan::BigInt> ws;
 
-            while(blinded_mult_timer->under(runtime))
+            while(mult_timer->under(runtime) &&
+                  blinded_mult_timer->under(runtime) &&
+                  blinded_var_mult_timer->under(runtime))
                {
+               const Botan::BigInt scalar(rng(), group.get_p_bits());
+
                const Botan::PointGFp r1 = mult_timer->run([&]() { return base_point * scalar; });
 
                const Botan::PointGFp r2 = blinded_mult_timer->run(
-                  [&]() { return scalar_mult.mul(scalar, group.get_order(), rng(), ws); });
+                  [&]() { return group.blinded_base_point_multiply(scalar, rng(), ws); });
+
+               const Botan::PointGFp r3 = blinded_var_mult_timer->run(
+                  [&]() { return group.blinded_var_point_multiply(base_point, scalar, rng(), ws); });
 
-               BOTAN_ASSERT_EQUAL(r1, r2, "Same point computed by both methods");
+               BOTAN_ASSERT_EQUAL(r1, r2, "Same point computed by Montgomery and comb");
+               BOTAN_ASSERT_EQUAL(r1, r3, "Same point computed by Montgomery and window");
                }
 
             record_result(mult_timer);
             record_result(blinded_mult_timer);
+            record_result(blinded_var_mult_timer);
             }
          }
 
diff --git a/src/fuzzer/ecc_helper.h b/src/fuzzer/ecc_helper.h
index cd0ef0ac9..ce0f56988 100644
--- a/src/fuzzer/ecc_helper.h
+++ b/src/fuzzer/ecc_helper.h
@@ -24,35 +24,45 @@ void check_ecc_math(const Botan::EC_Group& group,
    {
    // These depend only on the group, which is also static
    static const Botan::PointGFp base_point = group.get_base_point();
-   static Botan::PointGFp_Blinded_Multiplier blind(base_point);
 
    // This is shared across runs to reduce overhead
-   static std::vector<Botan::BigInt> ws(10);
+   static std::vector<Botan::BigInt> ws(Botan::PointGFp::WORKSPACE_SIZE);
 
    const size_t hlen = len / 2;
    const Botan::BigInt a = Botan::BigInt::decode(in, hlen);
    const Botan::BigInt b = Botan::BigInt::decode(in + hlen, len - hlen);
-
    const Botan::BigInt c = a + b;
 
-   const Botan::PointGFp P = base_point * a;
-   const Botan::PointGFp Q = base_point * b;
-   const Botan::PointGFp R = base_point * c;
+   const Botan::PointGFp P1 = base_point * a;
+   const Botan::PointGFp Q1 = base_point * b;
+   const Botan::PointGFp R1 = base_point * c;
 
-   const Botan::PointGFp A1 = P + Q;
-   const Botan::PointGFp A2 = Q + P;
+   const Botan::PointGFp S1 = P1 + Q1;
+   const Botan::PointGFp T1 = Q1 + P1;
 
-   FUZZER_ASSERT_EQUAL(A1, A2);
+   FUZZER_ASSERT_EQUAL(S1, R1);
+   FUZZER_ASSERT_EQUAL(T1, R1);
 
-   const Botan::PointGFp P1 = blind.mul(a, group.get_order(), fuzzer_rng(), ws);
-   const Botan::PointGFp Q1 = blind.mul(b, group.get_order(), fuzzer_rng(), ws);
-   const Botan::PointGFp R1 = blind.mul(c, group.get_order(), fuzzer_rng(), ws);
+   const Botan::PointGFp P2 = group.blinded_base_point_multiply(a, fuzzer_rng(), ws);
+   const Botan::PointGFp Q2 = group.blinded_base_point_multiply(b, fuzzer_rng(), ws);
+   const Botan::PointGFp R2 = group.blinded_base_point_multiply(c, fuzzer_rng(), ws);
+   const Botan::PointGFp S2 = P2 + Q2;
+   const Botan::PointGFp T2 = Q2 + P2;
 
-   const Botan::PointGFp S1 = P1 + Q1;
-   const Botan::PointGFp S2 = Q1 + P1;
+   FUZZER_ASSERT_EQUAL(S2, R2);
+   FUZZER_ASSERT_EQUAL(T2, R2);
+
+   const Botan::PointGFp P3 = group.blinded_var_point_multiply(base_point, a, fuzzer_rng(), ws);
+   const Botan::PointGFp Q3 = group.blinded_var_point_multiply(base_point, b, fuzzer_rng(), ws);
+   const Botan::PointGFp R3 = group.blinded_var_point_multiply(base_point, c, fuzzer_rng(), ws);
+   const Botan::PointGFp S3 = P3 + Q3;
+   const Botan::PointGFp T3 = Q3 + P3;
+
+   FUZZER_ASSERT_EQUAL(S3, R3);
+   FUZZER_ASSERT_EQUAL(T3, R3);
 
    FUZZER_ASSERT_EQUAL(S1, S2);
-   FUZZER_ASSERT_EQUAL(S1, A1);
+   FUZZER_ASSERT_EQUAL(S1, S3);
    }
 
 }
diff --git a/src/lib/pubkey/ec_group/curve_gfp.cpp b/src/lib/pubkey/ec_group/curve_gfp.cpp
index 216f2a894..e17812ca4 100644
--- a/src/lib/pubkey/ec_group/curve_gfp.cpp
+++ b/src/lib/pubkey/ec_group/curve_gfp.cpp
@@ -25,13 +25,15 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr
          m_p_words(m_p.sig_words()),
          m_p_dash(monty_inverse(m_p.word_at(0)))
          {
-         const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
-
          Modular_Reducer mod_p(m_p);
 
-         m_r2  = mod_p.square(r);
-         m_a_r = mod_p.multiply(r, m_a);
-         m_b_r = mod_p.multiply(r, m_b);
+         m_r.set_bit(m_p_words * BOTAN_MP_WORD_BITS);
+         m_r = mod_p.reduce(m_r);
+
+         m_r2  = mod_p.square(m_r);
+         m_r3  = mod_p.multiply(m_r, m_r2);
+         m_a_r = mod_p.multiply(m_r, m_a);
+         m_b_r = mod_p.multiply(m_r, m_b);
          }
 
       const BigInt& get_a() const override { return m_a; }
@@ -44,8 +46,12 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr
 
       const BigInt& get_b_rep() const override { return m_b_r; }
 
+      bool is_one(const BigInt& x) const override { return x == m_r; }
+
       size_t get_p_words() const override { return m_p_words; }
 
+      BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
+
       void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override;
 
       void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override;
@@ -56,14 +62,25 @@ class CurveGFp_Montgomery final : public CurveGFp_Repr
       void curve_sqr(BigInt& z, const BigInt& x,
                      secure_vector<word>& ws) const override;
    private:
-      BigInt m_p, m_a, m_b;
+      BigInt m_p;
+      BigInt m_a, m_b;
+      BigInt m_a_r, m_b_r;
       size_t m_p_words; // cache of m_p.sig_words()
 
       // Montgomery parameters
-      BigInt m_r2, m_a_r, m_b_r;
+      BigInt m_r, m_r2, m_r3;
       word m_p_dash;
    };
 
+BigInt CurveGFp_Montgomery::invert_element(const BigInt& x, secure_vector<word>& ws) const
+   {
+   // Should we use Montgomery inverse instead?
+   const BigInt inv = inverse_mod(x, m_p);
+   BigInt res;
+   curve_mul(res, inv, m_r3, ws);
+   return res;
+   }
+
 void CurveGFp_Montgomery::to_curve_rep(BigInt& x, secure_vector<word>& ws) const
    {
    const BigInt tx = x;
@@ -149,12 +166,16 @@ class CurveGFp_NIST : public CurveGFp_Repr
 
       const BigInt& get_b_rep() const override { return m_b; }
 
+      bool is_one(const BigInt& x) const override { return x == 1; }
+
       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); }
 
+      BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const override;
+
       void curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
                      secure_vector<word>& ws) const override;
 
@@ -168,6 +189,13 @@ class CurveGFp_NIST : public CurveGFp_Repr
       size_t m_p_words; // cache of m_p.sig_words()
    };
 
+
+BigInt CurveGFp_NIST::invert_element(const BigInt& x, secure_vector<word>& ws) const
+   {
+   BOTAN_UNUSED(ws);
+   return inverse_mod(x, get_p());
+   }
+
 void CurveGFp_NIST::curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
                               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 60e1a485d..d9649474b 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 bool is_one(const BigInt& x) const = 0;
+
       /*
       * Returns to_curve_rep(get_a())
       */
@@ -36,6 +38,8 @@ class BOTAN_UNSTABLE_API CurveGFp_Repr
       */
       virtual const BigInt& get_b_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;
 
       virtual void from_curve_rep(BigInt& x, secure_vector<word>& ws) const = 0;
@@ -96,6 +100,13 @@ class BOTAN_UNSTABLE_API CurveGFp final
 
       const BigInt& get_b_rep() const { return m_repr->get_b_rep(); }
 
+      bool is_one(const BigInt& x) const { return m_repr->is_one(x); }
+
+      BigInt invert_element(const BigInt& x, secure_vector<word>& ws) const
+         {
+         return m_repr->invert_element(x, ws);
+         }
+
       void to_rep(BigInt& x, secure_vector<word>& ws) const
          {
          m_repr->to_curve_rep(x, ws);
diff --git a/src/lib/pubkey/ec_group/ec_group.cpp b/src/lib/pubkey/ec_group/ec_group.cpp
index 9da1cd81f..723a4148e 100644
--- a/src/lib/pubkey/ec_group/ec_group.cpp
+++ b/src/lib/pubkey/ec_group/ec_group.cpp
@@ -9,6 +9,7 @@
 */
 
 #include <botan/ec_group.h>
+#include <botan/internal/point_mul.h>
 #include <botan/ber_dec.h>
 #include <botan/der_enc.h>
 #include <botan/oids.h>
@@ -17,10 +18,6 @@
 #include <botan/mutex.h>
 #include <vector>
 
-#if defined(BOTAN_HAS_SYSTEM_RNG)
-   #include <botan/system_rng.h>
-#endif
-
 namespace Botan {
 
 class EC_Group_Data final
@@ -42,15 +39,12 @@ class EC_Group_Data final
          m_order(order),
          m_cofactor(cofactor),
          m_mod_order(order),
-         m_base_mult(m_base_point, 5),
+         m_base_mult(m_base_point),
          m_oid(oid),
          m_p_bits(p.bits()),
          m_order_bits(order.bits()),
          m_a_is_minus_3(a == p - 3)
          {
-#if defined(BOTAN_HAS_SYSTEM_RNG)
-         m_base_mult.randomize(system_rng());
-#endif
          }
 
       bool match(const BigInt& p, const BigInt& a, const BigInt& b,
@@ -97,7 +91,7 @@ class EC_Group_Data final
                                            RandomNumberGenerator& rng,
                                            std::vector<BigInt>& ws) const
          {
-         return m_base_mult.mul(k, m_order, rng, ws);
+         return m_base_mult.mul(k, rng, m_order, ws);
          }
 
    private:
@@ -109,7 +103,7 @@ class EC_Group_Data final
       BigInt m_order;
       BigInt m_cofactor;
       Modular_Reducer m_mod_order;
-      PointGFp_Blinded_Multiplier m_base_mult;
+      PointGFp_Base_Point_Precompute m_base_mult;
       OID m_oid;
       size_t m_p_bits;
       size_t m_order_bits;
@@ -489,6 +483,16 @@ PointGFp EC_Group::blinded_base_point_multiply(const BigInt& k,
    return data().blinded_base_point_multiply(k, rng, ws);
    }
 
+PointGFp EC_Group::blinded_var_point_multiply(const PointGFp& point,
+                                              const BigInt& k,
+                                              RandomNumberGenerator& rng,
+                                              std::vector<BigInt>& ws) const
+   {
+   PointGFp_Var_Point_Precompute mul(point);
+   mul.randomize_repr(rng);
+   return mul.mul(k, rng, get_order(), ws);
+   }
+
 PointGFp EC_Group::zero_point() const
    {
    return PointGFp(data().curve());
diff --git a/src/lib/pubkey/ec_group/ec_group.h b/src/lib/pubkey/ec_group/ec_group.h
index 938059fc4..8238c2902 100644
--- a/src/lib/pubkey/ec_group/ec_group.h
+++ b/src/lib/pubkey/ec_group/ec_group.h
@@ -247,6 +247,19 @@ class BOTAN_PUBLIC_API(2,0) EC_Group final
                                            std::vector<BigInt>& ws) const;
 
       /**
+      * Blinded point multiplication, attempts resistance to side channels
+      * @param point input point
+      * @param k the scalar
+      * @param rng a random number generator
+      * @param ws a temp workspace
+      * @return point*k
+      */
+      PointGFp blinded_var_point_multiply(const PointGFp& point,
+                                          const BigInt& k,
+                                          RandomNumberGenerator& rng,
+                                          std::vector<BigInt>& ws) const;
+
+      /**
       * Return the zero (or infinite) point on this curve
       */
       PointGFp zero_point() const;
diff --git a/src/lib/pubkey/ec_group/info.txt b/src/lib/pubkey/ec_group/info.txt
index a0d025379..e382e25a5 100644
--- a/src/lib/pubkey/ec_group/info.txt
+++ b/src/lib/pubkey/ec_group/info.txt
@@ -8,3 +8,13 @@ asn1
 numbertheory
 pem
 </requires>
+
+<header:internal>
+point_mul.h
+</header:internal>
+
+<header:public>
+curve_gfp.h
+ec_group.h
+point_gfp.h
+</header:public>
diff --git a/src/lib/pubkey/ec_group/point_gfp.cpp b/src/lib/pubkey/ec_group/point_gfp.cpp
index da8b292f4..7968d2dcd 100644
--- a/src/lib/pubkey/ec_group/point_gfp.cpp
+++ b/src/lib/pubkey/ec_group/point_gfp.cpp
@@ -63,9 +63,113 @@ void PointGFp::randomize_repr(RandomNumberGenerator& rng)
       }
    }
 
+void PointGFp::add_affine(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
+   {
+   if(rhs.is_zero())
+      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;
+      return;
+      }
+
+   BOTAN_ASSERT(rhs.is_affine(), "PointGFp::add_affine requires arg be affine point");
+
+   /*
+   https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
+   simplified with Z2 = 1
+   */
+
+   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);
+
+   secure_vector<word>& ws = ws_bn[0].get_word_vector();
+
+   BigInt& T0 = ws_bn[1];
+   BigInt& T1 = ws_bn[2];
+   BigInt& T2 = ws_bn[3];
+   BigInt& T3 = ws_bn[4];
+   BigInt& T4 = ws_bn[5];
+
+   /*
+   https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-1998-cmo-2
+   */
+
+   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(T2, m_coord_z, T3, ws); // z1^3
+   m_curve.mul(T0, rhs.m_coord_y, T2, ws); // y2*z1^3
+
+   T4 -= m_coord_x; // x2*z1^2 - x1*z2^2
+   if(T4.is_negative())
+      T4 += p;
+
+   T0 -= m_coord_y;
+   if(T0.is_negative())
+      T0 += p;
+
+   if(T4.is_zero())
+      {
+      if(T0.is_zero())
+         {
+         mult2(ws_bn);
+         return;
+         }
+
+      // setting to zero:
+      m_coord_x = 0;
+      m_coord_y = 1;
+      m_coord_z = 0;
+      return;
+      }
+
+   m_curve.sqr(T2, T4, ws);
+
+   m_curve.mul(T3, m_coord_x, T2, ws);
+
+   m_curve.mul(T1, T2, T4, ws);
+
+   m_curve.sqr(m_coord_x, T0, ws);
+   m_coord_x -= T1;
+   m_coord_x -= T3;
+   m_coord_x -= T3;
+   while(m_coord_x.is_negative())
+      m_coord_x += p;
+
+   T3 -= m_coord_x;
+   if(T3.is_negative())
+      T3 += p;
+
+   T2 = m_coord_y;
+   m_curve.mul(m_coord_y, T0, T3, ws);
+   m_curve.mul(T3, T2, T1, ws);
+   m_coord_y -= T3;
+   if(m_coord_y.is_negative())
+      m_coord_y += p;
+
+   T3 = m_coord_z;
+   m_curve.mul(m_coord_z, T3, T4, ws);
+   }
+
 // Point addition
 void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
    {
+   if(rhs.is_zero())
+      return;
+
+   if(rhs.is_affine())
+      return this->add_affine(rhs, ws_bn);
+
    if(is_zero())
       {
       m_coord_x = rhs.m_coord_x;
@@ -73,8 +177,6 @@ void PointGFp::add(const PointGFp& rhs, std::vector<BigInt>& ws_bn)
       m_coord_z = rhs.m_coord_z;
       return;
       }
-   else if(rhs.is_zero())
-      return;
 
    const BigInt& p = m_curve.get_p();
 
@@ -345,17 +447,48 @@ PointGFp operator*(const BigInt& scalar, const PointGFp& point)
    return R[0];
    }
 
+void PointGFp::force_affine()
+   {
+   if(is_zero())
+      throw Invalid_State("Cannot convert zero ECC point to affine");
+
+   secure_vector<word> ws;
+   BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, ws);
+   BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, ws);
+
+   const BigInt z5 = m_curve.mul_to_tmp(z2, z3, ws);
+   const BigInt z5_inv = m_curve.invert_element(z5, ws);
+   const BigInt z2_inv = m_curve.mul_to_tmp(z5_inv, z3, ws);
+   const BigInt z3_inv = m_curve.mul_to_tmp(z5_inv, z2, 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);
+   }
+
+bool PointGFp::is_affine() const
+   {
+   return m_curve.is_one(m_coord_z);
+   }
+
 BigInt PointGFp::get_affine_x() const
    {
    if(is_zero())
       throw Illegal_Transformation("Cannot convert zero point to affine");
 
    secure_vector<word> monty_ws;
-   BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
-   m_curve.from_rep(z2, monty_ws);
-   z2 = inverse_mod(z2, m_curve.get_p());
 
-   return m_curve.mul_to_tmp(z2, m_coord_x, monty_ws);
+   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 r;
+   m_curve.mul(r, m_coord_x, z2_inv, monty_ws);
+   m_curve.from_rep(r, monty_ws);
+   return r;
    }
 
 BigInt PointGFp::get_affine_y() const
@@ -364,11 +497,18 @@ BigInt PointGFp::get_affine_y() const
       throw Illegal_Transformation("Cannot convert zero point to affine");
 
    secure_vector<word> monty_ws;
-   BigInt z3 = m_curve.mul_to_tmp(m_coord_z, m_curve.sqr_to_tmp(m_coord_z, monty_ws), monty_ws);
-   z3 = inverse_mod(z3, m_curve.get_p());
-   m_curve.to_rep(z3, monty_ws);
 
-   return m_curve.mul_to_tmp(z3, m_coord_y, monty_ws);
+   if(is_affine())
+      return m_curve.from_rep(m_coord_y, monty_ws);
+
+   const BigInt z2 = m_curve.sqr_to_tmp(m_coord_z, monty_ws);
+   const BigInt z3 = m_curve.mul_to_tmp(m_coord_z, z2, monty_ws);
+   const BigInt z3_inv = m_curve.invert_element(z3, monty_ws);
+
+   BigInt r;
+   m_curve.mul(r, m_coord_y, z3_inv, monty_ws);
+   m_curve.from_rep(r, monty_ws);
+   return r;
    }
 
 bool PointGFp::on_the_curve() const
diff --git a/src/lib/pubkey/ec_group/point_gfp.h b/src/lib/pubkey/ec_group/point_gfp.h
index abcc9656e..56844a26f 100644
--- a/src/lib/pubkey/ec_group/point_gfp.h
+++ b/src/lib/pubkey/ec_group/point_gfp.h
@@ -149,6 +149,13 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final
       BigInt get_affine_y() const;
 
       /**
+      * Force this point to affine coordinates
+      */
+      void force_affine();
+
+      bool is_affine() const;
+
+      /**
       * Is this the point at infinity?
       * @result true, if this point is at infinity, false otherwise.
       */
@@ -186,6 +193,13 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final
       void add(const PointGFp& other, std::vector<BigInt>& workspace);
 
       /**
+      * Point addition - mixed J+A
+      * @param other affine point to add
+      * @param workspace temp space, at least WORKSPACE_SIZE elements
+      */
+      void add_affine(const PointGFp& other, std::vector<BigInt>& workspace);
+
+      /**
       * Point doubling
       * @param workspace temp space, at least WORKSPACE_SIZE elements
       */
@@ -284,69 +298,24 @@ template<typename Alloc>
 PointGFp OS2ECP(const std::vector<uint8_t, Alloc>& data, const CurveGFp& curve)
    { return OS2ECP(data.data(), data.size(), curve); }
 
+class PointGFp_Var_Point_Precompute;
+
 /**
-* Blinded ECC point multiplication
+* Deprecated API for point multiplication
+* Use EC_Group::blinded_base_point_multiply or EC_Group::blinded_var_point_multiply
 */
-class BOTAN_PUBLIC_API(2,5) PointGFp_Blinded_Multiplier final
+class BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("See comments") Blinded_Point_Multiply final
    {
    public:
-      /**
-      * @param base_point the point that will be multiplied (eg, the base point of the curve)
-      * @param w the window bits (leave as zero to take a default value)
-      */
-      PointGFp_Blinded_Multiplier(const PointGFp& base_point,
-                                  size_t w = 0);
+      Blinded_Point_Multiply(const PointGFp& base, const BigInt& order, size_t h = 0);
 
-      /**
-      * @param base_point the point that will be multiplied (eg, the base point of the curve)
-      * @param ws a temporary workspace
-      * @param w the window bits (leave as zero to take a default value)
-      */
-      PointGFp_Blinded_Multiplier(const PointGFp& base_point,
-                                  std::vector<BigInt>& ws,
-                                  size_t w = 0);
+      ~Blinded_Point_Multiply();
 
-      /**
-      * Randomize the internal state. Changing the values may provide
-      * some protection against side channel attacks.
-      * @param rng a random number generator
-      */
-      void randomize(RandomNumberGenerator& rng);
-
-      /**
-      * Perform blinded point multiplication
-      * @param k the scalar
-      * @param group_order the order of the group
-      * @param rng a random number generator
-      * @param ws a temporary workspace
-      * @return base_point*k
-      */
-      PointGFp mul(const BigInt& k,
-                   const BigInt& group_order,
-                   RandomNumberGenerator& rng,
-                   std::vector<BigInt>& ws) const;
-   private:
-      void init(const PointGFp& base_point, size_t w, std::vector<BigInt>& ws);
-
-      std::vector<PointGFp> m_U;
-      size_t m_h;
-   };
-
-class BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use PointGFp_Blinded_Multiplier") Blinded_Point_Multiply final
-   {
-   public:
-      Blinded_Point_Multiply(const PointGFp& base, const BigInt& order, size_t h = 0) :
-         m_ws(PointGFp::WORKSPACE_SIZE), m_order(order), m_point_mul(base, m_ws, h) {}
-
-      PointGFp blinded_multiply(const BigInt& scalar, RandomNumberGenerator& rng)
-         {
-         m_point_mul.randomize(rng);
-         return m_point_mul.mul(scalar, m_order, rng, m_ws);
-         }
+      PointGFp blinded_multiply(const BigInt& scalar, RandomNumberGenerator& rng);
    private:
       std::vector<BigInt> m_ws;
       const BigInt& m_order;
-      PointGFp_Blinded_Multiplier m_point_mul;
+      std::unique_ptr<PointGFp_Var_Point_Precompute> m_point_mul;
    };
 
 }
diff --git a/src/lib/pubkey/ec_group/point_mul.cpp b/src/lib/pubkey/ec_group/point_mul.cpp
index 314807166..2a63a8221 100644
--- a/src/lib/pubkey/ec_group/point_mul.cpp
+++ b/src/lib/pubkey/ec_group/point_mul.cpp
@@ -4,86 +4,142 @@
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
-#include <botan/point_gfp.h>
+#include <botan/internal/point_mul.h>
 #include <botan/rng.h>
 #include <botan/internal/rounding.h>
 
 namespace Botan {
 
-PointGFp_Blinded_Multiplier::PointGFp_Blinded_Multiplier(const PointGFp& base,
-                                                         std::vector<BigInt>& ws,
-                                                         size_t w)
+Blinded_Point_Multiply::Blinded_Point_Multiply(const PointGFp& base,
+                                               const BigInt& order,
+                                               size_t h) :
+   m_ws(PointGFp::WORKSPACE_SIZE),
+   m_order(order)
    {
-   init(base, w, ws);
+   BOTAN_UNUSED(h);
+   m_point_mul.reset(new PointGFp_Var_Point_Precompute(base));
    }
 
-PointGFp_Blinded_Multiplier::PointGFp_Blinded_Multiplier(const PointGFp& base,
-                                                         size_t w)
+Blinded_Point_Multiply::~Blinded_Point_Multiply()
+   {
+   /* for ~unique_ptr */
+   }
+
+PointGFp Blinded_Point_Multiply::blinded_multiply(const BigInt& scalar,
+                                                  RandomNumberGenerator& rng)
+   {
+   return m_point_mul->mul(scalar, rng, m_order, m_ws);
+   }
+
+
+PointGFp_Base_Point_Precompute::PointGFp_Base_Point_Precompute(const PointGFp& base)
    {
    std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
-   init(base, w, ws);
+
+   const size_t p_bits = base.get_curve().get_p().bits();
+
+   /*
+   * Some of the curves (eg secp160k1) have an order slightly larger than
+   * the size of the prime modulus. In all cases they are at most 1 bit
+   * longer. The +1 compensates for this.
+   */
+   const size_t T_bits = p_bits + PointGFp_SCALAR_BLINDING_BITS + 1;
+
+   m_T.push_back(base);
+
+   for(size_t i = 1; i != T_bits; ++i)
+      {
+      m_T.push_back(m_T[i-1]);
+      m_T[i].mult2(ws);
+      }
+
+   for(size_t i = 0; i != m_T.size(); ++i)
+      m_T[i].force_affine();
    }
 
-void PointGFp_Blinded_Multiplier::init(const PointGFp& base,
-                                       size_t w,
-                                       std::vector<BigInt>& ws)
+PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k,
+                                             RandomNumberGenerator& rng,
+                                             const BigInt& group_order,
+                                             std::vector<BigInt>& ws) const
    {
-   m_h = (w == 0 ? 5 : w);
+   if(k.is_negative())
+      throw Invalid_Argument("PointGFp_Base_Point_Precompute scalar must be positive");
+
+   // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
+   const BigInt mask(rng, PointGFp_SCALAR_BLINDING_BITS, false);
+   const BigInt scalar = k + group_order * mask;
+
+   const size_t scalar_bits = scalar.bits();
+
+   BOTAN_ASSERT(scalar_bits <= m_T.size(),
+                "Precomputed sufficient values for scalar mult");
+
+   PointGFp R = m_T[0].zero();
 
    if(ws.size() < PointGFp::WORKSPACE_SIZE)
       ws.resize(PointGFp::WORKSPACE_SIZE);
 
-   // Upper bound is a sanity check rather than hard limit
-   if(m_h < 1 || m_h > 8)
-      throw Invalid_Argument("PointGFp_Blinded_Multiplier invalid w param");
+   for(size_t i = 0; i != scalar_bits; ++i)
+      {
+      //if(i % 4 == 3)
+      if(i == 4)
+         {
+         R.randomize_repr(rng);
+         }
+
+      if(scalar.get_bit(i))
+         R.add(m_T[i], ws);
+      }
 
-   m_U.resize(1 << m_h);
-   m_U[0] = base.zero();
-   m_U[1] = base;
+   return R;
+   }
 
+PointGFp_Var_Point_Precompute::PointGFp_Var_Point_Precompute(const PointGFp& point)
+   {
+   m_window_bits = 4;
+
+   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)
       {
       m_U[i] = m_U[i-1];
-      m_U[i].add(base, ws);
+      m_U[i].add(point, ws);
       }
    }
 
-void PointGFp_Blinded_Multiplier::randomize(RandomNumberGenerator& rng)
+void PointGFp_Var_Point_Precompute::randomize_repr(RandomNumberGenerator& rng)
    {
-   // Randomize each point representation (Coron's 3rd countermeasure)
-   for(size_t i = 0; i != m_U.size(); ++i)
+   for(size_t i = 1; i != m_U.size(); ++i)
       m_U[i].randomize_repr(rng);
    }
 
-PointGFp PointGFp_Blinded_Multiplier::mul(const BigInt& k,
-                                          const BigInt& group_order,
-                                          RandomNumberGenerator& rng,
-                                          std::vector<BigInt>& ws) const
+PointGFp PointGFp_Var_Point_Precompute::mul(const BigInt& k,
+                                            RandomNumberGenerator& rng,
+                                            const BigInt& group_order,
+                                            std::vector<BigInt>& ws) const
    {
    if(k.is_negative())
-      throw Invalid_Argument("PointGFp_Blinded_Multiplier scalar must be positive");
+      throw Invalid_Argument("PointGFp_Base_Point_Precompute scalar must be positive");
+   if(ws.size() < PointGFp::WORKSPACE_SIZE)
+      ws.resize(PointGFp::WORKSPACE_SIZE);
 
-#if BOTAN_POINTGFP_USE_SCALAR_BLINDING
    // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
-   const BigInt mask(rng, group_order.bits() / 4, false);
+   const BigInt mask(rng, PointGFp_SCALAR_BLINDING_BITS, false);
    const BigInt scalar = k + group_order * mask;
-#else
-   const BigInt& scalar = k;
-#endif
-
-   if(ws.size() < PointGFp::WORKSPACE_SIZE)
-      ws.resize(PointGFp::WORKSPACE_SIZE);
 
    const size_t scalar_bits = scalar.bits();
 
-   size_t windows = round_up(scalar_bits, m_h) / m_h;
+   size_t windows = round_up(scalar_bits, m_window_bits) / m_window_bits;
 
    PointGFp R = m_U[0];
 
    if(windows > 0)
       {
       windows--;
-      const uint32_t nibble = scalar.get_substring(windows*m_h, m_h);
+      const uint32_t nibble = scalar.get_substring(windows*m_window_bits, m_window_bits);
       R.add(m_U[nibble], ws);
 
       /*
@@ -95,18 +151,16 @@ PointGFp PointGFp_Blinded_Multiplier::mul(const BigInt& k,
 
       while(windows)
          {
-         for(size_t i = 0; i != m_h; ++i)
+         for(size_t i = 0; i != m_window_bits; ++i)
             R.mult2(ws);
 
-         const uint32_t inner_nibble = scalar.get_substring((windows-1)*m_h, m_h);
+         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...
          R.add(m_U[inner_nibble], ws);
          windows--;
          }
       }
 
-   //BOTAN_ASSERT(R.on_the_curve(), "Output is on the curve");
-
    return R;
    }
 
diff --git a/src/lib/pubkey/ec_group/point_mul.h b/src/lib/pubkey/ec_group/point_mul.h
new file mode 100644
index 000000000..97fd326a2
--- /dev/null
+++ b/src/lib/pubkey/ec_group/point_mul.h
@@ -0,0 +1,47 @@
+/*
+* (C) 2018 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_POINT_MUL_H_
+#define BOTAN_POINT_MUL_H_
+
+#include <botan/point_gfp.h>
+
+namespace Botan {
+
+static const size_t PointGFp_SCALAR_BLINDING_BITS = 80;
+
+class PointGFp_Base_Point_Precompute
+   {
+   public:
+      PointGFp_Base_Point_Precompute(const PointGFp& base_point);
+
+      PointGFp mul(const BigInt& k,
+                   RandomNumberGenerator& rng,
+                   const BigInt& group_order,
+                   std::vector<BigInt>& ws) const;
+   private:
+      std::vector<PointGFp> m_T;
+   };
+
+class PointGFp_Var_Point_Precompute
+   {
+   public:
+      PointGFp_Var_Point_Precompute(const PointGFp& point);
+
+      void randomize_repr(RandomNumberGenerator& rng);
+
+      PointGFp mul(const BigInt& k,
+                   RandomNumberGenerator& rng,
+                   const BigInt& group_order,
+                   std::vector<BigInt>& ws) const;
+   private:
+      size_t m_window_bits;
+      std::vector<PointGFp> m_U;
+   };
+
+}
+
+#endif
diff --git a/src/lib/pubkey/ecdh/ecdh.cpp b/src/lib/pubkey/ecdh/ecdh.cpp
index 4989fa0a5..adadb2703 100644
--- a/src/lib/pubkey/ecdh/ecdh.cpp
+++ b/src/lib/pubkey/ecdh/ecdh.cpp
@@ -39,9 +39,8 @@ class ECDH_KA_Operation final : public PK_Ops::Key_Agreement_with_KDF
          PointGFp input_point = m_group.get_cofactor() * m_group.OS2ECP(w, w_len);
          input_point.randomize_repr(m_rng);
 
-         PointGFp_Blinded_Multiplier blinder(input_point, m_ws);
-
-         const PointGFp S = blinder.mul(m_l_times_priv, m_group.get_order(), m_rng, m_ws);
+         const PointGFp S = m_group.blinded_var_point_multiply(
+            input_point, m_l_times_priv, m_rng, m_ws);
 
          if(S.on_the_curve() == false)
             throw Internal_Error("ECDH agreed value was not on the curve");
diff --git a/src/lib/pubkey/ecies/ecies.cpp b/src/lib/pubkey/ecies/ecies.cpp
index 1120a850a..06d5cfeee 100644
--- a/src/lib/pubkey/ecies/ecies.cpp
+++ b/src/lib/pubkey/ecies/ecies.cpp
@@ -71,9 +71,8 @@ class ECIES_ECDH_KA_Operation final : public PK_Ops::Key_Agreement_with_KDF
          PointGFp input_point = group.OS2ECP(w, w_len);
          input_point.randomize_repr(m_rng);
 
-         PointGFp_Blinded_Multiplier blinder(input_point, m_ws);
-
-         const PointGFp S = blinder.mul(m_key.private_value(), group.get_order(), m_rng, m_ws);
+         const PointGFp S = group.blinded_var_point_multiply(
+            input_point, m_key.private_value(), m_rng, m_ws);
 
          if(S.on_the_curve() == false)
             throw Internal_Error("ECDH agreed value was not on the curve");
diff --git a/src/lib/pubkey/sm2/sm2_enc.cpp b/src/lib/pubkey/sm2/sm2_enc.cpp
index b0d773635..4a6aa2b6e 100644
--- a/src/lib/pubkey/sm2/sm2_enc.cpp
+++ b/src/lib/pubkey/sm2/sm2_enc.cpp
@@ -6,6 +6,7 @@
 */
 
 #include <botan/sm2_enc.h>
+#include <botan/internal/point_mul.h>
 #include <botan/pk_ops.h>
 #include <botan/keypair.h>
 #include <botan/der_enc.h>
@@ -76,7 +77,7 @@ class SM2_Encryption_Operation final : public PK_Ops::Encryption
          BigInt::encode_1363(x1_bytes.data(), x1_bytes.size(), x1);
          BigInt::encode_1363(y1_bytes.data(), y1_bytes.size(), y1);
 
-         const PointGFp kPB = m_mul_public_point.mul(k, m_group.get_order(), rng, m_ws);
+         const PointGFp kPB = m_mul_public_point.mul(k, rng, m_group.get_order(), m_ws);
 
          const BigInt x2 = kPB.get_affine_x();
          const BigInt y2 = kPB.get_affine_y();
@@ -113,7 +114,7 @@ class SM2_Encryption_Operation final : public PK_Ops::Encryption
 
    private:
       const EC_Group m_group;
-      PointGFp_Blinded_Multiplier m_mul_public_point;
+      PointGFp_Var_Point_Precompute m_mul_public_point;
       const std::string m_kdf_hash;
       std::vector<BigInt> m_ws;
    };
@@ -161,6 +162,8 @@ class SM2_Decryption_Operation final : public PK_Ops::Decryption
             .verify_end();
 
          PointGFp C1 = group.point(x1, y1);
+         C1.randomize_repr(m_rng);
+
          if(!C1.on_the_curve())
             return secure_vector<uint8_t>();
 
@@ -169,11 +172,8 @@ class SM2_Decryption_Operation final : public PK_Ops::Decryption
             return secure_vector<uint8_t>();
             }
 
-         C1.randomize_repr(m_rng);
-
-         PointGFp_Blinded_Multiplier C1_mul(C1);
-
-         const PointGFp dbC1 = C1_mul.mul(m_key.private_value(), group.get_order(), m_rng, m_ws);
+         const PointGFp dbC1 = group.blinded_var_point_multiply(
+            C1, m_key.private_value(), m_rng, m_ws);
 
          const BigInt x2 = dbC1.get_affine_x();
          const BigInt y2 = dbC1.get_affine_y();
diff --git a/src/tests/unit_ecc.cpp b/src/tests/unit_ecc.cpp
index 6f0d1a243..cbff3ff4f 100644
--- a/src/tests/unit_ecc.cpp
+++ b/src/tests/unit_ecc.cpp
@@ -136,10 +136,6 @@ std::vector<Test::Result> ECC_Randomized_Tests::run()
          const size_t trials = (Test::run_long_tests() ? 10 : 3);
          for(size_t i = 0; i < trials; ++i)
             {
-            const size_t w = 1 + (Test::rng().next_byte() % 8);
-
-            Botan::PointGFp_Blinded_Multiplier blinded(base_point, w);
-
             const Botan::BigInt a = Botan::BigInt::random_integer(Test::rng(), 2, group_order);
             const Botan::BigInt b = Botan::BigInt::random_integer(Test::rng(), 2, group_order);
             const Botan::BigInt c = a + b;
@@ -148,13 +144,18 @@ std::vector<Test::Result> ECC_Randomized_Tests::run()
             const Botan::PointGFp Q = base_point * b;
             const Botan::PointGFp R = base_point * c;
 
-            const Botan::PointGFp P1 = blinded.mul(a, group_order, Test::rng(), blind_ws);
-            const Botan::PointGFp Q1 = blinded.mul(b, group_order, Test::rng(), blind_ws);
-            const Botan::PointGFp R1 = blinded.mul(c, group_order, Test::rng(), blind_ws);
+            Botan::PointGFp P1 = group.blinded_base_point_multiply(a, Test::rng(), blind_ws);
+            Botan::PointGFp Q1 = group.blinded_base_point_multiply(b, Test::rng(), blind_ws);
+            Botan::PointGFp R1 = group.blinded_base_point_multiply(c, Test::rng(), blind_ws);
+
+            Botan::PointGFp A1 = P + Q;
+            Botan::PointGFp A2 = Q + P;
 
-            const Botan::PointGFp A1 = P + Q;
-            const Botan::PointGFp A2 = Q + P;
+            result.test_eq("p + q", A1, R);
+            result.test_eq("q + p", A2, R);
 
+            A1.force_affine();
+            A2.force_affine();
             result.test_eq("p + q", A1, R);
             result.test_eq("q + p", A2, R);
 
@@ -165,6 +166,13 @@ std::vector<Test::Result> ECC_Randomized_Tests::run()
             result.test_eq("P1", P1, P);
             result.test_eq("Q1", Q1, Q);
             result.test_eq("R1", R1, R);
+
+            P1.force_affine();
+            Q1.force_affine();
+            R1.force_affine();
+            result.test_eq("P1", P1, P);
+            result.test_eq("Q1", Q1, Q);
+            result.test_eq("R1", R1, R);
             }
          }
       catch(std::exception& e)