2048-bit RSA keys

[Steven Bellovin]

On Aug 17, 2010, at 5:19 10PM, Samuel Neves wrote:

> On 17-08-2010 21:42, Perry E. Metzger wrote:
>> On Tue, 17 Aug 2010 22:32:52 +0200 Simon Josefsson
>> <simon at josefsson.org> wrote:
>>> Bill Stewart <bill.stewart at pobox.com> writes:
>>> 
>>>> Basically, 2048's safe with current hardware
>>>> until we get some radical breakthrough
>>>> like P==NP or useful quantum computers,
>>>> and if we develop hardware radical enough to
>>>> use a significant fraction of the solar output,
>>>> we'll probably find it much easier to eavesdrop
>>>> on the computers we're trying to attack than to
>>>> crack the crypto.
>>> Another breakthrough in integer factoring could be sufficient for an
>>> attack on RSA-2048.  Given the number of increasingly efficient
>>> integer factorization algorithms that have been discovered
>>> throughout history, another breakthrough here seems more natural
>>> than unlikely to me.
>> A breakthrough could also render 10kbit keys broken, or might never
>> happen at all. A breakthrough could make short ECC keys vulnerable.
>> A breakthrough could make AES vulnerable. One can't operate on this
>> basis -- it makes it impossible to use anything other than one-time
>> pads.
>> 
> 
> A breakthrough is a rather strong term. But it's not unreasonable to
> believe that the number field sieve's complexity could be lowered on the
> near future by an *incremental* improvement --- it would only require
> lowering the complexity from L[1/3, ~1.92] to L[1/3, ~1.2] to make 2048
> bit factorization roughly as easy as 768 bits today.

It's worth quote from the paper at CRYPTO '10 on factorization of a 768-bit number:

	The new NFS record required the following effort. We spent half a year on
	80 processors on polynomial selection. This was about 3% of the main task,
	the sieving, which took almost two years on many hundreds of machines. On
	a single core 2.2 GHz AMD Opteron processor with 2 GB RAM, sieving would
	have taken about fifteen hundred years. We did about twice the sieving
	strictly necessary, to make the most cumbersome step, the matrix step, more
	manageable. Preparing the sieving data for the matrix step took a couple of
	weeks on a few processors. The final step after the matrix step took less
	than half a day of computing.

They conclude with

	at this point factoring a 1024-bit RSA modulus looks more than five times
	easier than a 768-bit RSA modulus looked back in 1999, when we achieved
	the first public factorization of a 512-bit RSA modulus. Nevertheless, a
	1024-bit RSA modulus is still about a thousand times harder to factor than
	a 768-bit one. It may be possible to factor a 1024-bit RSA modulus within
	the next decade by means of an academic effort on the same scale as the
	effort presented here. Recent standards recommend phasing out such moduli
	by the end of the year 2010 [28]. See also [21]. Another conclusion from
	our work is that we can confidently say that if we restrict ourselves to
	an open community, academic effort such as ours and unless something
	dramatic happens in factoring, we will not be able to factor a 1024-bit
	RSA modulus within the next five years [27]. After that, all bets are off.

They also suggest that a 3-4 year phase-out of 1024-bit moduli is the proper course.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com