1280-Bit RSA

[Samuel Neves]

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