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.

2 files changed, 45 insertions, 0 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
       */