Multi-expoentiation, using the single bit variation. Using a 2 or 3

bit window may well improve things further. Currently seeing 20-25%
improvement in ECDSA signature verification and 25 to 40% in
GOST-34.10 verifications.

4 files changed, 49 insertions, 2 deletions

diff --git a/src/math/ec_gfp/point_gfp.cpp b/src/math/ec_gfp/point_gfp.cpp
index 04805010d..0bfff7d46 100644
--- a/src/math/ec_gfp/point_gfp.cpp
+++ b/src/math/ec_gfp/point_gfp.cpp
@@ -268,6 +268,39 @@ PointGFp& PointGFp::operator*=(const BigInt& scalar)
    return *this;
    }
 
+PointGFp multi_exponentiate(const PointGFp& p1, const BigInt& z1,
+                            const PointGFp& p2, const BigInt& z2)
+   {
+   const PointGFp p3 = p1 + p2;
+
+   PointGFp H(p1.curve); // create as zero
+   size_t bits_left = std::max(z1.bits(), z2.bits());
+
+   std::vector<BigInt> ws(11);
+
+   while(bits_left)
+      {
+      H.mult2(ws);
+
+      const bool z1_b = z1.get_bit(bits_left - 1);
+      const bool z2_b = z2.get_bit(bits_left - 1);
+
+      if(z1_b == true && z2_b == true)
+         H.add(p3, ws);
+      else if(z1_b)
+         H.add(p1, ws);
+      else if(z2_b)
+         H.add(p2, ws);
+
+      --bits_left;
+      }
+
+   if(z1.is_negative() != z2.is_negative())
+      H.negate();
+
+   return H;
+   }
+
 PointGFp operator*(const BigInt& scalar, const PointGFp& point)
    {
    const CurveGFp& curve = point.get_curve();
diff --git a/src/math/ec_gfp/point_gfp.h b/src/math/ec_gfp/point_gfp.h
index 8c279dbd1..b2b6fe2f0 100644
--- a/src/math/ec_gfp/point_gfp.h
+++ b/src/math/ec_gfp/point_gfp.h
@@ -99,6 +99,18 @@ class BOTAN_DLL PointGFp
       friend BOTAN_DLL PointGFp operator*(const BigInt& scalar, const PointGFp& point);
 
       /**
+      * Multiexponentiation
+      * @param p1 a point
+      * @param z1 a scalar
+      * @param p2 a point
+      * @param z2 a scalar
+      * @result (p1 * z1 + p2 * z2)
+      */
+      friend BOTAN_DLL PointGFp multi_exponentiate(
+        const PointGFp& p1, const BigInt& z1,
+        const PointGFp& p2, const BigInt& z2);
+
+      /**
       * Negate this point
       * @return *this
       */
diff --git a/src/pubkey/ecdsa/ecdsa.cpp b/src/pubkey/ecdsa/ecdsa.cpp
index 79b4d7f51..5c45c5ed3 100644
--- a/src/pubkey/ecdsa/ecdsa.cpp
+++ b/src/pubkey/ecdsa/ecdsa.cpp
@@ -85,7 +85,8 @@ bool ECDSA_Verification_Operation::verify(const byte msg[], size_t msg_len,
 
    BigInt w = inverse_mod(s, order);
 
-   PointGFp R = w * (e * base_point + r * public_point);
+   PointGFp R = w * multi_exponentiate(base_point, e,
+                                       public_point, r);
 
    if(R.is_zero())
       return false;
diff --git a/src/pubkey/gost_3410/gost_3410.cpp b/src/pubkey/gost_3410/gost_3410.cpp
index 100986ccd..f97f83aa0 100644
--- a/src/pubkey/gost_3410/gost_3410.cpp
+++ b/src/pubkey/gost_3410/gost_3410.cpp
@@ -165,7 +165,8 @@ bool GOST_3410_Verification_Operation::verify(const byte msg[], size_t msg_len,
    BigInt z1 = (s*v) % order;
    BigInt z2 = (-r*v) % order;
 
-   PointGFp R = (z1 * base_point + z2 * public_point);
+   PointGFp R = multi_exponentiate(base_point, z1,
+                                   public_point, z2);
 
    if(R.is_zero())
      return false;