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 

        The new NFS record required the following effort. We spent half a year 
        80 processors on polynomial selection. This was about 3% of the main 
        the sieving, which took almost two years on many hundreds of machines. 
        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, 
        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 
        than half a day of computing.

They conclude with

        at this point factoring a 1024-bit RSA modulus looks more than five 
        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 
        a 768-bit one. It may be possible to factor a 1024-bit RSA modulus 
        the next decade by means of an academic effort on the same scale as the
        effort presented here. Recent standards recommend phasing out such 
        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 

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

Reply via email to