The article below was taken from:
ftp://rsa.com/pub/ciphertext/vol1n1.txt
And is Copyright (C) RSA Data Security Inc.
----------------------------------------------------------------------------
DR. RON RIVEST ON THE DIFFICULTY OF FACTORING
(Since the difficulty of "cracking" the RSA algorithm has long been believed
to be roughly equivalent to the difficulty of factoring a given RSA modulus,
we have decided to reprint one of Ron Rivest's classic papers on the
difficulty of the factoring problem. -Ed.)
Abstract
Here are the results of some simple estimations I have done on the projected
difficulty of factoring various sizes of numbers for the next 25 years.
The basic question is:
"In the year YYYY, what size number will I be able to factor for an investment
of $DDDD?"
To be specific, I've looked at
YYYY= 1990, 1995, 2000, 2005, 2010, 2015
and
$DDDD = $25K, $25M, and $25G
(that is, $25,000, $25,000,000, and $25,000,000,000). The three levels might
correspond to "individual", "corporate", and "national" levels of attack. All
calculations are done in 1990 dollars.
Each of these estimates is also done in an "high," "average," and "low" point
of view. (That is, the high estimates are for the greatest number of digits
possible, while the low estimates are for the least number possible.)
The estimates are done in terms of MIP-years, a computational unit of power
analogous to a "kilowatt-hour" of electricity. Specifically, a MIP-year is the
computational power of a one-MIP machine running for one year. A MIP (more
correctly, a MIPS) is a "million-instruction per second" machine. Today's
workstations run in the 1 to 10 MIPS range, and 100 MIPS machines are under
development. One MIP-year corresponds to 3.15x1013 operations.
Factoring algorithms
To factor a number n with current technology using the best known algorithms,
we need a number of operations roughly equal to
L(n) = exp (_ ln n ln ln n) (1)
(Using, say, the quadratic sieve algorithm.) We use this formula for our "low"
estimates, since this is currently achievable. For our "average" estimate, we
use the formula
A(n) = min (L(n), exp (2.08 (ln n)l/3 (ln ln n)2/3)) (2)
This presupposes that the number field sieve (NFS) can be generalized to
handle ordinary (cryptographic) numbers, as conjectured in the 1990 ACM STOC
article. Finally, for the high estimates, we use the formula
H(n) = exp (1.526 (ln n)l/3 (ln ln n)2/3) (3)
which is the number of operations that NFS now uses for rarefied numbers.
(Achieving this formula would be quite a breakthrough.)
Costs of computation
I estimate that today a MIP-year costs about $10, as follows. You can buy
(parts for) a 10-MIP machine for about $500. With a lifetime of five years,
you get 50 MIP-years out of the machine.
As for rates of technological progress, for the "low" estimate I assume that
technology only advances at 20%/year. For the "average" estimate I assume that
technology advances at 33%/year, and for the "high" estimate I assume
45%/year. These are measured in terms of the drop in the cost of a MIP-year in
constant 1990 dollars. Thus, under the high estimate, $10 will buy 1.45 MIP-
years in 1991 and 2.10 MIP-years in 1992, etc.
At this rate, we can estimate the number of MIP-years that can be bought for
$1 as follows:
Year Low Average High
1990 0.100 0.100 0.100
1995 0.249 0.416 0.641
2000 0.619 1.732 4.109
2005 1.540 7.207 26.340
2010 3.833 30.000 168.800
2015 9,540 124.800 1082.000
2020 23.74 519.500 6935.000
Combining this with our "low" ($25K), "average" ($25M), and "high" ($25G)
estimates for dollars available, we arrive at the following chart for the
number of MIP-years affordable. (Here T is the abbreviation for "tera," i.e.
1012.)
Year Low Average High
1990 2.5K 2.5M 2.5G
1995 6K 10M 16G
2000 15K 43M 103G
2005 38K 180M 658G
2010 96K 750M 4.2T
2015 239K 3.1G 27T
2020 549K 13G 173T
That is, in the year 2020, a determined opponent with $25G might be able to
afford 173 tera MIP-years to attack a number.
Results
We now give the number of operations required to factor numbers of various
sizes under our low, average, and high estimates (formulas (1), (2), and (3)).
These are given in MIP-years.
Digits Low Average High
100 74 74 0.1
150 1M 1M 38
200 4G 4G 4K
250 6T 2T 261K
300 5 x 1015 3 x 1014 10M
350 2 x 1018 2 x 1016 252M
400 9 x 1020 1018 5G
450 2 x 1023 6 x 1019 81G
500 4 x 1025 2 x 1021 1T
Combining the above charts with some additional calculation, we end up with
our low, average, and high estimates for the size of a number (in digits) that
an attacker would be able to factor at various points in time.
Year Low Average High
1990 117 155 388
1995 122 163 421
2000 127 172 455
2005 132 181 490
2010 137 190 528
2015 142 199 567
2020 147 204 607
Conclusions
If one wishes to devise a "standard" based on a 25-year lifetime for an
average attack, then a recommendation of 200 decimal digits (665 bits) seems
justified. A "super-master" key over the same lifetime might well be chosen to
be three times that length (600 decimal digits, or 1994 bits).
- Dr. Ron Rivest