aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorlloyd <[email protected]>2015-03-12 11:14:44 +0000
committerlloyd <[email protected]>2015-03-12 11:14:44 +0000
commit857fc0f160e5359f5894bf3a5640cdd168b095be (patch)
tree5f97d0517d9e786e888493e8495cd210256bd785
parenta4b75876eb2ae8b9b1edeea1927a6ad0da1dad88 (diff)
Avoid a ECC point multiplication in ECDSA signature verification by
distributing w into the exponents. This is at least a 50% speedup across all keysizes on my laptop. Optimization pointed out by Dr. Falko Strenzke on the mailing list.
-rw-r--r--src/lib/pubkey/ecdsa/ecdsa.cpp34
1 files changed, 20 insertions, 14 deletions
diff --git a/src/lib/pubkey/ecdsa/ecdsa.cpp b/src/lib/pubkey/ecdsa/ecdsa.cpp
index 6b8e5fa67..d2ad82b94 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.cpp
+++ b/src/lib/pubkey/ecdsa/ecdsa.cpp
@@ -93,30 +93,34 @@ class ECDSA_Verification_Operation : public PK_Ops::Verification
typedef ECDSA_PublicKey Key_Type;
ECDSA_Verification_Operation(const ECDSA_PublicKey& ecdsa,
const std::string&) :
- base_point(ecdsa.domain().get_base_point()),
- public_point(ecdsa.public_point()),
- order(ecdsa.domain().get_order())
+ m_base_point(ecdsa.domain().get_base_point()),
+ m_public_point(ecdsa.public_point()),
+ m_order(ecdsa.domain().get_order()),
+ m_mod_order(m_order)
{
+ //m_public_point.precompute_multiples();
}
size_t message_parts() const { return 2; }
- size_t message_part_size() const { return order.bytes(); }
- size_t max_input_bits() const { return order.bits(); }
+ size_t message_part_size() const { return m_order.bytes(); }
+ size_t max_input_bits() const { return m_order.bits(); }
bool with_recovery() const { return false; }
bool verify(const byte msg[], size_t msg_len,
const byte sig[], size_t sig_len);
private:
- const PointGFp& base_point;
- const PointGFp& public_point;
- const BigInt& order;
+ const PointGFp& m_base_point;
+ const PointGFp& m_public_point;
+ const BigInt& m_order;
+ // FIXME: should be offered by curve
+ Modular_Reducer m_mod_order;
};
bool ECDSA_Verification_Operation::verify(const byte msg[], size_t msg_len,
const byte sig[], size_t sig_len)
{
- if(sig_len != order.bytes()*2)
+ if(sig_len != m_order.bytes()*2)
return false;
BigInt e(msg, msg_len);
@@ -124,18 +128,20 @@ bool ECDSA_Verification_Operation::verify(const byte msg[], size_t msg_len,
BigInt r(sig, sig_len / 2);
BigInt s(sig + sig_len / 2, sig_len / 2);
- if(r <= 0 || r >= order || s <= 0 || s >= order)
+ if(r <= 0 || r >= m_order || s <= 0 || s >= m_order)
return false;
- BigInt w = inverse_mod(s, order);
+ BigInt w = inverse_mod(s, m_order);
- PointGFp R = w * multi_exponentiate(base_point, e,
- public_point, r);
+ const BigInt u1 = m_mod_order.reduce(e * w);
+ const BigInt u2 = m_mod_order.reduce(r * w);
+ const PointGFp R = multi_exponentiate(m_base_point, u1, m_public_point, u2);
if(R.is_zero())
return false;
- return (R.get_affine_x() % order == r);
+ const BigInt v = m_mod_order.reduce(R.get_affine_x());
+ return (v == r);
}
BOTAN_REGISTER_PK_SIGNATURE_OP("ECDSA", ECDSA_Signature_Operation);