grated circuit technologies will be considered. If ei-

ther quantum computers (a la Shor) or DNA com-

puters (a la Adleman) become practical, the outlook

might change, and even larger moduli might become

n-

Computing power will be measured in units of MY,

or mips-years. By convention, a 1 mips machine is

equivalent to the DEC VAX 11/780 in computing

power, and so 1 MY is one year on a VAX 11/780.

This measure has many defects, and nowadays a wide

Andn?wM. Od&zko is Head of the Mathematics of Communica-

Projections of computing power

tionandComputevSystemsLkpa?tmentatAE˜TBellLhorato-

available in the future

ries in Murray Hill, NewJersey. Hb tnteres.% include computa-

tional complexiFy, cppjpt#˜y, number theory, combinatoti,

The dramatic increase in computing power used for

˜i˜theo?y,a˜˜a˜˜i˜thaotHecanbecontacred

factorization between 1984 and 1994 resulted largely

atamo@x5txazb.att.com.

CRYPTOBYTES

OF RSA LABORATORIES - SUMMER 1995

THE TECHNICAL NEWSLETTER

Page 47

Previous Page Home Next Page

from the introduction of distributed computing, RSA129 project. Thus it is conceivable that a few

The organizers

using the idle time on a network of workstations. individuals, such as systems administrators at a large

of the MA129

This trend was started by Bob Silverman. (An ear- corporation, could organize a covert effort at factor-

project were

lier instance was Richard Schroeppel™s attempt to ing that would dwarf that of the RSA129 project. In

able to obtain

factor&, but that work did not attract much public particular, using the current implementations of the

about 0.03%

attention.) It was fully developed by Arjen Lenstra number field sieve, they could easily factor a 512-bit

of the total

and Mark Manasse. The RSAl29 factorization used integer in under a year of elapsed time, and could do

computing

idle time on around 1600 computers around the so now.

power of the

world during an 8 month period. Most modem fac-

Internet. They

toring methods do lend themselves to distributed It is also possible for small groups of people to as-

also estimated

implementations. semble considerable amounts of distributed comput-

that without

ing power surreptitiously. As an example, a 384-bit

extraordinary

In the remainder of this discussion, we will only con- RSA key was recently broken by Muffett et al. [lo]

effort they could

sider factoring attempts similar to that on RSA129, using about 400 MY. In a few years, we might see

have organized

namely ones that use idle time on networks of com- teenage system administrators for local real estate

a project with

puters. Unlike attacks on DES, where effective at- agents or laundries breaking 512-bit RSA keys with-

100 times as

tacks appear to require a special purpose machine (see out anyone being aware of the attack.

much power,

Appendix J), these attacks do not require any major

commitment of financial or technical resources, and What about the future? Moore™s “Law” says that

can even be mounted surreptitiously. microprocessor processing speed doubles every 18

months. In 10 years, that means an increase by a

Another projection of the future of integer factoriza- factor of about 100. Let us assume that this “law”

