Long thought nearly unbreakable, public-key cryptography is yielding to attack. The secret of security here is key length.
Bruce Schneier
Factoring large numbers is hard but not as hard as it used to be. This has grave implications for the effectiveness of public-key cryptography, which relies on the difficulty of factoring long keys for its security. But how long is long enough?
In 1976, Richard Guy wrote: "I shall be surprised if anyone regularly factors numbers of size 10(80) without special form during the present century." In 1977, Ron Rivest said that factoring a 125-digit number would take 40 quadrillion years. In 1994, a 129-digit number was factored. T
he lesson here is that making predictions is foolish.
Today, 512-bit keys are common. Factoring them, thus destroying their security, is well within the range of possibility for today's computing resources. A weekend-long worm on the Internet could do it.
Computing power is measured in MIPS-years: a million-instructions-per-second computer running for one year, or about 3 x 10(13) instructions. A 100-MHz Pentiu3m is about a 50-MIPS machine; a 1600-node Intel Paragon is about 50,000 MIPS.
In 1983, a Cray X-MP supercomputer factored a 71-digit number in 0.1 MIPS-years, using 9.5 CPU hours. That's expensive. Factoring the 129-digit number in 1994 required 5000 MIPS-years and used the idle time on 1600 computers around the world over an eight-month period. Although it took longer, it was essentially free.
Those two computations used what's called the
quadratic sieve
, but a newer, more powerful algorithm has arrived. The
general number field sieve
is faster than the quadra
tic sieve for numbers well below 116 digits and can factor a 512-bit number over 10 times faster -- it would take less than a year to run on an 1800-node Intel Paragon.
And the process gets still faster. Mathematicians keep coming up with new tricks, new optimizations, and new techniques. A related algorithm, the
special number field sieve
, can already factor numbers of a specialized form (not generally used for cryptography) much faster. So we can probably optimize the general number field sieve to run that fast. For all we know, the National Security Agency is already doing it.
The figure
"MIPS Years Needed to Factor"
gives the number of MIPS-years required to factor "special" and "general" numbers of different lengths.
How Big Is Big Enough?
The wise cryptographer is ultraconservative when choosing key lengths for a public-key system. You must consider the intended security, the key's expected lifetime, and the current state of the
factoring art. Now you need a 1024-bit number to get the same security you got from a 512-bit number in the early 1980s. If you want your keys to remain secure for 20 years, 1024 bits is probably too short.
Consider these assumptions from the mathematicians who factored RSA-129: We believe we could acquire 100,000 machines without superhuman or unethical efforts and without an Internet worm or virus. Many organizations have several thousand machines on the Net. Using their facilities would require diplomacy but should not be impossible. Assuming an average power of 5 MIPS and one year elapsed time, we could reasonably embark on a project that would require half a million MIPS-years. The project to factor the 129-digit number harnessed an estimated 0.03 percent of the Internet's total computing power. A well-publicized project might be able to harness 2 percent of the world's computing power for a year.
My recommendations for public-key lengths are given in the figure
"Recommend
ed Public-Key Key Lengths"
according to how long you require the key to be secure. There are three key lengths given for each period -- one secure against an individual cryptanalyst who can get his hands on 10,000 MIPS-years, one against a major corporation that could harness 10(7) MIPS-years, and the third secure against a major government and 10(9) MIPS-years. These figures assume that computing power will increase by a factor of 10 every five years and that mathematical advances will let us factor numbers at the speeds of the special number field sieve.
Not everyone will agree with these final recommendations. The National Institute of Standards and Technology has mandated 512- to 1024-bit keys for its Digital Signature Standard. PGP has a maximum RSA key length of 1280 bits. Arjen Lenstra, the world's most successful factorer, refuses to predict beyond 10 years. There's always the possibility that an advance in factoring will surprise me as well, though I tried to factor everything into my calcu
lations. But why trust me? I just proved my own foolishness by making predictions.
illustration_link (11 Kbytes)
illustration_link (9 Kbytes)
Bruce Schneier is the author of
Applied Cryptog
raphy
(John Wiley), the second edition of which is due out in December. He can be reached on the Internet as
schneier@winternet.com
, or on BIX c/o
editors@bix.com
.
Factoring in Public-Key's Future
