Hi,
The big difference in the sign operation timings between the two keys is
not caused by any property of the second key parameters (like their
hamming weight) but it is rather the expected manifestation of two
counter-measures implemented by OpenSSL. Those are :
- RSA Blinding that protects against timing attacks.
- Verification of CRT output that protects against fault attacks.
Each of these counter-measures involves a modular exponentiation by the
public exponent e.
When the public exponent e is equal to 2^16-1, then the cost of these
two counter-measures is negligible.
When e is big (in your case the same size as the modulus), then these
counter-measures add an overhead that is equal to twice the cost of an
RSA verification.
In your case, for the second key, this overhead is expected to be equal
to 2x21 min = 42 min. The cost of a pure CRT signature without
counter-measures is roughly 5 min (taken from CRT of key1 for whom
counter-measures are negligible).
This gives us an expected running time for a signature with key2 of 42 +
5 = 47 min, that is very close to what you actually obtained.
You can deactivate the blinding counter-measure by calling the function
RSA_blinding_off. On the other hand, CRT output verification
counter-measure can't be deactivated.
I hope this clarifies the behavior you have encountered.
Cheers,
--
Mounir IDRASSI
IDRIX
http://www.idrix.fr
On 8/29/2010 10:51 AM, Georgi Guninski wrote:
inconsistent timings for rsa sign/verify with 100K bit rsa keys.
using pycrypto i generated two valid 100 000 bit rsa keys with the same modulus:
key1: log(n)=100K, e=2^16-1,d=BIG
key2: log(n)=100K, e=BIG, d=BIG
(note key1 and key2 share the same modulus)
recompiled openssl with increased parameters so the keys are usable.
i expect the keys to be slow, but this benchmarks quite surprise me:
sign verify
key1 5min<1sec
key2 48min 21min
(tested on patched openssl1.0.0a)
is it normal key2 to be so slower compared with the signing of key1 (the 1sec
verification with low exponent is clear to me).
signature verification passes for both keys and the big exponents seem of the right
size. both keys passed "rsa check" with reduced number of pseudoprimality tests
(to 3).
pycrypto is much faster with key2 and general purpose math program suggest
sign/verify to be about 5min for big exponents (<phi(n)).
the tarball with the private keys + 2 certs (190K) is at:
http://seclists.org/fulldisclosure/2010/Aug/384
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [email protected]
Automated List Manager [email protected]
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [email protected]
Automated List Manager [email protected]
