<<

. 12
( 19 .)



>>

Only conventional algorithms and standard inte-
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

<<

. 12
( 19 .)



>>