aboutsummaryrefslogtreecommitdiffstats
path: root/src/math/ec_gfp
diff options
context:
space:
mode:
authorlloyd <[email protected]>2011-06-01 14:34:37 +0000
committerlloyd <[email protected]>2011-06-01 14:34:37 +0000
commit917aa9a47695e2b94d5693ffeb6170e8477ee43d (patch)
treec71f5cd27ee430f12cf8ab3f310e9c2bc1870834 /src/math/ec_gfp
parent7b10642990382932af4639186057b81f5de87605 (diff)
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.
Diffstat (limited to 'src/math/ec_gfp')
-rw-r--r--src/math/ec_gfp/point_gfp.cpp33
-rw-r--r--src/math/ec_gfp/point_gfp.h12
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
*/