X From:	CRDGW2::CRDGW2::MRGATE::"SMTP::PYRITE.RUTGERS.EDU::NOBODY" 17-JUL-1990 12:22:00.76 To:	MRGATE::"ARISIA::EVERHART" CC:	. Subj:	[Theodore Lee:  The F9 factoring result]  * Received:  by crdgw1.ge.com (5.57/GE 1.70)) 	 id AA23335; Tue, 17 Jul 90 02:06:22 EDT / Message-Id:  <9007170606.AA23335@crdgw1.ge.com> ! Sender: nobody@pyrite.rutgers.edu $ Date:     Mon, 2 Jul 90 11:29:15 EDT> From: "Michael J. Chinni, SMCAR-CCS-E" <mchinni@pica.army.mil>2 Subject:  [Theodore Lee:  The F9 factoring result] To: security@pyrite.rutgers.edu   , 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  H 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 8 reports of RSA's demise have been greatly exaggerated...0 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. 6 	Please send corrections to rivest@theory.lcs.mit.edu)  J This note is in response to the numerous inquiries I've received regardingI the recent factoring of a 155-digit number by A. Lenstra, M. Manasse, and E others.  (See the New York Times article of 6/20/1990 by G. Kolata.)  J This note attempts specifically to correct some of the misimpressions that8 may arise from a reading of such popular press articles.  C Using an ingenious new algorithm, Lenstra, Manasse, and others have E 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.)I This is a fascinating development, and the researchers involved are to be & congratulated for this accomplishment.  F The algorithm used is known as the "number field sieve", or "NFS" (notF to be confused with a network protocol of the same acronym!).  The NFSJ algorithm is described in the Proceedings of the 1990 ACM STOC Conference.M The NFS algorithm is based on an idea due to Pollard, as developed further by 7 Arjen Lenstra, Hendrik W. Lenstra, and Mark S. Manasse.   B 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 D where c is relatively small.  (For F9, we have a=2, b=512, and c=1.)E Some simple extensions of this algorithm are also possible, to handle E numbers whose binary representation has many zeros, and related kinds J of numbers (ternary, etc.)  Numbers that have such a special structure areF extremely rare and are unlikely to be encountered by chance.  That is,G the NFS algorithm does not apply to the kind of "ordinary" numbers that G arise in practical cryptography, such as using RSA.  They only apply to D numbers with "sparse" representations having few nonzero components.& (Let us call such numbers "rarefied".)  E When working on a rarefied number, the NFS algorithm has an estimated 1 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, F 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,L only off by a factor of two from the actual work of 275 MIP-years. (That is,7 formula (1) may be roughly too low by a factor of two.)   F It is instructive to see the effect of doubling the size of the numberO 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,H a dramatic increase in difficulty.  The NFS algorithm algorithm is not aD "polynomial-time" algorithm; the difficulty of factoring still growsH **exponentially** with a polynomial function of the length of the input.  G 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. A 	-- The NFS algorithm may yet be generalized to handle "ordinary" C 	   numbers, and the potential impact of this should be considered. C 	-- Factoring is still a very hard problem, despite everyone's best  	   efforts to master it.   K Regarding the further extensions of NFS to handle ordinary numbers, this is H judged to be a reasonable possibility by those working on NFS, so it is . helpful to consider what impact this may have.  M It is conjectured (see the ACM STOC paper referenced above) that a successful L 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 isE 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-yearsB which (in my opinion) is a substantial degree of security.  It is G interesting to note that this work factor is actually GREATER than that N 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. N Indeed, the NFS algorithm (when extended) will be asymptotically superior thanH the quadratic sieve algorithm, but will be slower for numbers with less H than about 200 digits.  That is, assuming that (2) is indeed the correctL running-time estimate for any extension of NFS, then NFS will not affect theJ security of any numbers of less than about 215 digits.  So any "standards"G that have been considered using 512-bit RSA moduli are not likely to be E affected by any NFS extensions.  (At most, one could imagine that the H RSA key-generation process might be extended to check that the resulting$ modulus n is not a rarefied number.)  D In the truly worst-case scenario, we would have that an extension ofE NFS would be found that allows ordinary numbers to be factored with a D work-factor that is governed by equation (1); in this case one wouldE need to adjust the sizes of moduli used by RSA upwards by a factor of E 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 C signature verification) by a factor of four and the running time of F private-key encryption (or signature generation) by a factor of eight.B Noting that the speed of workstations has increased by a factor of? over 100 in the last decade (indeed, such factors have been the D technological advance that made the successful implementation of NFS@ possible!), such performance penalties, if necessary, seem to beC easily absorbed by expected technological advances in the speeds of F the underlying RSA implementation technologies.  That is, the NFS-likeF factoring algorithms do not, even in this worst-case scenario, prevent3 successful implementations of the RSA cryptosystem.   E As a cryptographer, I am actually very happy with all the effort that C is being spent trying to determine the exact level of difficulty of F factoring.  Achievements such as the recent development of NFS help to> pin down the best-possible rate of growth of the difficulty ofD factoring, so that users of cryptographic schemes can pick key sizesC 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 andC continuously (but unsuccessfully) by well-qualified attackers.  If,.A despite their best efforts, the difficulty of cracking the systemEF remains intrinsically exponential, then one can have a reasonably highE degree of confidence that the system is actually secure.  This is the6D process we have been seeing at work in the recent work on factoring.D The results of the attacks can be used to guide the selection of the; necessary key size for a desired level of security (with anj2 appropriate margin of safety built in, of course).  D (As a closing note, here's a prediction: I expect that the 128-digit> ``challenge RSA cipher'' published in the August 1977 issue ofB Scientific American to be cracked (probably by the quadratic sieveA algorithm or a variant, not NFS) during the next 1-3 years.  ThistE accomplishment will require substantially more computer time than thef% 275 MIP-years required to factor F9.)f  