ñòð. 2 |

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 |