[prev in list] [next in list] [prev in thread] [next in thread] 

List:       full-disclosure
Subject:    Re: [Full-disclosure] nonsense fun: 100 000 bit rsa key
From:       Jeffrey Walton <noloader () gmail ! com>
Date:       2010-08-30 0:39:11
Message-ID: AANLkTinJ0qTBz0GHEe0ker2W8ztvk1zWATpbh0dB8==7 () mail ! gmail ! com
[Download RAW message or body]

> 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@guninski.com> 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/


[prev in list] [next in list] [prev in thread] [next in thread]