tion has been made by Ron Rivest [141. Rivest™s ex- will hold for the next 10 years (Appendix E), and

pectations for progress in computer technology and that a further increase in processing power of between

algorithms do not differ much from mine, but he con- 10 and 100 will be achieved in the following 10 years.

siders what cdn be done with a fured amount of money We then find that the typical processor in 2004 might

using machines bought especially for factoring. be rated at 103 mips, and in 2014 at lo* - 105 mips.

Since there are already over lo8 computers in the

Table 3 (see Appendix D>

world, it seems safe to assume there will be at least

2 * lo9 by 2004. By the year 2014, we might have

RSA129 project 1O™O - 10” (Appendix F). Further, by that time

almost all are likely to be networked together.

However, it is uncertain what fraction might be avail-

able for a factoring experiment. Let us consider two

We note that even without an extensive effort, the scenarios:

It is also

organizers of the RSA129 project were able to obtain

possible for

about 0.03% of the total computing power of the (a) Widely known collaborative effort to break some

small groups

Internet. They also estimated [ll that without ex- challenge cipher. It does not seem out of the ques-

of people to

tion that up to 0.1% of the world™s computing power

traordinary effort they could have organized a project

assemble

with 100 times as much power, or about 3% of the might be made available for a year. (The RSA129

considerable

capacity of the Internet. project organizers estimated they could have obtained

amounts of

access to 3% of the computing power of the Internet,

distributed

We should also note that (and this is relevant for but this 3% factor might not scale as the networks

computing

cryptosystem security) there are relatively small or- grow.) This yields 2.109 MY available in 2004, and

power

ganizations that have large amounts of computing 101™ - 10™3 MY in 2014.

surreptitiously.

power all by themselves. Silicon Graphics, for ex-

ample, has about 5,000 employees and 10,000 work- (b) Surreptitious effort arranged by a handful of

stations, for total computing power of perhaps lo5 people at an organization such as a corporation or

mips, about 10 times the computing power of the university. They might have available to them lo5

CRYPTOBYTES S ER 1 9 9 5 -THE TECHNICAL NEWSLETTER LABORATORIES

OF RSA

hia U M M

Page 48

Previous Page Home Next Page

computers in 2004, and up to lo6 in 2014. Thus they tions of RSA, can already be factored with the

might have 10s MY at their disposal in 2004, and available computing power. There is no need for

1Oro - 10” in 2014. (Would they attempt to attack a new algorithms or faster or more computers, just the

single cryptographic system, or would they attempt effort to find enough people willing to let their

to attack 1000 different systems? This would likely workstations be used in their idle time. The ma-

depend on what moduli are used, and on the poten- chines at Silicon Graphics alone could factor a

tial payoff.) single 512-bit integer in about half a year total time

(under the assumption that they are idle about two

We summarize the projections above in Table 4. thirds of the time).

Algorithmic improvements

Table 4

The special number field sieve (snfs) applies to inte-

gers such as the Fermat numbers. Based on the re-

cent factorization of a I62D special integer by

Boender et al. in about 200 MY, we can estimate how

long snfs takes to factor various integers, and the re-

Factorization using current algorithms sults are presented in Table 6.

Of the methods that are currently known and apply

to generally hard integers, the general number field Table 6

sieve (gnfs) has the best asymptotic running time Is it reasonable

estimate. It is also practical, and runs faster than pre- to expect a

vious algorithms on generally hard integers of more l-105 breakthrough

768

than about 115D. Since a 119D integer was factored that would

1024 3'107

recently using gnfs with 250 MY (see Appendix 0, enable

1280 3.109

we can project, using standard methods (see Appen- 2 - 10” generally hard

1536

dix H), the amount of computing that is likely to be 4 * 10'4

2048 integers to be

required to factor various integers. The results are factored in

shown in Table 5. In particular, it appears that it might be possible to about the

factor F,, = 2*O** + 1 by the year 2000 (continuing same time

the tradition in which F, was factored in 1970, Fs in

Table 5 that the snfs

1980, and F9 in 1990). factors integers

of comparable

Is it reasonable to expect a breakthrough that would size?

enable generally hard integers to be factored in about

the same time that the snfs factors integers of com-

parable size? I feel that it is prudent to expect even

larger improvements. It is impossible to predict sci-

entific breakthroughs. However, just as in other dis-

ciplines (cf. “Moore™s Law”), one can observe a steady

progress in integer factoring. Every few years a new

Thus, based on tables 4 and 5, moduli of 1280 bits

algorithm appears that allows for factoring much

are likely to be safe for well over 20 years, and even

larger integers, and then there is a steady stream of

1024-bit moduli are not likely to be vulnerable,

incremental improvements. As one example, there

unless they conceal extremely valuable information.

were wide concerns that the linear algebra step that

However, Table 5 assumes that the current version of

plays a crucial role in most of the fast integer factor-

gnfs will remain the best algorithm. This would be

ization algorithms might become a serious bottleneck

an extremely imprudent assumption, as history shows

that algorithmic improvements are often crucial. when factoring large integers, since it could not be

executed easily in a distributed way. However, new

It is important to note that 512-bit integers, which algorithms were developed in the last decade that

are used in a variety of commercial implementa- have allayed these concerns.

THE TECHNICAL NEWSLETTER OF RSA LABORATORIES - SUMMER 1995 CRYPTOBYTES

Page 49

Previous Page Home Next Page

The main reason that the projections for lengths of

To factor a 129D integer with the continued frac-

safe moduli are growing so fast is that the asymptotic

tion method that was used in the 1970s would have

required about 6 * lOi* times more computing power running time estimates for the latest factoring algo-

than to factor a 45D integer, but the factorization rithms are subexponential. In particular, the growth

took only about 5. lo6 times as much because a rate for the running time of the number field sieve is

much better algorithm was used. Thus here the al- not fast. By comparison, there are problems where

gorithmic improvement was comparable (on a loga- the only known algorithms have exponential running

rithmic scale) to the hardware one. This is similar times, such as DES and related ciphers, and also many

to what has been reported in other areas, such as public key schemes on elliptic curves (see Appendix

numerical analysis, where again better mathemati- I>. It might therefore be prudent to consider even

cal ideas have contributed about as much as faster more seriously elliptic curve cryptosystems.

computers.

Acknowledgements

Let us assume that algorithmic improvements will I thank Len Adleman, John Brillhart, Dan Bernstein,

continue to be comparable to those from increasing Marije Huizing, Hugo Krawczyk, Arjen Lenstra, Paul

computing power. Then we can expect that even a Leyland, Mark Manasse, Carl Pomerance, Ron

covert attack in 2004, which with present algorithms Rivest, and Michael Wiener for their helpful com-

ments.

could only factor about a 768bit integer, will instead

be able to factor a 1024-bit one. For the year 2014,

References

the threshold of what might be achievable rises to

1500 bits or even more. [ll D. Atkins, M. Graff, A. K. Lenstra, and P. C. Leyland,

The magic words are squeamish ossiftage, pp. 263-277 in

Conclusions Advances in Cryptology- ASIACRI?T ˜94, J. Pieprzyk and

For many applications, the conjectured progress in R. Safavi-Naini, eds., Lecture Notes in Comp. Sci. 917,

For many

factorization is not a serious threat. For example, Springer, 1995.

applications,

for digital signatures, time-stamping (a la Haber 121 J. Brillhart and J. L. Selfridge, Some factorizations of

the conjectured

and Stornetta) provides a way to maintain their 2” f 1 and related results,M&. Comp. 21(1967), 87-96.

progress in

validity (although in a somewhat cumbersome way, 131 B. Dodson and A. K. Lenstra, NFS with four large primes:

factorization is

requiring recourse to a document trail) even as se- An explosive experiment, Advances in Cryptology -

not a serious

cret moduli are factored. (This assumes, or course,

threat. [...I CRYPTO ˜95, D. Coppersmith, ed., Lecture Notes in

that there are no totally unexpected breakthroughs, Comp. Sci., Springer, 1995, to appear.

However, for

so that it is possible to estimate at any given time I41 J. J. Dongarra, H. W. Meuer, and E. Stmhmaier, TOP500

some records,

what are the largest integers that might be factor- supercomputer sites, report available electronically at

even 20-year

able in the next year, say.) Also, for many records, URL http://www.netlib.org/benchmark/top5OO.html.

protection is

the security requirements are not serious, in that [51 M. Gardner, Mathematical games, Sci. Amer., August

not sufficient.

loss of secrecy after 10 years or sometimes even 10 1977, 120-124.

days is acceptable. Hardware improvements favor [61 R. K. Guy, How to factor a number, in “Proc. Fifth

the cipher designer, since a loo-fold speedup in Manitoba Conf. Num. Math.,” Congressus Num. 1G

commonly used processors allows for a lo-fold in- (19761, 49-89.

crease in the modulus in DSS (assuming, as seems 171 W. Stanley Jevons, i%ePrinc@les ofScience, 1874.

reasonable, that the auxiliary prime q stays at 160 181 A. K. Lenstra and H. W. Lenstra, Jr., eds., TheDevelop-

bits, or is increased to at most 240 bits), for ex- ment of the NumberField Sieve, Lecture Notes in Math.

ample. However, for some records, even 20-year 1554, Springer, 1993.

protection is not sufficient. In those cases ex- [9] A. J. Menezes, Elliptic Curve Public Key Cyptosystems,

tremely large moduli appear to be required for many Kiuwer, 1993.

of the most popular public key systems, such as (101 A. Muffett, P. Leyland, A. Lenstra, and J. Gillogly, The

RSA and the various ElGamal-type algorithms, BlackNet 384-bit PGP key has been BROKEN, message

such as the DSA. For extremely sensitive informa- posted to scicrypt and other newsgroups on June 26,1995.

tion, it might sometimes be prudent to use lO,OOO- Ill] A. M. Odlyzko, Discrete logarithms and smooth polyno-

mials, pp. 269-278 in Finite Fiehk 7&o y, A@ications and

bit moduli.

CRYPTOBYTES 1 9 9 5 -THE TECHNICAL

SUMME? NEWSLETTER OF RSA LABORATORIES

H