diff options
author | lloyd <[email protected]> | 2011-06-01 14:34:37 +0000 |
---|---|---|
committer | lloyd <[email protected]> | 2011-06-01 14:34:37 +0000 |
commit | 917aa9a47695e2b94d5693ffeb6170e8477ee43d (patch) | |
tree | c71f5cd27ee430f12cf8ab3f310e9c2bc1870834 /src/math/ec_gfp | |
parent | 7b10642990382932af4639186057b81f5de87605 (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.cpp | 33 | ||||
-rw-r--r-- | src/math/ec_gfp/point_gfp.h | 12 |
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 */ |