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