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
>> <si...@josefsson.org> wrote:
>>> Bill Stewart <bill.stew...@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 majord...@metzdowd.com
