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