2048-bit RSA keys

[Samuel Neves]

 Forwarded at Andrew's request.

-------- Original Message --------
Subject:     Re: 2048-bit RSA keys
Date:     Tue, 17 Aug 2010 19:11:55 -0500 (CDT)
From:     Andrew Odlyzko <odlyzko at umn.edu>
To:     Samuel Neves <sneves at dei.uc.pt>
CC:     cryptography at metzdowd.com


It is not unreasonable to consider the possibility of
algorithmic improvements.  But that does not guarantee
accuracy.

My 1995 paper "The future of integer factorization,"

    http://www.dtc.umn.edu/~odlyzko/doc/future.of.factoring.pdf

published in CryptoBytes (The technical newsletter of RSA
Laboratories), vol. 1, no. 2, 1995, pp. 5-12, considered
the historical record of integer factorizations up to that
point, and took account both of the increasing computing
power and the progress in algorithms (which over the preceding
20 years contributed about as much as the growth in the
number of available cycles).  It then projected when
integers of various sizes might get factored, and even
the most conservative projection had 768-bit integers
getting factored by 2004 or so.

In retrospect, the latest 768-bit factorization shows that
over the preceding 15 years there has been practically no
progress in algorithms, and even the computing power that
is actually used for the experiments has fallen behind
projections.

Andrew

On Tue, 17 Aug 2010, Samuel Neves wrote:

> 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
>

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com