Re: [Full-disclosure] nonsense fun: 100 000 bit rsa key



out of boredom i generated two 100K bit rsa key in about 30 hours on
1 core (i would be interested how long it will take generating it on openssl.
Or is it morbid curiosity (it motivated me as I've never gone above 15360)....

the first key is with public exponent e=2^16-1...
Crypto++ uses e=17.

a wild guess is *at least week* if not using sophie-germain
primes, otherwise much longer).
You also might consider making the bit length a power of 2 to take
advantage of any available optimizations.

Key | Sign | Verify
key2 | 48min | 21min
Shooting from the hip, it looks like you need a larger sample size
(assuming the weights of the second key's exponents are about equal).

Crypto++ RSA key generation stats (Core 2 Duo T6500 at 2.1 GHz with
plenty of memory. The EXE was built with -DNDEBUG and then strip'd.):

512 bit: 0.02 seconds
1024 bit: 0.02 seconds
2048 bit: 0.14 seconds
4096 bit: 0.81 seconds
8192 bit: 25.87 seconds
15360 bit: 4 minutes, 11.17 seconds
30720 bit: 43 minutes, 42.57 seconds
61440 bit: 11 hours, 21 minutes, 34.52 seconds
122880 bit: no dice

I'm not bitting on 100000 (its linear when plotted using logarithmic
scales). But it is impressive that you were able to generate two keys
in under 30 hours.

Jeff

On Sat, Aug 28, 2010 at 5:38 AM, Georgi Guninski <guninski@xxxxxxxxxxxx> wrote
nonsense fun: 100 000 bit rsa key

out of boredom i generated two 100K bit rsa key in about 30 hours on 1 core (i would be interested how long it will take generating it on openssl. a wild guess is *at least week* if not using sophie-germain primes, otherwise much longer).

the first key is with public exponent e=2^16-1, the second is with with 100Kbit e and d, the modulus is the same for both keys.

stats:
    sign   verify
key1  5min   <1sec
key2 48min   21min
(tested on patched openssl1.0.0a)

attached are two certs + the keys, openssl needs recompilation with increased limits.


_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/



Relevant Pages