Reference / Paper · 2003
Factoring Large Numbers with the TWIRL Device (CRYPTO 2003)
TWIRL, a proposed special-purpose hardware sieve for factoring 1024-bit RSA moduli.
Reference / Paper · 2003
TWIRL, a proposed special-purpose hardware sieve for factoring 1024-bit RSA moduli.
Factoring Large Numbers with the TWIRL Device Adi Shamir and Eran Tromer Department of Computer Science and Applied Mathematics Weizmann Institute of Science, Rehovot 76100, Israel {shamir,tromer}@wisdom.weizmann.ac.il Abstract. The security of the RSA cryptosystem depends on the difficulty of factoring large integers. The best current factoring algorithm is the Number Field Sieve (NFS), and its most difficult part is the sieving step. In 1999 a large distributed computation involving hundreds of workstations working for many months managed to factor a 512-bit RSA key, but 1024bit keys were believed to be safe for the next 15-20 years. In this paper we describe a new hardware implementation of the NFS sieving step (based on standard 0.13µm, 1GHz silicon VLSI technology) which is 3-4 orders of magnitude more cost effective than the best previously published designs (such as the optoelectronic TWINKLE and the mesh-based sieving). Based on a detailed analysis of all the critical components (but without an actual implementation), we believe that the NFS sieving step for 512-bit RSA keys can be completed in less than ten minutes by a $10K device. For 1024-bit RSA keys, analysis of the NFS parameters (backed by experimental data where possible) suggests that sieving step can be completed in less than a year by a $10M device. Coupled with recent results about the cost of the NFS matrix step, this raises some concerns about the security of this key size. 1 Introduction The hardness of integer factorization is a central cryptographic assumption and forms the basis of several widely deployed cryptosystems. The best integer factorization algorithm known is the Number Field Sieve [12], which was successfully used to factor 512-bit and 530-bit RSA moduli [5,1]. However, it appears that a PC-based implementation of the NFS cannot practically scale much further, and specifically its cost for 1024-bit composites is prohibitive. Recently, the prospect of using custom hardware for the computationally expensive steps of the Number Field Sieve has gained much attention. While mesh-based circuits for the matrix step have rendered that step quite feasible for 1024-bit composites [3,16], the situation is less clear concerning the sieving step. Several sieving devices have been proposed, including TWINKLE [19,15] and a mesh-based circuit [7], but apparently none of these can practically handle 1024-bit composites. One lesson learned from Bernstein’s mesh-based circuit for the matrix step [3] is that it is inefficient to have memory cells that are ”simply sitting around, twiddling their thumbs” — if merely storing the input is expensive, we should utilize it efficiently by appropriate parallelization. We propose a new device that combines this intuition with the TWINKLElike approach of exchanging time and space. Whereas TWINKLE tests sieve location one by one serially, the new device handles thousands of sieve locations in parallel at every clock cycle. In addition, it is smaller and easier to construct: for 512-bit composites we can fit 79 independent sieving devices on a 30cm single silicon wafer, whereas each TWINKLE device requires a full GaAs wafer. While our approach is related to [7], it scales better and avoids some thorny issues. The main difficulty is how to use a single copy of the input (or a small number of copies) to solve many subproblems in parallel, without collisions or long propagation delays and while maintaining storage efficiency. We address this with a heterogeneous design that uses a variety of routing circuits and takes advantage of available technological tradeoffs. The resulting cost estimates suggest that for 1024-bit composites the sieving step may be surprisingly feasible. Section 2 reviews the sieving problem and the TWINKLE device. Section 3 describes the new device, called TWIRL1 , and Section 4 provides preliminary cost estimates. Appendix A discusses additional design details and improvements. Appendix B specifies the assumptions used for the cost estimates, and Appendix C relates this work to previous ones. 2 Context 2.1 Sieving in the Number Field Sieve Our proposed device implements the sieving substep of the NFS relation collection step, which in practice is the most expensive part of the NFS algorithm [16]. We begin by reviewing the sieving problem, in a greatly simplified form and after appropriate reductions.2 See [12] for background on the Number Field Sieve. The inputs of the sieving problem are R ∈ Z (sieve line width), T > 0 (threshold ) and a set of pairs (pi ,ri ) where the pi are the prime numbers smaller than some factor base bound B. There is, on average, one pair per such prime. Each pair (pi ,ri ) corresponds to an arithmetic progression Pi = {a : a ≡ ri (mod pi )}. We are interested in identifying the sieve locations a ∈ {0, . . . ,R − 1} that are members of many progressions Pi with large pi : X logh pi g(a) > T where g(a) = i:a∈Pi for some fixed h (possibly h > 2). It is permissible to have “small” errors in this threshold check; in particular, we round all logarithms to the nearest integer. In the NFS relation collection step we have two types of sieves: rational and algebraic. Both are of the above form, but differ in their factor base bounds (BR vs. BA ), threshold T and basis of logarithm h. We need to handle H sieve lines, and for sieve line both sieves are performed, so there are 2H sieving instances overall. For each sieve line, each value a that passes the threshold in both sieves implies a candidate. Each candidate undergoes additional tests, for which it is beneficial to also know the set {i : a ∈ Pi } (for each sieve 1 2 TWIRL stands for “The Weizmann Institute Relation Locator” The description matches both line sieving and lattice sieving. However, for lattice sieving we may wish to take a slightly different approach (cf. A.8). 2 separately). The most expensive part of these tests is cofactor factorization, which involves factoring medium-sized integers.3 The candidates that pass the tests are called relations. The output of the relation collection step is the list of relations and their corresponding {i : a ∈ Pi } sets. Our goal is to find a certain number of relations, and the parameters are chosen accordingly a priori. 2.2 TWINKLE Since TWIRL follows the TWINKLE [19,15] approach of exchanging time and space compared to traditional NFS implementations, we briefly review TWINKLE (with considerable simplification). A TWINKLE device consists of a wafer containing numerous independent cells, each in charge of a single progression Pi . After initialization the device operates for R clock cycles, corresponding to the sieving range {0 ≤ a < R}. At clock cycle a, the cell in charge of the progression Pi emits the value log pi iff a ∈ Pi . The values emitted at each clock cycle are summed, and if this sum exceeds the threshold T then the integer a is reported. This event is announced back to the cells, so that the i values of the pertaining Pi is also reported. The global summation is done using analog optics; clocking and feedback are done using digital optics; the rest is implemented by digital electronics. To support the optoelectronic operations, TWINKLE uses Gallium Arsenide wafers which are small, expensive and hard to manufacture compared to silicon wafers, which are readily available. 3 3.1 The New Device Approach We next describe the TWIRL device. The description in this section applies to the rational sieve; some changes will be made for the algebraic sieve (cf. A.6), since it needs to consider only a values that passed the rational sieve. For the sake of concreteness we provide numerical examples for a plausible choice of parameters for 1024-bit composites.4 This choice will be discussed in Sections 4 and B.2; it is not claimed to be optimal, and all costs should be taken as rough estimates. The concrete figures will be enclosed in double angular brackets: hhxiiR and hhxiiA indicate values for the algebraic and rational sieves respectively, and hhxii is applicable to both. We wish to solve H hh≈ 2.7 · 108 ii pairs of instances of the sieving problem, each of which has sieving line width R hh= 1.1 · 1015 ii and smoothness bound B hh= 3.5 · 109 iiR hh= 2.6 · 1010 iiA . Consider first a device that handles one sieve location per clock cycle, like TWINKLE, but does so using a pipelined systolic chain of electronic adders.5 Such a device would consist of a long unidirectional bus, log2 T hh= 10ii bits wide, that connects millions of conditional 3 We assume use of the “2+2 large primes” variant of the NFS [12,13]. This choice differs considerably from that used in preliminary drafts of this paper. 5 This variant was considered in [15], but deemed inferior in that context. 4 3 p1 p2 p3 p4 p5 (a) p1 t p2 t −1 p3 t −2 p4 t −3 t −4 p5 (b) (t ) s +0 (t ) s +1 (t ) s +2 (t ) s +1( s −1) ( t −1 ) s +0 ( t −1 ) s +1 (t −1 ) s +2 (t −1 ) s +1( s −1) ( t −2 ) s +0 ( t −2 ) s +1 (t −2 ) s +2 (t −2 ) s +1( s −1) ( t −3 ) s +0 ( t −3 ) s +1 (t −3 ) s +2 (t −3 ) s +1( s −1) ( t −4 ) s +0 ( t −4 ) s +1 (t −4 ) s +2 (t −4 ) s +1( s −1) Fig. 1: Flow of sieve locations through the device in (a) a chain of adders and (b) TWIRL. adders in series. Each conditional adder is in charge of one progression Pi ; when activated by an associated timer, it adds the value6 blog pie to the bus. At time t, the z-th adder handles sieve location t − z. The first value to appear at the end of the pipeline is g(0), followed by g(1), . . . ,g(R), one per clock cycle. See Fig. 1(a). We reduce the run time by a factor of s hh= 4,096iiR hh= 32,768iiA by handling the sieving range {0, . . . ,R − 1} in chunks of length s, as follows. The bus is thickened by a factor of s to contain s logical lines of log2 T bits each. As a first approximation (which will be altered later), we may think of it as follows: at time t, the z-th stage of the pipeline handles the sieve locations (t − z)s + i, i ∈ {0, . . . ,s − 1}. The first values to appear at the end of the pipeline are {g(0), . . . ,g(s − 1)}; they appear simultaneously, followed by successive disjoint groups of size s, one group per clock cycle. See Fig. 1(b). Two main difficulties arise: the hardware has to work s times harder since time is compressed by a factor of s, and the additions of blog pie corresponding to the same given progression Pi can occur at different lines of a thick pipeline. Our goal is to achieve this parallelism without simply duplicating all the counters and adders s times. We thus replace the simple TWINKLE-like cells by other units which we call stations. Each station handles a small portion of the progressions, and its interface consists of bus input, bus output, clock and some circuitry for loading the inputs. The stations are connected serially in a pipeline, and at the end of the bus (i.e., at the output of the last station) we place a threshold check unit that produces the device output. An important observation is that the progressions have periods pi in a very large range of sizes, and different sizes involve very different design tradeoffs. We thus partition the progressions into three classes according to the size of their pi values, and use a different 6 blog pie denote the value logh pi for some fixed h, rounded to the nearest integer. 4 station design for each class. In order of decreasing pi value, the classes will be called largish, smallish and tiny.7 This heterogeneous approach leads to reasonable device sizes even for 1024-bit composites, despite the high parallelism: using standard VLSI technology, we can fit hh4iiR rationalside TWIRLs into a single 30cm silicon wafer (whose manufacturing cost is about $5,000 in high volumes; handling local manufacturing defects is discussed in A.9). Algebraic-side TWIRLs use higher parallelism, and we fit hh1iiA of them into each wafer. The following subsections describe the hardware used for each class of progressions. The preliminary cost estimates that appear later are based on a careful analysis of all the critical components of the design, but due to space limitations we omit the descriptions of many finer details. Some additional issues are discussed in Appendix A. 3.2 Largish Primes Progressions whose pi values are much larger than s emit blog pie values very seldom. For these largish primes hhpi > 5.2 · 105 iiR hhpi > 4.2 · 106 iiA , it is beneficial to use expensive logic circuitry that handles many progressions but allows very compact storage of each progression. The resultant architecture is shown in Fig. 2. Each progression is represented as a progression triplet that is stored in a memory bank, using compact DRAM storage. The progression triplets are periodically inspected and updated by special-purpose processors, which identify emissions that should occur in the “near future” and create corresponding emission triplets. The emission triplets are passed into buffers that merge the outputs of several processors, perform fine-tuning of the timing and create delivery pairs. The delivery pairs are passed to pipelined delivery lines, consisting of a chain of delivery cells which carry the delivery pairs to the appropriate bus line and add their blog pie contribution. Scanning the progressions. The progressions are partitioned into many hh8,490iiR hh59,400iiA DRAM banks, where each bank contains some d progression hh32 ≤ d < 2.2 · 105 iiR hh32 ≤ d < 2.0 · 105 iiA . A progression Pi is represented by a progression triplet of the form (pi , `i , τi ), where `i and τi characterize the next element ai ∈ Pi to be emitted (which is not stored explicitly) as follows. The value τi = bai /sc is the time when the next emission should be added to the bus, and `i = ai mod s is the number of the corresponding bus line. A processor repeats the following operations, in a pipelined manner:8 1. Read and erase the next state triplet (pi , `i , τi ) from memory. 2. Send an emission triplet (blog pie, `i , τi ) to a buffer connected to the processor. 3. Compute `0 ← (` + p) mod s and τi0 ← τi + bp/sc + w, where w = 1 if `0 < ` and w = 0 otherwise. 4. Write the triplet (pi , `0i , τi0 ) to memory, according to τi0 (see below). 7 These are not to be confused with the ”large” and ”small” primes of the high-level NFS algorithm — all the primes with which we are concerned here are ”small” (rather than ”large” or in the range of “special-q”). 8 Additional logic related to reporting the sets {i : a ∈ Pi } is described in Appendix A.7. 5 Processor Buffer Delivery lines Processor DRAM DRAM Cache Cache Fig. 2: Schematic structure of a largish station. We wish the emission triplet (blog pie, `i , τi ) to be created slightly before time τi (earlier creation would overload the buffers, while later creation would prevent this emission from being delivered on time). Thus, we need the processor to always read from memory some progression triplet that has an imminent emission. For large d, the simple approach of assigning each emission triplet to a fixed memory address and scanning the memory cyclically would be ineffective. It would be ideal to place the progression triplets in a priority queue indexed by τi , but it is not clear how to do so efficiently in a standard DRAM due to its passive nature and high latency. However, by taking advantage of the unique properties of the sieving problem we can get a good approximation, as follows. Progression storage. The processor reads progression triplets from the memory in sequential cyclic order and at a constant rate hhof one triplet every 2 clock cyclesii. If the value read is empty, the processor does nothing at that iteration. Otherwise, it updates the progression state as above and stores it at a different memory location — namely, one that will be read slightly before time τi0 . In this way, after a short stabilization period the processor always reads triplets with imminent emissions. In order to have (with high probability) a free memory location within a short distance of any location, we increase the amount of memory hhby a factor of 2ii; the progression is stored at the first unoccupied location, starting at the one that will be read at time τi0 and going backwards cyclically. If there is no empty location within hh64ii locations from the optimal designated address, the progression triplet is stored at an arbitrary location (or a dedicated overflow region) and restored to its proper place at some later stage; when this happens we may miss a 6 few emissions (depending on the implementation). This happens very seldom,9 and it is permissible to miss a few candidates. Autonomous circuitry inside the memory routes the progression triplet to the first unoccupied position preceeding the optimal one. To implement this efficiently we use a twolevel memory hierarchy which is rendered possibly by the following observation. Consider a largish processor which is in charge of a set of d adjacent primes {pmin , . . . ,pmax }. We set the size of the associated memory to pmax /s triplet-sized words, so that triplets with pi = pmax are stored right before the current read location; triplets with smaller pi are stored further back, in cyclic order. By the density of primes, pmax − pmin ≈ d · ln(pmax ). Thus triplet values are always stored at an address that precedes the current read address by at most d · ln(pmax )/s, or slightly more due to congestions. Since ln(pmax ) ≤ ln(B) is much smaller than s, memory access always occurs at a small window that slides at a constant rate of one memory location every hh2ii clock cycles. We may view the hh8,490iiR hh59,400iiA memory banks as closed rings of various sizes, with an active window “twirling” around each ring at a constant linear velocity. Each sliding window is handled by a fast SRAM-based cache. Occasionally, the window is shifted by writing the oldest cache block to DRAM and reading the next block from DRAM into the cache. Using an appropriate interface between the SRAM and DRAM banks (namely, read/write of full rows), this hides the high DRAM latency and achieves very high memory bandwidth. Also, this allows simpler and thus smaller DRAM.10 Note that cache misses cannot occur. The only interface between the processor and memory are the operations “read next memory location” and “write triplet to first unoccupied memory location before the given address”. The logic for the latter is implemented within the cache, using auxiliary per-triplet occupancy flags and some local pipelined circuitry. Buffers. A buffer unit receives emission triplets from several processors in parallel, and sends delivery pairs to several delivery lines. Its task is to convert emission triplets into delivery pairs by merging them where appropriate, fine-tuning their timing and distributing them across the delivery lines: for each received emission triplet of the form (blog pie, `, τ ), the delivery pair (blog pie, `) should be sent to some delivery line (depending on `) at time exactly τ . Buffer units can be be realized as follows. First, all incoming emission triplets are placed in a parallelized priority queue indexed by τ , implemented as a small mesh whose 9 For instance, in simulations for primes close to hh20,000siiR , the distance between the first unoccupied location and the ideal location was smaller than hh64iiR for all but hh5 · 10−6 iiR of the iterations. The probability of a random integer x ∈ {1, . . . ,x} having k factors is about (log log x)k−1 /(k − 1)! log x. Since we are (implicitly) sieving over values of size about x ≈ hh1064 iiR hh10101 iiA which are “good” (i.e., semi-smooth) with probability p ≈ hh6.8 · 10−5 iiR hh4.4 · 10−9 iiA , less than 10−15 /p of the good a’s have more than 35 factors; the probability of missing other good a’s is negligible. 10 Most of the peripheral DRAM circuitry (including the refresh circuitry and column decoders) can be eliminated, and the row decoders can be replaced by smaller stateful circuitry. Thus, the DRAM bank can be smaller than standard designs. For the stations that handle the smaller primes in the “largish” range, we may increase the cache size to d and eliminate the DRAM. 7 rows are continuously bubble-sorted and whose columns undergo random local shuffles. The elements in the last few rows are tested for τ matching the current time, and the matching ones are passed to a pipelined network that sorts them by `, merges where needed and passes them to the appropriate delivery lines. Due to congestions some emissions may be late and thus discarded; since the inputs are essentially random, with appropriate choices of parameters this should happen seldom. The size of the buffer depends on the typical number of time steps that an emission triplet is held until its release time τ (which is fairly small due to the design of the processors), and on the rate at which processors produce emission triplets hhabout once per 4 clock cyclesii. Delivery lines. A delivery line receives delivery pairs of the form (blog pie, `) and adds each such pair to bus line ` exactly b`/kc clock cycles after its receipt. It is implemented as a one-dimensional array of cells placed across the bus, where each cell is capable of containing one delivery pair. Here, the j-th cell compares the ` value of its delivery pair (if any) to the constant j. In case of equality, it adds blog pie to the bus line and discards the pair. Otherwise, it passes it to the next cell, as in a shift register. Overall, there are hh2,100iiR hh14,900iiA delivery lines in the largish stations, and they occupy a significant portion of the device. Appendix A.1 describes the use of interleaved carry-save adders to reduce their cost, and Appendix A.6 nearly eliminates them from the algebraic sieve. Notes. In the description of the processors, DRAM and buffers, we took the τ values to be arbitrary integers designating clock cycles. Actually, it suffices to maintain these values modulo some integer hh2048ii that upper bounds the number of clock cycles from the time a progression triplet is read from memory to the time when it is evicted from the buffer. Thus, a progression occupies log2 pi + hhlog2 2048ii DRAM bits for the triplet, plus log2 pi bits for re-initialization (cf. A.4). The amortized circuit area per largish progression is Θ(s2 (log s)/pi + log s + log pi ).11 For fixed s this equals Θ(1/pi + log pi ), and indeed for large composites the overwhelming majority of progressions hh99.97%iiR hh99.98%iiA will be handled in this manner. 3.3 Smallish Primes For progressions with pi close to s, hh256 < pi < 5.2 · 105 iiR hh256 < pi < 4.2 · 106 iiA , each processor can handle very few progressions because it can produce at most one emission triplet every hh2ii clock cycles. Thus, the amortized cost of the processor, memory control circuitry and buffers is very high. Moreover, such progression cause emissions so often that communicating their emissions to distant bus lines (which is necessary if the state of each progression is maintained at some single physical location) would involve enormous 11 The frequency of emissions is s/pi , and each emission occupies some delivery cell for Θ(s) clock cycles. The last two terms are due to DRAM storage, and have very small constants. 8 Emitter Emitter Emitter Emitter Funnel Funnel Emitter Funnel Emitter Emitter Emitter Funnel Emitter Funnel Emitter Funnel Emitter Emitter Fig. 3: Schematic structure of a smallish station. communication bandwidth. We thus introduce another station design, which differs in several ways from the largish stations (see Fig 3). Emitters and funnels. The first change is to replace the combination of the processors, memory and buffers by other units. Delivery pairs are now created directly by emitters, which are small circuits that handle a single progression each (as in TWINKLE). An emitter maintains the state of the progression using internal registers, and occasionally emits delivery pairs of the form (blog pie, `) which indicate that the value blog pie should be added to the `-th bus line some fixed time interval later. Appendix A.2 describes a compact emitters design. Each emitter is continuously updating its internal counters, but it creates a delivery √ pair only once per roughly pi (between hh8iiR and hh512iiR clock cycles — see below). It would be wasteful to connect each emitter to a dedicated delivery line. This is solved using funnels, which “compress” their sparse inputs as follows. A funnel has a large number of input lines, connected to the outputs of many adjacent emitters; we may think of it as receiving a sequence of one-dimensional arrays, most of whose elements are empty. The funnel outputs a sequence of much shorter arrays, whose non-empty elements are exactly the non-empty elements of the input array received a fixed number of clock cycle earlier. The funnel outputs are connected to the delivery lines. Appendix A.3 describes an implementation of funnels using modified shift registers. Duplication. The other major change is duplication of the progression states, in order to move the sources of the delivery pairs closer to their destination and reduce the cross√ bus communication bandwidth. Each progression is handled by ni ≈ s/ pi independent emitters12 which are placed at regular intervals across the bus. Accordingly we fragment √ the delivery lines into segments that span s/ni ≈ pi bus lines each. Each emitter is connected (via a funnel) to a different segment, and sends emissions to this segment every 12 √ hhni = s/2 pi ii rounded to a power of 2 (cf. A.2), which is in the range hh{2, . . . ,128}iiR . 9 Emitter Emitter Emitter Fig. 4: Schematic structure of a tiny station, for a single progression. √ pi /sni ≈ p clock cycles. As emissions reach their destination quicker, we can decrease the total number of delivery lines. Also, there is a corresponding decrease in the emission frequency of any specific emitter, which allows us to handle pi close to (or even smaller than) s. Overall there are hh501iiR delivery lines in the smallish stations, broken into segments of various sizes. √ Notes. Asymptotically the amortized circuit area per smallish progression is Θ( (s/ pi + 1) (log s + log pi ) ). The term 1 is less innocuous than it appears — it hides a large constant (roughly the size of an emitter plus the amortized funnel size), which dominates the cost for large pi . 3.4 Tiny Primes For very small primes, the amortized cost of the duplicated emitters, and in particular the related funnels, becomes too high. On the other hand, such progressions cause several emissions at every clock cycle, so it is less important to amortize the cost of delivery lines over several progressions. This leads to a third station design for the tiny primes hhpi < 256ii. While there are few such progressions, their contributions are significant due to their very small periods. Each tiny progression is handled independently, using a dedicated delivery line. The delivery line is partitioned into segments of size somewhat smaller than pi ,13 and an emitter is placed at the input of each segment, without an intermediate funnel (see Fig 4). These emitters are a degenerate form of the ones used for smallish progressions (cf. A.2). Here we cannot interleave the adders in delivery cells as done in largish and smallish stations, but the carry-save adders are smaller since they only (conditionally) add the small constant blog pie. Since the area occupied by each progression is dominated by the delivery lines, it is Θ(s) regardless of pi . Some additional design considerations are discussed in Appendix A. 4 Cost estimates Having outlined the design and specified the problem size, we next estimate the cost of a hypothetical TWIRL device using today’s VLSI technology. The hardware parameters 13 The segment length is the largest power of 2 smaller than pi (cf. A.2). 10 used are specified in Appendix B.1. While we tried to produce realistic figures, we stress that these estimates are quite rough and rely on many approximations and assumptions. They should only be taken to indicate the order of magnitude of the true cost. We have not done any detailed VLSI design, let alone actual implementation. 4.1 Cost of Sieving for 1024-bit Composites We assume the following NFS parameters: BR = 3.5 · 109 , BA = 2.6 · 1010 , R = 1.1 · 1015 , H ≈ 2.7 · 108 (cf. B.2). We use the cascaded sieves variant of Appendix A.6. For the rational side we set sR = 4,096. One rational TWIRL device requires 15,960mm2 of silicon wafer area, or 1/4 of a 30cm silicon wafer. Of this, 76% is occupied by the largish progressions (and specifically, 37% of the device is used for the DRAM banks), 21% is used by the smallish progressions and the rest (3%) is used by the tiny progressions. For the algebraic side we set sA = 32,768. One algebraic TWIRL device requires 65,900mm2 of silicon wafer area — a full wafer. Of this, 94% is occupied by the largish progressions (66% of the device is used for the DRAM banks) and 6% is used by the smallish progressions. Additional parameters of are mentioned throughout Section 3. The devices are assembled in clusters that consist each of 8 rational TWIRLs and 1 algebraic TWIRL, where each rational TWIRL has a unidirectional link to the algebraic TWIRL over which it transmits 12 bits per clock cycle. A cluster occupies three wafers, and handles a full sieve line in R/sA clock cycles, i.e., 33.4 seconds when clocked at 1GHz. The full sieving involves H sieve lines, which would require 194 years when using a single cluster (after the 33% saving of Appendix A.5.) At a cost of $2.9M (assuming $5,000 per wafer), we can build 194 independent TWIRL clusters that, when run in parallel, would complete the sieving task within 1 year. After accounting for the cost of packaging, power supply and cooling systems, adding the cost of PCs for collecting the data and leaving a generous error margin,14 it appears realistic that all the sieving required for factoring 1024-bit integers can be completed within 1 year by a device that cost $10M to manufacture. In addition to this per-device cost, there would be an initial NRE cost on the order of $20M (for design, simulation, mask creation, etc.). 4.2 Implications for 1024-bit Composites It has been often claimed that 1024-bit RSA keys are safe for the next 15 to 20 years, since both NFS relation collection and the NFS matrix step would be unfeasible (e.g., [4,21] and a NIST guideline draft [18]). Our evaluation suggests that sieving can be achieved within one year at a cost of $10M (plus a one-time cost of $20M), and recent works [16,8] indicate that for our NFS parameters the matrix can also be performed at comparable costs. 14 It is a common rule of thumb to estimate the total cost as twice the silicon cost; to be conservative, we triple it. 11 With efficient custom hardware for both sieving and the matrix step, other subtasks in the NFS algorithm may emerge as bottlenecks.15 Also, our estimates are hypothetical and rely on numerous approximations; the only way to learn the precise costs involved would be to perform a factorization experiment. Our results do not imply that breaking 1024-bit RSA is within reach of individual hackers. However, it is difficult to identify any specific issue that may prevent a sufficiently motivated and well-funded organization from applying the Number Field Sieve to 1024bit composites within the next few years. This should be taken into account by anyone planning to use a 1024-bit RSA key. 4.3 Cost of Sieving for 512-bits Composites Since several hardware designs [19,15,10,7] were proposed for the sieving of 512-bit composites, it would be instructive to obtain cost estimates for TWIRL with the same problem parameters. We assume the same parameters as in [15,7]: BR = BA = 224 ≈ 1.7 · 107 , R = 1.8 · 1010 , 2H = 1.8 · 106 . We set s = 1,024 and use the same cost estimation expressions that lead to the 1024-bit estimates. A single TWIRL device would have a die size of about 800mm2 , 56% of which are occupied by largish progressions and most of the rest occupied by smallish progressions. It would process a sieve line in 0.018 seconds, and can complete the sieving task within 6 hours. For these NFS parameters TWINKLE would require 1.8 seconds per sieve line, the FPGA-based design of [10] would require about 10 seconds and the mesh-based design of [7] would require 0.36 seconds. To provide a fair comparison to TWINKLE and [7], we should consider a single wafer full of TWIRL devices running in parallel. Since we can fit 79 of them, the effective time per sieve line is 0.00022 seconds. Thus, in factoring 512-bit composites the basic TWIRL design is about 1,600 times more cost effective than the best previously published design [7], and 8,100 times more cost effective than TWINKLE. Adjusting the NFS parameters to take advantage of the cascaded-sieves variant (cf. A.6) would further increase this gap. However, even when using the basic variant, a single wafer of TWIRLs can complete the sieving for 512-bit composites in under 10 minutes. 4.4 Cost of Sieving for 768-bits Composites We assume the following NFS parameters: BR = 1 · 108 , BA = 1 · 109 , R = 3.4 · 1013 , H ≈ 8.9·106 (cf. B.2). We use the cascaded sieves variant of Appendix A.6, with sR = 1,024 and sA = 4,096. For this choice, a rational sieve occupies 1,330mm2 and an algebraic sieve occupies 4,430mm2 . A cluster consisting of 4 rational sieves and one algebraic sieve can 15 Note that for our choice of parameters, the cofactor factorization is cheaper than the sieving (cf. Appendix A.7). 12 process a sieve line in 8.3 seconds, and 6 independent clusters can fit on a single 30cm silicon wafer. Thus, a single wafer of TWIRL clusters can complete the sieving task within 95 days. This wafer would cost about $5,000 to manufacture — one tenth of the RSA-768 challenge prize [20].16 4.5 Larger composites For largish progressions, the amortized cost per progression is Θ(s2 (log s)/pi + log s + log pi ) with small constants (cf. 3.2). For smallish progressions, the amortized cost is √ Θ( (s/ pi + 1) (log s + log pi ) ) with much larger constants (cf. 3.3). For a serial implementation (PC-based or TWINKLE), the cost per This √ progression is clearly Ω(log pi ). √ means that asymptotically we can choose s = Θ̃( B) to get a speed advantage of Θ̃( B) over serial implementations, while maintaining the small constants. Indeed, we can keep increasing s essentially for free until the area of the largish processors, buffers and delivery lines becomes comparable to the area occupied by the DRAM that holds the progression triplets. For some range of input sizes, it may be beneficial to reduce the amount of DRAM used for largish progressions by storing only the prime pi , and computing the rest of the progression triplet values on-the-fly in the special-purpose processors (this requires computing the roots modulo pi of the relevant NFS polynomial). If the device would exceed the capacity of a single silicon wafer, then as long as the bus itself is narrower than a wafer, we can (with appropriate partitioning) keep each station fully contained in some wafer; the wafers are connected in a serial chain, with the bus passing through all of them. 5 Conclusion We have presented a new design for a custom-built sieving device. The device consists of a thick pipeline that carries sieve locations through thrilling adventures, where they experience the addition of progression contributions in myriad different ways that are optimized for various scales of progression periods. In factoring 512-bit integers, the new device is 1,600 times faster than best previously published designs. For 1024-bit composites and appropriate choice of NFS parameters, the new device can complete the sieving task within 1 year at a cost of $10M, thereby raising some concerns about the security of 1024-bit RSA keys. Acknowledgments. This work was inspired by Daniel J. Bernstein’s insightful work on the NFS matrix step, and its adaptation to sieving by Willi Geiselmann and Rainer Steinwandt. We thank the latter for interesting discussions of their design and for suggesting an 16 Needless to say, this disregards an initial cost of about $20M. This initial cost can be significantly reduced by using older technology, such as 0.25µm process, in exchange for some decrease in sieving throughput. 13 improvement to ours. We are indebted to Arjen K. Lenstra for many insightful discussions, and to Robert D. Silverman, Andrew “bunnie” Huang and Michael Szydlo for valuable comments and suggestions. Early versions of [14] and the polynomial selection programs of Jens Franke and Thorsten Kleinjung were indispensable in obtaining refined estimates for the NFS parameters. References 1. F. Bahr, J. Franke, T. Kleinjung, M. Lochter, M. Böhm, RSA-160, e-mail announcement, Apr. 2003, http://www.loria.fr/~zimmerma/records/rsa160 2. Daniel J. Bernstein, How to find small factors of integers, manuscript, 2000, http://cr.yp.to/papers.html 3. Daniel J. Bernstein, Circuits for integer factorization: a proposal, manuscript, 2001, http://cr.yp.to/papers.html 4. Richard P. Brent, Recent progress and prospects for integer factorisation algorithms, proc. COCOON 2000, LNCS 1858 3–22, Springer-Verlag, 2000 5. S. Cavallar, B. Dodson, A.K. Lenstra, W. Lioen, P.L. Montgomery, B. Murphy, H.J.J. te Riele, et al., Factorization of a 512-bit RSA modulus, proc. Eurocrypt 2000, LNCS 1807 1–17, Springer-Verlag, 2000 6. Don Coppersmith, Modifications to the number field sieve, Journal of Cryptology 6 169–180, 1993 7. Willi Geiselmann, Rainer Steinwandt, A dedicated sieving hardware, proc. PKC 2003, LNCS 2567 254–266, Springer-Verlag, 2002 8. Willi Geiselmann, Rainer Steinwandt, Hardware to solve sparse systems of linear equations over GF(2), proc. CHES 2003, LNCS, Springer-Verlag, to be published. 9. International Technology Roadmap for Semiconductors 2001, http://public.itrs.net/ 10. Hea Joung Kim, William H. Magione-Smith, Factoring large numbers with programmable hardware, proc. FPGA 2000, ACM, 2000 11. Robert Lambert, Computational aspects of discrete logarithms, Ph.D. Thesis, University of Waterloo, 1996 12. Arjen K. Lenstra, H.W. Lenstra, Jr., (eds.), The development of the number field sieve, Lecture Notes in Math. 1554, Springer-Verlag, 1993 13. Arjen K. Lenstra, Bruce Dodson, NFS with four large primes: an explosive experiment, proc. Crypto ’95, LNCS 963 372–385, Springer-Verlag, 1995 14. Arjen K. Lenstra, Bruce Dodson, James Hughes, W. Kortsmit, Paul Leyland, Factoring estimates for 1024-bit RSA modulus, to be published. 15. Arjen K. Lenstra, Adi Shamir, Analysis and Optimization of the TWINKLE Factoring Device, proc. Eurocrypt 2002, LNCS 1807 35–52, Springer-Verlag, 2000 16. Arjen K. Lenstra, Adi Shamir, Jim Tomlinson, Eran Tromer, Analysis of Bernstein’s factorization circuit, proc. Asiacrypt 2002, LNCS 2501 1–26, Springer-Verlag, 2002 17. Brian Murphy, Polynomial selection for the number field sieve integer factorization algorithm, Ph. D. thesis, Australian National University, 1999 18. National Institute of Standards and Technology, Key management guidelines, Part 1: General guidance (draft), Jan. 2003, http://csrc.nist.gov/CryptoToolkit/tkkeymgmt.html 19. Adi Shamir, Factoring large numbers with the TWINKLE device (extended abstract), proc. CHES’99, LNCS 1717 2–12, Springer-Verlag, 1999 20. RSA Security, The new RSA factoring challenge, web page, Jan. 2003, http://www.rsasecurity.com/rsalabs/challenges/factoring/ 21. Robert D. Silverman, A cost-based security analysis of symmetric and asymmetric key lengths, Bulletin 13, RSA Security, 2000, http://www.rsasecurity.com/rsalabs/bulletins/bulletin13.html 22. Web page for this paper, http://www.wisdom.w