The TWIRL integer factorization device

TWIRL (The Weizmann Institute Relation Locator) is an electronic device for factoring of large integers. It implements the sieving step of the Number Field Sieve integer factorization algorithm, which is in practice the most expensive step in factorization. TWIRL is more efficient than previous designs by several orders of magnitude, due to high algorithmic parallelization combined with adaptation to technological hardware constraints. Although fairly detailed, the design remains hypothetical since the device has not been actually built. However, projected cost estimates suggest that if TWIRL is built using current VLSI technology, it will be possible to factor 1024-bit integers, and hence to break 1024-bit RSA keys, in 1 year at the cost of a few dozen million US dollars (or significantly less, if several integers are to be factored simultaneously).

Papers

TWIRL is described in the following paper:

Adi Shamir, Eran Tromer, Factoring Large Numbers with the TWIRL Device, proc. Crypto 2003, LNCS 2729, 1-26, Springer-Verlag, 2003
[ps.gz] [pdf]

Another account, more accessible but shorter on details, was published here:

Adi Shamir, Eran Tromer, On the cost of factoring RSA-1024, RSA CryptoBytes, vol. 6 no. 2, 10-19, 2003
[ps.gz] [pdf]

For analysis of several technical aspects (choice of NFS polynomial, sieve yield and frequency of candidates), and for updated figures reflecting more recent VLSI technology, see the following:

Arjen K. Lenstra, Eran Tromer, Adi Shamir, Wil Kortsmit, Bruce Dodson, James Hughes, Paul Leyland, Factoring estimates for a 1024-bit RSA modulus, proc. Asiacrypt 2003, Springer-Verlag, to appear.
[ps.gz] [pdf]

Presentations

The following presentation slides discuss TWIRL, as well as hardware for the other main step of the Number Field Sieve algorithm:

Hardware-Based Implementations of Factoring Algorithms, invited talk at ECC 2003.
[PowerPoint XP] [PDF without animated illustrations]

For a shorter version which focuses on TWIRL, see:

Factoring Large Numbers with the TWIRL Device, presentation of paper at Crypto 2003.
[PowerPoint XP] [PDF without animated illustrations]

A more recent survey of hardware for the Number Field Sieve sieving step:

Adi Shamir, Eran Tromer, Special-purpose hardware for factoring: the NFS sieving step, proc. Workshop on Special Purpose Hardware for Attacking Cryptographic Systems (SHARCS), 2005.
[PowerPoint XP] (slides)
[pdf] [ps.gz] (paper)

Linear algebra step

TWIRL addresses the sieving (relation collection) step of the Number Field Sieve. Our proposed architectures for the other major step on the Number Field Sieve, namely the matrix (linear algebra) step, are addressed in the following papers and presentations:

Willi Geiselmann, Adi Shamir, Rainer Steinwandt, Eran Tromer, Scalable hardware for sparse systems of linear equations, with applications to integer factorization, proc. CHES 2005, LNCS 3659, 131--146, Springer, 2005
[pdf] [ps.gz]
Willi Geiselmann, Hubert Köpfer, Rainer Steinwandt, Eran Tromer, Improved routing-based linear algebra for the Number Field Sieve, proc. International Conference on Information Technology: Coding and Computing (ITCC'05), Volume 1, 636-641, IEEE, 2005
[pdf] [ps.gz]

Other cryptanalytic hardware

See Special-Purpose Cryptanalytic Devices.

Difference from drafts

A preliminary draft of the TWIRL paper was circulated on Feb. 2003 (and marked as such). The major changes between the preliminary draft and the final version (which appears above and in the conference proceeding) are as follows.

The extrapolations were replaced by analysis of semi-smoothness probabilities for concrete NFS polynomials. Accordingly, different NFS sieving parameters are now assumed. The smoothness bounds are much larger, the sieve region is somewhat smaller and 2+2 large primes are used. This is briefly discussed in Appendix B.2; a more detailed writeup is due, and will appear here.
For these parameters, cofactor factorization is not a problem (end of Appendix A.7).
Improvement: the algebraic sieves consider only the sieve locations that passed the rational sieves. This makes the algebraic-side bus much narrower, thereby allowing greater parallelization and a higher algebraic smoothness bound (Appendix A.6).
The accumulated logarithms are now represented using 10 bits rather than 6, to increase accuracy.
All costs were re-evaluated in light of the above, and various parameters were optimized.
The bottom line for 1024-bit composites is unchanged: 10M $ x year.

In addition, there are numerous minor improvements and clarifications.

NFS polynomials for RSA-1024

The RSA-1024 NFS polynomials mentioned in the paper are given below, for your copy&paste convenience.

f (x) = 1719304894236345143401011418080x⁵ -6991973488866605861074074186043634471x⁴ +27086030483569532894050974257851346649521314x³ +46937584052668574502886791835536552277410242359042x² -101070294842572111371781458850696845877706899545394501384x -22666915939490940578617524677045371189128909899716560398434136

g(x) = 93877230837026306984571367477027x -37934895496425027513691045755639637174211483324451628365

m = 2626198687912508027781823689041581872398105941296246738850076103682306 1967405529250615451338729866356088714618385497519816050227824324506707 4820593711054723850570027395756140011420203134807117903732061718812827 3668251667044346501282228160838716940928246913831125952039276984310498 5793744494821437272961970486

n = 1350664108659952233496032162788059699388814756056670275244851438515265 1060485953383394028715057190944179820728216447155137368041970396419174 3046496589274256239341020864383202110372958725762358509643110564073501 5081875106765946292055636855294752135008528794163773285339061097505443 34999811150056977236890927563

This fulfills f(m)=g(m)=0 (mod n), where n is the RSA-1024 challenge number. These polynomials were found using the NFS polynomial generation programs of Jens Franke and Thorsten Kleinjung (with minor adaptations).

-- Eran Tromer