[145308] in cryptography@c2.net mail archive
Re: 1280-Bit RSA
daemon@ATHENA.MIT.EDU (Brandon Enright)
Sat Jul 10 20:46:48 2010
Date: Sun, 11 Jul 2010 00:11:15 +0000
From: Brandon Enright <bmenrigh@ucsd.edu>
To: Jonathan Thornburg <jthorn@astro.indiana.edu>
Cc: Dan Kaminsky <dan@doxpara.com>, cryptography@metzdowd.com,
bmenrigh@ucsd.edu
In-Reply-To: <alpine.BSO.2.00.1007092102090.6211@oxygen.astro.indiana.edu>
On Fri, 9 Jul 2010 21:16:30 -0400 (EDT)
Jonathan Thornburg <jthorn@astro.indiana.edu> wrote:
> The following usenet posting from 1993 provides an interesting bit
> (no pun itended) of history on RSA key sizes. The key passage is the
> last paragraph, asserting that 1024-bit keys should be ok (safe from
> key-factoring attacks) for "a few decades". We're currently just
> under 1.75 decades on from that message. I think the take-home lesson
> is that forecasting progress in factoring is hard, so it's useful to
> add a safety margin...
This is quite interesting. The post doesn't say but I suspect at the
factoring effort was based on using Quadratic Sieve rather than GNFS.
The difference in speed for QS versus GNFS starts to really diverge with
larger composites. Here's another table:
RSA GNFS QS
===========================
256 43.68 43.73
384 52.58 55.62
512 59.84 65.86
664 67.17 76.64
768 71.62 83.40
1024 81.22 98.48
1280 89.46 111.96
1536 96.76 124.28
2048 109.41 146.44
3072 129.86 184.29
4096 146.49 216.76
8192 195.14 319.63
16384 258.83 469.80
32768 342.05 688.62
Clearly starting at key sizes of 1024 and greater GNFS starts to really
improve over QS. If the 1993 estimate for RSA 1024 was assuming QS
then that was roughly equivalent to RSA 1536 today. Even improving the
GNFS constant from 1.8 to 1.6 cuts off the equivalent of about 256 bits
from the modulus.
The only certainty in factoring techniques is that they won't get worse
than what we have today.
Brandon
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
