On 11-07-2010 01:11, Brandon Enright wrote: > On Fri, 9 Jul 2010 21:16:30 -0400 (EDT) > Jonathan Thornburg <jth...@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 majord...@metzdowd.com >

The exponent can be further lowered from that (somewhere between 1.6 and 1.7) --- RSA-768 took about 2^67 Opteron instructions to complete, and RSA-512 can be done in about 2^54 similar operations (it is in the realm of possibility for a single box over a few days/weeks). Best regards, Samuel Neves --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com