Arjen K. LenstraLucent Technologies' Bell Labs.ppt

1、Arjen K. Lenstra Lucent Technologies Bell Labs,Actual and proposed special purpose hardware devices for integer factorization(a historical perspective),Integer factorization,Given a composite n, find a non-trivial factor of n,Example: given n = 15, find 3 or 5,Why?,Special purpose hardware forintege

2、r factorization,Why?,Actual and proposed special purposehardware devices for integer factorization,Actual and proposed special purposehardware devices for integer factorization,1919, Carissan: Machine Congruences1930s, Lehmer: Bicycle Chain Sieve, Photo-Electric Number Sieve, and Movie Film Sieve197

3、0s, Smith/Wagstaff: Georgia Cracker1980s, Pomerance/Smith/Tuler: Quasimodo,Actual and proposed special purposehardware devices for integer factorization,1919, Carissan: Machine Congruences1930s, Lehmer: Bicycle Chain Sieve, Photo-Electric Number Sieve, and Movie Film Sieve1970s, Smith/Wagstaff: Geor

4、gia Cracker1980s, Pomerance/Smith/Tuler: Quasimodo,1999, Shamir: Twinkle2002, Bernstein: Factoring Circuits2003, Shamir/Tromer: Twirl2004, Geiselmann/Steindwandt: YASD2005, Franke/Kleinjung/Paar/Pelzl/Priplata/Stahlke: SHARK (and several other matrix step proposals),The early machines (Carissan, Leh

5、mer),To factor n, try to solve n = x2 y2 = (x + y)(x y):look for x = i + n such that x2 n is a square (y2):for a small set of small primes p:manually find the xs for which x2 n modulo p is a squaremark those xs on a wheel with p positionsturn all wheels simultaneously (i = 0,1,2,) until there is a s

6、et of conditions (one per wheel) that lines uphope that it leads to the desired solution y if there is a solution, it will show up, but it may take a while,Carissans Machine Congruences,14 concentric brass rings with p 59 studs per ringconditions x2 n square mod p represented by caps on studsa cap u

7、nder the arm triggers a switch14 switches in series: alarm sounds if all 14 switches triggered,Some results,primality proof of 708 158 977 in 10 minutes (of manual cranking)factorization, in 18 minutes: 7 141 075 053 842 = 2 841 249 4 244 329,around 1920: the only prototype disappeared in a drawer,n

8、ot to be seen again until March 1992see: Jeff Shallit, Hugh Williams, Franois Morain, Discovery of a lost factoring machine,Mathematical Intelligencer 17 (1995) 41-47,Lehmers Bicycle Chain Sieve,cruder (but faster: motorized!) version of same ideafound that 9 999 000 099 990 001 = 1 676 321 5 964 84

9、8 081,Lehmers Photo-Electric Number Sieve,condition corresponds to a hole in a sprocket-wheelif holes line up: a (weak) light beam passes through, caught by photo-electric detector (the fair Rebecca) & stops the machine (unless nearby ham radio operator was active)much faster than Carissans machine,

10、Some results,factorization, in 12 seconds: 279 1 = 2 687 202 029 703 1 113 491 139 767factors of 293 + 1 , in a few seconds: 529 510 939 and 2 903 110 321,see: D.N. Lehmer, Hunting big game in the theory of numbers,Scripta Mathematica 1 (1932-33) 229-235D.H. Lehmer,A photo-electric number sieve,Amer

11、 Math. Monthly 40 (1933) 401-406,The later machines,All based on the 1970s Morrison-Brillhart approach: to factor n, try to solve x2 y2 mod n as follows,Collect set V of integers v with v2 pP pe(v,p) mod nfor some fixed set P and |V| |P|Find |V| |P| linear dependencies mod 2 among the|P|-dimensiona

