2048-bit RSA keys

[Samuel Neves]

 On 17-08-2010 21:42, Perry E. Metzger wrote:
> On Tue, 17 Aug 2010 22:32:52 +0200 Simon Josefsson
> <simon at josefsson.org> wrote:
>> Bill Stewart <bill.stewart at 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 majordomo at metzdowd.com