Merge GH #1538 Minor ECC optimizations

8 files changed, 137 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,
diff --git a/src/tests/data/pubkey/ecdh.vec b/src/tests/data/pubkey/ecdh.vec
index 085041b1a..336fd0acb 100644
--- a/src/tests/data/pubkey/ecdh.vec
+++ b/src/tests/data/pubkey/ecdh.vec
@@ -607,3 +607,35 @@ K = c026b625989f1c31e9330792ca6a9fd11896938ade31a91d38ab0457d911eeaa
 Secret = 0x85a268f9d7772f990c36b42b0a331adc92b5941de0b862d5d89a347cbf8faab0
 CounterKey = 04AE597AD61FF4489367D4BD4132CCFD738E53C347AA463FFB5EA193713612530CBDAF81342A5ABF8B9A62CA88D52C5B6F6873678B6FEB0B991C2E16E32FDEB141
 K = 19ee841c07e4874d727e4d56a664cbc0af6238ca49fd54f567c9829299b8dbff
+
+# From RFC 7027
+
+[brainpool256r1]
+
+Secret = 0x81DB1EE100150FF2EA338D708271BE38300CB54241D79950F77B063039804F1D
+CounterKey = 048D2D688C6CF93E1160AD04CC4429117DC2C41825E1E9FCA0ADDD34E6F1B39F7B990C57520812BE512641E47034832106BC7D3E8DD0E4C7F1136D7006547CEC6A
+K = 89AFC39D41D3B327814B80940B042590F96556EC91E6AE7939BCE31F3A18BF2B
+
+Secret = 0x55E40BC41E37E3E2AD25C3C6654511FFA8474A91A0032087593852D3E7D76BD3
+CounterKey = 0444106E913F92BC02A1705D9953A8414DB95E1AAA49E81D9E85F929A8E3100BE58AB4846F11CACCB73CE49CBDD120F5A900A69FD32C272223F789EF10EB089BDC
+K = 89AFC39D41D3B327814B80940B042590F96556EC91E6AE7939BCE31F3A18BF2B
+
+[brainpool384r1]
+
+Secret = 0x1E20F5E048A5886F1F157C74E91BDE2B98C8B52D58E5003D57053FC4B0BD65D6F15EB5D1EE1610DF870795143627D042
+CounterKey = 044D44326F269A597A5B58BBA565DA5556ED7FD9A8A9EB76C25F46DB69D19DC8CE6AD18E404B15738B2086DF37E71D1EB462D692136DE56CBE93BF5FA3188EF58BC8A3A0EC6C1E151A21038A42E9185329B5B275903D192F8D4E1F32FE9CC78C48
+K = 0BD9D3A7EA0B3D519D09D8E48D0785FB744A6B355E6304BC51C229FBBCE239BBADF6403715C35D4FB2A5444F575D4F42
+
+Secret = 0x032640BC6003C59260F7250C3DB58CE647F98E1260ACCE4ACDA3DD869F74E01F8BA5E0324309DB6A9831497ABAC96670
+CounterKey = 0468B665DD91C195800650CDD363C625F4E742E8134667B767B1B476793588F885AB698C852D4A6E77A252D6380FCAF06855BC91A39C9EC01DEE36017B7D673A931236D2F1F5C83942D049E3FA20607493E0D038FF2FD30C2AB67D15C85F7FAA59
+K = 0BD9D3A7EA0B3D519D09D8E48D0785FB744A6B355E6304BC51C229FBBCE239BBADF6403715C35D4FB2A5444F575D4F42
+
+[brainpool512r1]
+
+Secret = 0x16302FF0DBBB5A8D733DAB7141C1B45ACBC8715939677F6A56850A38BD87BD59B09E80279609FF333EB9D4C061231FB26F92EEB04982A5F1D1764CAD57665422
+CounterKey = 049D45F66DE5D67E2E6DB6E93A59CE0BB48106097FF78A081DE781CDB31FCE8CCBAAEA8DD4320C4119F1E9CD437A2EAB3731FA9668AB268D871DEDA55A5473199F2FDC313095BCDD5FB3A91636F07A959C8E86B5636A1E930E8396049CB481961D365CC11453A06C719835475B12CB52FC3C383BCE35E27EF194512B71876285FA
+K = A7927098655F1F9976FA50A9D566865DC530331846381C87256BAF3226244B76D36403C024D7BBF0AA0803EAFF405D3D24F11A9B5C0BEF679FE1454B21C4CD1F
+
+Secret = 0x230E18E1BCC88A362FA54E4EA3902009292F7F8033624FD471B5D8ACE49D12CFABBC19963DAB8E2F1EBA00BFFB29E4D72D13F2224562F405CB80503666B25429
+CounterKey = 040A420517E406AAC0ACDCE90FCD71487718D3B953EFD7FBEC5F7F27E28C6149999397E91E029E06457DB2D3E640668B392C2A7E737A7F0BF04436D11640FD09FD72E6882E8DB28AAD36237CD25D580DB23783961C8DC52DFA2EC138AD472A0FCEF3887CF62B623B2A87DE5C588301EA3E5FC269B373B60724F5E82A6AD147FDE7
+K = A7927098655F1F9976FA50A9D566865DC530331846381C87256BAF3226244B76D36403C024D7BBF0AA0803EAFF405D3D24F11A9B5C0BEF679FE1454B21C4CD1F