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. Coppersmith's variant of the number field sieve proposed a tradeoff that dramatically lowered the exponent, if one wanted to break many keys of roughly the same size. The idea was to fix m, the 'base' of the number field polynomial, and precompute many many pairs (a,b) such that a - bm was smooth. With this precomputation, the NFS runs in L[1/3, ~1.639], which is dramatically faster (and quite worth it for a large organization --- they're bound to want to break multiple keys). It is not unreasonable to think that a small(ish) improvement to the number field sieve could significantly lower the strength of current keys. It *looks* more likely to happen than a significant improvement on the speed of ECDLP breaking (I'll make no bets on AES, though). Best regards, Samuel Neves --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com