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).

- Adi Shamir, Eran Tromer,
, proc. Crypto 2003, LNCS 2729, 1-26, Springer-Verlag, 2003*Factoring Large Numbers with the TWIRL Device*

[ps.gz] [pdf]

- Adi Shamir, Eran Tromer,
, RSA CryptoBytes, vol. 6 no. 2, 10-19, 2003*On the cost of factoring RSA-1024*

[ps.gz] [pdf]

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

[ps.gz] [pdf]

- Hardware-Based
Implementations of Factoring Algorithms, invited talk at ECC
2003.

[PowerPoint XP] [PDF without animated illustrations]

, presentation of paper at Crypto 2003.*Factoring Large Numbers with the TWIRL Device*

[PowerPoint XP] [PDF without animated illustrations]

- Adi Shamir, Eran Tromer,
, proc. Workshop on Special Purpose Hardware for Attacking Cryptographic Systems (SHARCS), 2005.*Special-purpose hardware for factoring: the NFS sieving step*

[PowerPoint XP] (slides)

[pdf] [ps.gz] (paper)

- Willi Geiselmann, Adi Shamir, Rainer Steinwandt, Eran Tromer,
, proc. CHES 2005, LNCS 3659, 131--146, Springer, 2005*Scalable hardware for sparse systems of linear equations, with applications to integer factorization*

[pdf] [ps.gz] - Willi Geiselmann, Hubert Köpfer, Rainer Steinwandt, Eran Tromer,
, proc. International Conference on Information Technology: Coding and Computing (ITCC'05), Volume 1, 636-641, IEEE, 2005*Improved routing-based linear algebra for the Number Field Sieve*

[pdf] [ps.gz]

- 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.

f (x) = 1719304894236345143401011418080x^{5} -6991973488866605861074074186043634471x^{4} +27086030483569532894050974257851346649521314x^{3} +46937584052668574502886791835536552277410242359042x^{2} -101070294842572111371781458850696845877706899545394501384x -22666915939490940578617524677045371189128909899716560398434136g(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).