full-disclosure - Re: nonsense fun: 100 000 bit rsa key

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date: Sun, 29 Aug 2010 20:39:11 -0400
From: Jeffrey Walton <noloader@...il.com>
To: Georgi Guninski <guninski@...inski.com>
Cc: full-disclosure@...ts.grok.org.uk
Subject: Re: 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@...inski.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/