mleone@f.gp.cs.cmu.edu (Mark Leone) (07/17/90)
Here is a followup to the recent discussion on factoring that seems to be making its way around the net: >From: mchinni@PICA.ARMY.MIL ("Michael J. Chinni, SMCAR-CCS-E") >Newsgroups: misc.security >Subject: [Theodore Lee: The F9 factoring result] >Message-ID: <9007170603.AA12748@ucbarpa.Berkeley.EDU> >Date: 2 Jul 90 15:29:15 GMT FYI ... (this is a long message: 155+ lines) Date: Wed, 27 Jun 90 22:19:44 -0400 >From: Theodore Lee <lee@TIS.COM> Subject: The F9 factoring result MESSAGE FROM RON RIVEST VIA JIM BIDZOS VIA STEVE KENT VIA STEVE CROCKER: Thanks to Robert Silverman for keeping many people honest. As an additional effort to that end, I attach an analysis of the recent factoring effort, done by Ron Rivest. The early reports of RSA's demise have been greatly exaggerated... Note: Be sure and read the end of Rivest's note. Jim Bidzos, RSA Data Security To: Whom It May Interest (Feel free to distribute further...) >From: Ronald L. Rivest Date: June 21, 1990 Re: Recent Factoring Achievement (Preliminary draft; may contain typos or other inaccuracies. Please send corrections to rivest@theory.lcs.mit.edu) This note is in response to the numerous inquiries I've received regarding the recent factoring of a 155-digit number by A. Lenstra, M. Manasse, and others. (See the New York Times article of 6/20/1990 by G. Kolata.) This note attempts specifically to correct some of the misimpressions that may arise from a reading of such popular press articles. Using an ingenious new algorithm, Lenstra, Manasse, and others have factored the 155-digit number known as "F9", the ninth Fermat number: F9 = 2^(2^9) + 1 = 2^(512) + 1 . In binary, this number has the form 100000....000000001 where there are 511 zeros altogether. (F9 is a 513-bit number.) This is a fascinating development, and the researchers involved are to be congratulated for this accomplishment. The algorithm used is known as the "number field sieve", or "NFS" (not to be confused with a network protocol of the same acronym!). The NFS algorithm is described in the Proceedings of the 1990 ACM STOC Conference. The NFS algorithm is based on an idea due to Pollard, as developed further by Arjen Lenstra, Hendrik W. Lenstra, and Mark S. Manasse. The NFS algorithm is specifically designed to factor numbers that, like F9, have a very simple structure: they are of the form a^b + c where c is relatively small. (For F9, we have a=2, b=512, and c=1.) Some simple extensions of this algorithm are also possible, to handle numbers whose binary representation has many zeros, and related kinds of numbers (ternary, etc.) Numbers that have such a special structure are extremely rare and are unlikely to be encountered by chance. That is, the NFS algorithm does not apply to the kind of "ordinary" numbers that arise in practical cryptography, such as using RSA. They only apply to numbers with "sparse" representations having few nonzero components. (Let us call such numbers "rarefied".) When working on a rarefied number, the NFS algorithm has an estimated running time of the form (for an input number n): exp(1.56 (ln n)^1/3 (ln ln n)^2/3) (1) For n = F9, this evaluates to 4.1 x 10^15 operations, which, at 3.15 x 10^13 operations/year for a 1 MIP/sec machine (i.e. a MIP-year), gives a workload estimate of 130 MIP-years, only off by a factor of two from the actual work of 275 MIP-years. (That is, formula (1) may be roughly too low by a factor of two.) It is instructive to see the effect of doubling the size of the number being dealt with. A 1024-bit (332-digit) rarefied number requires an estimated 1.54 x 10^21 operations = 4.9 x 10^7 MIP-years, a dramatic increase in difficulty. The NFS algorithm algorithm is not a "polynomial-time" algorithm; the difficulty of factoring still grows **exponentially** with a polynomial function of the length of the input. What has this to do with RSA and cryptography? I think there are three basic points: -- This development indicates that the status of factoring is still subject to further developments, and it is wise to be conservative in one's choice of key-length. -- The NFS algorithm may yet be generalized to handle "ordinary" numbers, and the potential impact of this should be considered. -- Factoring is still a very hard problem, despite everyone's best efforts to master it. Regarding the further extensions of NFS to handle ordinary numbers, this is judged to be a reasonable possibility by those working on NFS, so it is helpful to consider what impact this may have. It is conjectured (see the ACM STOC paper referenced above) that a successful extension of the NFS algorithm to ordinary numbers would have a running time of the form: exp(2.08 (ln n)^1/3 (ln ln n)^2/3) (2) This is similar to equation (1) except that the constant 1.56 is replaced by the constant 2.08. Note that a practical version of such an extension does NOT yet currently exist (to the best of my knowledge), but even granting its plausibility we arrive at an estimate of the tie required to factor a 512-bit number of 6.5 x 10^20 operations = 2 x 10^7 MIP-years which (in my opinion) is a substantial degree of security. It is interesting to note that this work factor is actually GREATER than that required by the ``standard'' factoring algorithms (e.g., the quadratic sieve), which have a running time of exp((ln n)^1/2 (ln ln n)^1/2); for a 512-bit number, this gives a work-factor estimate of only 6.7 x 10^19 operations. Indeed, the NFS algorithm (when extended) will be asymptotically superior than the quadratic sieve algorithm, but will be slower for numbers with less than about 200 digits. That is, assuming that (2) is indeed the correct running-time estimate for any extension of NFS, then NFS will not affect the security of any numbers of less than about 215 digits. So any "standards" that have been considered using 512-bit RSA moduli are not likely to be affected by any NFS extensions. (At most, one could imagine that the RSA key-generation process might be extended to check that the resulting modulus n is not a rarefied number.) In the truly worst-case scenario, we would have that an extension of NFS would be found that allows ordinary numbers to be factored with a work-factor that is governed by equation (1); in this case one would need to adjust the sizes of moduli used by RSA upwards by a factor of less than two to more than offset the new algorithm. A factor of two in size affects the running time of public-key encryption (or signature verification) by a factor of four and the running time of private-key encryption (or signature generation) by a factor of eight. Noting that the speed of workstations has increased by a factor of over 100 in the last decade (indeed, such factors have been the technological advance that made the successful implementation of NFS possible!), such performance penalties, if necessary, seem to be easily absorbed by expected technological advances in the speeds of the underlying RSA implementation technologies. That is, the NFS-like factoring algorithms do not, even in this worst-case scenario, prevent successful implementations of the RSA cryptosystem. As a cryptographer, I am actually very happy with all the effort that is being spent trying to determine the exact level of difficulty of factoring. Achievements such as the recent development of NFS help to pin down the best-possible rate of growth of the difficulty of factoring, so that users of cryptographic schemes can pick key sizes with an increased degree of confidence that unforeseen developments are unlikely to occur. The best way to ensure confidence in a cryptographic system is to have it attacked vigorously and continuously (but unsuccessfully) by well-qualified attackers. If, despite their best efforts, the difficulty of cracking the system remains intrinsically exponential, then one can have a reasonably high degree of confidence that the system is actually secure. This is the process we have been seeing at work in the recent work on factoring. The results of the attacks can be used to guide the selection of the necessary key size for a desired level of security (with an appropriate margin of safety built in, of course). (As a closing note, here's a prediction: I expect that the 128-digit ``challenge RSA cipher'' published in the August 1977 issue of Scientific American to be cracked (probably by the quadratic sieve algorithm or a variant, not NFS) during the next 1-3 years. This accomplishment will require substantially more computer time than the 275 MIP-years required to factor F9.)