<<

. 2
( 2 .)



expected to factor a 512-bit modulus in under eight months. With a $lO,OOO,OOO
investment in 1996, it might take around five weeks. While such an investment
is perhaps out of proportion to the value of the data protected using a 512-bit
modulus, the investment can be recovered by factoring other numbers. And,
as we have repeatedly stressed, we have taken no account of future algorithm
improvements. It is not inconceivable that by the turn of the century, a viable
*This would make the effort required to factor a 512-bit number around lo4 MY.




5
Previous Page Home Next Page




business could be established that is dedicated to factoring 512-bit numbers,
assuming there is a market for such an enterprise.
The power of the well positioned adversary should demand the utmost at-
tention. As we have shown, the computing power already possessed in 1995 by
large companies3, could be harnessed to factor 512-bit numbers in a matter of
months.
Perhaps less significant is the short-term risk posed by overt networked fac-
toring efforts. Since 512-bit keys should not be used to secure any valuable
information it is unlikely that nearly a thousand people could be persuaded to
donate spare cycles to factor a 512-bit RSA number in a year. (Within a few
years we might assume that the novelty of factoring 512-bit numbers has worn
off.) However, networked attacks are an important consideration for certifica-
tion hierarchy root-keys which are high-profile targets. Clearly, the moduli for
such valuable data should be chosen to be well out of reach of even the most
committed efforts.
With the current information we have, it might be reasonably argued that
with regards to the installed base of 512-bit RSA, it will still be moderately
expensive to attack any individual key over the next two or three years. In-
deed, if improvements to the speed of computation provide the only advances in
factoring ability in the near future, then the figures in this note might be used
to give a rough idea of the increasing risk incurred by the continued use of a
512-bit RSA key.
It cannot be sufficiently stressed however, that any new advances in the
performance of factoring algorithms will, in all likelihood, have catastrophic
implications for the security offered by 512-bit RSA numbers.
Predictions for larger RSA moduli are notoriously difficult to make; new
developments often overtake old predictions. However, recent estimates [3] put
the computational effort required to factor a 768-bit RSA modulus, using the
current techniques that threaten 512-bit RSA, at 2 x 10™ MY and to factor
a 1024-bit RSA modulus, at 3 x 10l1 MY. These contrast with the 3 x lo4
MY estimated to attack a 512-bit modulus and they clearly offer a much more
acceptable level of security.
For many years now, 512-bit RSA has been adequate for a great number of
applications. At present however, even without further advances in factoring
techniques, 512-bit RSA can only be considered as offering moderate, short-term
security.
The first conclusion to draw from this note is that systems implementing
RSA should support a variable key size. While it is easy to account for im-
provements in computational performance, one should also allow for unforeseen
developments in factoring ability when choosing the size of an RSA modulus.
And perhaps most importantly, it is clear that factoring 512-bit RSA moduli
30dlyzko estimates that Silicon Graphics has around 10,000 workstations which could each
contribute 10 MIPS.



6
Previous Page Home Next Page




is soon going to be moderately routine. With this in mind, users are advised
to begin phasing out the use of 512-bit RSA as soon as possible. Depending
on the particular security requirements, and assuming that there are no new
developments in factoring ability, some users might prefer to continue using
512-bit RSA moduli for moderate to low security applications. Even for this
use, however, it seems prudent to recommend that 512-bit RSA moduli should
not be used after 1997 or 1998 at the latest.


References
[l] D. Atkins, M. Graff, A.J. Lenstra, and P.C. Leyland. The magic words are
squeamish ossifrage. In J. Pieprzyk and R. Safavi-Naini, editors, Advances in
Cryptology - Asiacrypt ˜94, pages 263-277, Springer-Verlag, Berlin, 1995.
[2] J.P. Buhler, H.W. Lenstra, and C. Pomerance. Factoring integers with the
number field sieve. 1992. To appear.
[3] A. Odlyzko. The future of integer factorization.4 CryptoBytes, l(2), Summer
1995. To appear.
[4] R.L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital
signatures and public-key cryptosystems. Communications of the ACM,
21(2):120-126, February 1978.




4Al˜˜ available by sending the message futw-e.of.factoring.ps from att/math/odlyzko to
netlibOresearch.att.com.


7

<<

. 2
( 2 .)