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:
Another account, more accessible but shorter on details, was published here: 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:

Presentations

The following presentation slides discuss TWIRL, as well as hardware for the other main step of the Number Field Sieve algorithm:
For a shorter version which focuses on TWIRL, see:
A more recent survey of hardware for the Number Field Sieve sieving step:

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:

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.
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) = 1719304894236345143401011418080x5 -6991973488866605861074074186043634471x4 +27086030483569532894050974257851346649521314x3 +46937584052668574502886791835536552277410242359042x2 -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