The F9 factoring result

 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.)