12、l vectors (e(v,p)vVEach dependency leads to pair x, y with x2 y2 mod n and thus to a chance to factor n by computing gcd(n, x y),: Georgia Cracker, QuasimodoTwinkle, Twirl, YASD, SHARK: Factoring Circuits,The Georgia Cracker,special purpose hardware to collect relationsusing CFRAC (continued fractio

13、n factoring method) no striking or particularly interesting features (no picture either),used to factor numbers from Cunningham tables,largest: a 62-digit factor of 3204 + 1, January 1986sitting on a shelf in Jeff Smiths office:it could be working again 1wk,Quasimodo,stands for Quadratic Sieve Motor

14、special purpose hardware to collect relationsusing QS (quadratic sieve factoring method)interesting pipelined architecture,supposedly very fast, when it was designedno longer so when it was actually builtnever properly debugged, never used to factor anythingparts of only existing prototype used for

15、other purposesnever seen it, no pictures, unclear what survives, if anything,Intermezzo,Since the late 1980s:PCs become ubiquitouscomputing power for relation collection step canrelatively easily be arrangedas a result:special purpose devices no longer worth the trouble,unless they offer something n

16、ew or special(or lead to interesting funding possibilities)relation collection step easiest(just sit back and relax until done, progress can be monitored)matrix more cumbersome(get your hands on a big machine, worry about bits),Twinkle, 1999,The first special purpose hardware factoring device sincei

17、nternet factoring became popularstands for The Weizmann INstitute Key Locating Engine,special purpose optical sieving device to collectrelations using QS or NFS (number field sieve),short history:spring 1999: wild claims in press that 512-bit RSA moduli can be broken very quicklyMay 1999: Twinkle an

18、nounced at EC99 rumpsessionAugust 1999: 512-bit RSA actually broken (but not using Twinkle)May 2000: Twinkle buried at EC2000,Regular sieving,initialize si = 0 for all i in some large interval Ifor all p P:compute starting point rpfor all rp + kp I with k Z: replace srp + kp by srp + kp + logpfurthe

19、r process all i I for which si is large enough,sieve s represented by spacep P processed in time,sieve represented by timeTwinkle:p P processed in space(just like Carissan and the Lehmer sieves),Twinkle sieving,Build a wafer with for all p P:a cell with:a counter c starting at 0a register a containi

20、ng rp, the starting point for pan LED of strength proportional to logp Put a photo-electric cell opposite the wafer,for i = 0, 1, 2, in succession:on all cells simultaneously:if c = a: flash the LED and replace a by a + preplace c by c + 1( for cell p, light of intensity logp flashes at i = rp + kp)

21、if light intensity at photo-electric cell strong enough: many ps flash at i, thus further process i,Analysis of Twinkle,for 384-bit QS factorization: not clearly infeasible,for anything interesting (such as, back then, 512-bit moduli): wafer too large to be practicalwafer may melt (part of audience

22、did) processing of reports too expensive,multi-wafer designsrun it at lower speedadd hardware,idea in the mean time abandonedexcept for a rather crude prototype, device never built,Factoring circuits, 2002,At least two interesting aspects:,Claim that 3d-digit integers can be factored at the cost of

23、d-digit integers using old method,A new method to do the matrix step,Influential, because: It caused confusion (almost panic), thus got a lot of attentionTriggered lots of new activity in this field (possibly even culminating in the present workshop)Pushed a new, better cost function: time equipment

24、 cost,Matrix step,Find dependency mod 2 among columns of sparse A:,compute Aiv for some vector v and 1 i m = dim(A)(plus additional fiddling around),Matrix step hardware proposals and claims,This workshop, and earlier:several mesh proposalssystolic architecture(s),Results and claims for 1024-bit mod

25、ulistrongly depend on dimension and density of the matrixresults of mostly speculative naturematrix step still seems not as hard as relation collection,known: factor bases sizes that will most likely workno real clue yet about dimension and density of the matrix,Relation collection in the NFS,A comm

26、on version of the problem:integer m, polynomial f of degree d, smoothness bounds B1, B2 find many coprime integers a and b 0 such that|a mb| is B1-smooth and |bdf(a/b)| is B2-smooth,Software approaches:line sieving: for b = 1, 2, in succession process line of asspecial q: for many qs, look at a,b wi

27、th q | bdf(a/b):do line sieving in index q sublattice (insane but common)do lattice sieving as suggested byPollards ancient paper (not so bad)Franke and Kleinjungs SHARCS paper (looks promising),combine with or replace by non-sieving methods such aselliptic curve factoring or FFT&gcd based,Special p

28、urpose hardware to collect relations,My limited understanding of the situation (as of Feb 23):TWIRL: line siever (or KF lattice siever?) with priority queues, challenging pipelined design 1024-bit in about 1M$yrYASD: traditional liner siever, mesh based, no inter-chip connects, 6.3 times slower than

29、 TWIRLSHARK: KF lattice siever with special cofactor hardware, modular, realizable ASIC design 1024-bit in 200M$yr,ECCITY: replace all sieving by Elliptic Curve Factoring, fills entire country with multicomputers, each of which has the size of a major city (at break-even point),Putting 1-200M$yr int

30、o context,SHA-1 random collision attack: fewer than 269 SHA-1 applicationsSHA-1 application takes fewer than 900 cyclesplaystation 3 VGA card (16 vector 4.5GHz PEs) costs US$50attacking SHA-1 on a single COTS card takes 2K centuries Attacking SHA-1 costs 10M$yr,same ballpark as 1024-bit RSAsame card

31、s: crack DES in a day for about 200KSHA1 attack cost: down from 20B$yr a few weeks agoat least a factor 200 gap between 1024-bit RSA and 80-bit securitywhat about running ECM on those cards?,Conclusion,design and evaluation of current special purpose hardwarefactoring devices still mostly in the mud

32、 slinging phaselisten to the talks here and make up your own mindmy pessimistic guesses:none of the currently proposed devices will collect relationsfor an actual 1024-bit factorization anytime soonspecial purpose factoring hardware will not havemuch impact on the security of RSA moduli untilquantum computers are built(I hope I will be proved wrong),