[145692] in cryptography@c2.net mail archive
Re: 2048-bit RSA keys
daemon@ATHENA.MIT.EDU (Steven Bellovin)
Tue Aug 17 19:51:47 2010
From: Steven Bellovin <smb@cs.columbia.edu>
In-Reply-To: <4C6AFCCE.5010703@dei.uc.pt>
Date: Tue, 17 Aug 2010 18:24:20 -0400
Cc: cryptography@metzdowd.com
To: Samuel Neves <sneves@dei.uc.pt>
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@josefsson.org> wrote:
>>> Bill Stewart <bill.stewart@pobox.com> writes:
>>>=20
>>>> Basically, 2048's safe with current hardware
>>>> until we get some radical breakthrough
>>>> like P=3D=3DNP 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.
>>=20
>=20
> 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@metzdowd.com
