<<

. 13
( 19 .)



>>

Page 50
Previous Page Home Next Page




be surprised if anyone regularly factors numbers of
Algorithms, G. L. Mullen and P. Shiue, eds., Amer. Math. The problem
size lo” without special form during the present cen-
sot., 1994. of factoring
tury.” He was also shown to be too cautious in a few
I121 C. Pomerance, The number field sieve, pp. 465-480 in integers has
years. The choice of a 129D integer for the RSA
Mathematics of Computation 1943-1993: A HalfCentury fascinated
challenge number in 1977 151 was apparently moti-
of ComputationalMathemutics, W. Gautschi, ed., Amer. mathematicians
vated by an estimate of Ron Rivest that to factor such
Math. Sot., 1994. for a long time
an integer would require more than “40 quadrillion
[I31 C. Pometance, J. W. Smith, and R. Tuler, A pipeline ar-
years” on a computer much faster than any that exist
chitecture for factoring large integers with the quadratic
even today. However, this challenge integer was fac-
sieve algorithm, SIAMJ. Comput. 17(1988), 387-403.
tored in 1994.
[14] R. L. Rivest, Dr. Ron Rivest on the difficulty of factoring,
first published inCipher?ext: L%eRSA Newsktte˜ vol. 1,
no. 1, fall 1993, and reprinted, in an updated form, in an
appendix on pp. 361-364 in S. Garfinkel, PGR Pretty
In 1964, there was practically no organized activity
Goodpriuacy, O™Reilly & Associates, 1995.
in factoring integers, and so this entry is based on the
f151 M. J. Wiener, Efficient DES key search, TR-244, May
remarks in 121.
1994, School of Computer Science, Carleton University,
Ottawa, Canada. Presented at the Rump Session of
The largest generally hard integer that had been fac-
Crypto ˜93. Available through anonymous ftp from
tored by 1974 was F,, the 7-th Fermat number,
ripem.msu.edu:/pub/crvpt/docs/des-key-˜.˜.
21B + 1, which is 39D. (Today it would not be classi-
fied as “generally hard,” since the special number field
Appendices sieve handles numbers of this type much more effi-
ciently than general ones. Also, as another techni-
cal point, the integer that was factored was 257 * F,,
AppendkA:Hidoricales-
since the use of a multiplier speeded up the algo-
ofthed3Ekultyoff
rithm.) F, had been factored in 1970 by Mike
The problem of factoring integers has fascinated Morrison and John Brillhart, but their paper describ-
mathematicians for a long time, and there is a fa- ing this work was only published in the 1975 D. H.
mous quote of Gauss on what a fundamental ques- Lehmer special issue of&&. Comp. In those days,
tion this is. A concrete estimate of how hard it might integer factorization was not fashionable, and there
be was provided in 1874 by W. Stanley Jevons, the was not much interest in going after records. There-
English economist and logician. He conjectured 171 fore inspection of the published literature is not ad-
that nobody but he would ever know the factors of equate to assess the state of the art. Experts who were
the 10D integer 8616460799. However, he was active in this area in the 1970s say that they thought
proved wrong by Bancroft Brown around 1925, and that numbers of 45D were doable with the algorithms
perhaps by others even earlier. In an unpublished and machines available then, and so 45D is the fig-
manuscript, a copy of which was kindly provided ure used here.
by John Brillhan, Brown explained how he obtained
the factorization 1984: This is the Sandia factorization of Jim Davis,
Diane Holdridge, and Gus Simmons.
8616460799 = 96079 * 89681.
1994: This is RSA129, the RSA challenge integer of
In 1967, John Brillhart and John Selfridge [21 stated 1977, which was factored by a world-wide collabora-
that ˜I... in general nothing but frustration can be tive effort organized and led by Derek Atkins,
expected to come from an attack on a number of 25 Michael Graff, Arjen Lenstra, and Paul Leyland [l].
or more digits, even with the speeds available in mod-
ern computers.” By 1970 their estimate was out of If we also consider integers of a special form, then the
date because of a new factoring method that allowed i62D integer (12i5i - 1) / 11 provides another record.
Mike Morrison and John Brillhart to factor an inte- It was factored in 1994 by Henk Boender, Joe Buhler,
ger of 39D. In 1976, Richard Guy t61 stated “I shall Scott Huddleston, Marije Huizing, Walter Lioen,


la
THE TECHNICAL NEWSLETTER OF RSA LABORATORIES - SUMMER 1995 CRYPTOBYTES
Page 51
Previous Page Home Next Page




mate equates 1 megaflop with 1 mips, which is not
Peter Montgomery, Herman te Riele, Robby Robson,
very accurate, and is based on the June 1995 version
Russell Ruby, and Dik Winter.
of the TOP500 report 141.) IBM mainframes shipped
in 1994 (which was a record year in terms of main-
Appendixc:Gxnput@powerof
frame computing power, although not in dollar vol-
histodd-ns
ume of sales) amounted to only 2 * lo5 mips.
According to John Brillhart, integer factorizations in
It seems
the early 1970s usually used up only about an hour of Appendix E: Moore™s “Iaw”
imprudent
cpu time on the mainframes of those days, which are
to assume
There is some skepticism whether this law will con-
typically rated at l-10 mips.
Moore™s “Law”
tinue to hold much longer. Line widths will eventu-
will be violated
ally be so small that entire new technologies might
The 1984 Sandia factorization used 9.5 cpu hours on
any time soon.
be needed, architectural improvements (speculative
a Cray X-MP, which is on the order of 100 mips.
execution, etc.) might run into the exponential com-
plexity blowup, and so on. Even if the bare tech-
1994: This is the Atkins et al. estimate tll for the
nologies are not a barrier, economics might present
computation, which used the ppmpqs algorithm.
one, since the costs of state of the art fabrication fa-
Since then a 119D integer has been factored by Scott
cilities are also escalating. However, such concerns
Contini, Bruce Dodson, Arjen Lenstra, and Peter
are not new, and were already present a decade ago,
Montgomery in about 250 MY using gnfs (the gen-
and yet progress has continued unhindered. Thus it
eral number field sieve), suggesting that today the
seems imprudent to assume Moore™s “Law” will be
RSA129 factorization could be carried out in about
violated any time soon. Since state of the art micro-
1000 MY instead of the 5000 MY that was used. See
processors are already running close to 500 mips, the
131 for details.
projection that by 2004 the typical processor will
have a rating of 1000 mips (compared to around 10
AppendixD:Qmentcomputingpower
mips today) seems safe. Beyond that, there are big-
ger question marks. Even if raw processor speed con-
The oft-quoted figure of 30M users of the Internet is
tinues to increase, memories might be more of a
questionable, as it is obtained by assuming there are
bottleneck. Since most fast factorization algorithms
10 users per computer. However, the estimate that
rely on substantial memories to perform sieving op-
about 3M machines of one kind or another are
erations, they are often already limited by memory
hooked up to the Internet seems much more solid.
system performance more than by the processor.
Since many of them are old, an average 10 mips rat-
However, this is a problem that is afflicting an in-
ing seems reasonable for them.
creasing range of problems. Therefore there are
strong incentives towards dealing with it, and again
There are well over 108 PCs in the world. Since sev-
it seems imprudent to assume it will form an insur-
eral tens of millions of them already have the 486
mountable barrier.
chips, which are usually rated at tens of mips, the es-
The TV set-top
timate of 3 * lOa mips is conservative. On the other
boxes being
hand, most of these machines are not easily usable AppedixF:Numberofcomputem
designed today
for factoring, since they are not networked, do not
have more
Since there will be about lOi people on Earth in
have enough memory, do not have operating systems
computing
2014, a projection of 10” computers implies that
that allow for background jobs to run easily in idle
power than
there will be over 10 computers per person. This may
time, etc. All these factors will change in a few years,
the Cray- I,
seem fanciful, but we should remember that there are
but now it would be hard to harness a large fraction
the first
many embedded microprocessors in everyday appli-
of all the PCs in a factoring project.
supercomputer.
ances such as cars, dishwashers, etc., and they will be
getting increasingly powerful. To provide voice rec-
We might note that all the supercomputers in the
ognition capability for the coffee pot will require con-
world (about 103 in total) have a computing power
siderable processing power. (The TV set-top boxes
of about 3 . lo6 mips, with several sites having be-
being designed today have more computing power
tween 5% and 10% of of that capacity. (This esti-


RSA LABORATORIES
1 9 9 5 -THE TECHNICAL NEWSLETTER OF
CRYPTOBYTES SUMMER
Eiil
Page 52
Previous Page Home Next Page




The continued fraction method, which was the
than the Cray-1, the first supercomputer. The new
32-bit video game machines, of which tens of mil- most widely used method in the 197Os, appears
lions are expected to be sold each year, will have (at least for the most common variant) to have nm-
similar power.) We might note, as a forerunner of ning time
what will be common, that there were two fax ma-
chines among the approximately 1600 processors in Lh, l/2, c3 + o(l)1 as 72 0 ,
the RSA129 project.
where c, = 2l/* = 1.4142 . . .
There is still a question, even if we assume that there
will be many computers around, of whether they will AppendixH:Comparisonofnmningt.imes
all be networked together, and whether their com- ofalgprithnrs
puting power will be easily accessible. Will there be
computing-power brokers, selling time on millions of The o(1) terms in the estimates of running times of
machines? Will people be willing to tolerate some- factorization algorithms are usually not computed
body else running jobs on their machines, even in explicitly. Instead, to estimate how long an algorithm
spare time? with asymptotic running time Lln, z.r, a + o(l)1
should take to factor an integer n, one takes the
observed running timeX on an integer m and com-
AppendhGRmmingtimeofalgorithms
putesX * Lln, ˜1, al /L[m, V, al. This has worked well
In a variant of the standard notation, we define in practice. This method does ignore various impor-
tant practical aspects, such as the need for memory
and communication capacity as well as cpu cycles,
Lln, v, al = exp<u - (log fz)” - (log log tzP) >,
but those have been overcome in the past either
where log n refers to the natural logarithm of n. through better algorithms or general technological
improvements, so it seems reasonable to continue to
The heuristic running time (there are no rigorous ignore them.
proofs, but experience and heuristics support the cal-
culations) of the gnfs to factor an integer n is

Lln, l/3, co + o(l)1 as n 0 , Public key cryptosystems such as RSA and DSA There are some
require use of large moduli because known general problems in
where cg = (64/W/3 = 1.9229 . . . . There is also a algorithms for factoring integers and computing dis- which the best
variant, due to Don Coppersmith, which does not crete logarithms are subexponential, and so hardware algorithms
seem to be practical, that allows the replacement of improvements by themselves lead to substantial known are
q, by cl = 1.3018. . . . See 18,121 for presentations of progress. In addition, there have been steady and exponential,
the gnfs. rapid improvements in algorithms, On the other and where
hand, there are some problems in which the best al- there has been
The special number field sieve, which factors effi- gorithms known are exponential, and where there has no recent
ciently integers of the form& 1 6, for example, where been no recent algorithmic improvement. We cite algorithmic
a and 6 are small, and k large (k can also be small, but here as an example attacks on DSA, the US Digital improvement
then has to fall into certain ranges) has running time Signature Algorithm, that do not use the structure of
the multiplicative group of integers modulo the large
Lb, l/3, c2 + o(l)1 as n 0 , basic primep. The DSA uses discrete exponentia-
tion modulo a primep, but the exponents are com-
where ca = (32/9)˜/3 = 1.5262 . . . . puted modulo a prime q such that q dividesp - 1.
CIlis is the Schnorr method that speeds up the algo-
Previous methods, such as variants of the quadratic rithm.) Therefore all the integers are inside an abe-
sieve algorithm, have running times of the form lian group of order q. To break DSA, one can either
solve the general discrete log problem modulo p,
which can be done using a variant of the number field
L[n, l/2, 1 + o(l)] as n 0



liiii
THE TECHNICAL NEWSLETTER OF RSA LABORATORIES - SUMMER CRYPTOBYTES
199S
Page 53
Previous Page Home Next Page




cost) and would find a single DES key in about 4
sieve, or else work inside the group of order q. The
hours. What this shows is that special purpose hard-
best algorithms for the second attack are those of Dan
Shanks and John Pollard, both of which take about ware can be of great help in breaking DES. On the
& operations. Since these 6 operations involve other hand, general integer factorization and dis-
multiplications modulop, though, even for q of 160 crete logarithm algorithms do not benefit that much
bits andp of 1024 bits or more, it would take at least from special designs, and it is the threat of the free

<<

. 13
( 19 .)



>>