Highly-parallel electronic sieving device. Differs from TWIRL in its use of a butterfly routing network, use of standard-sized chips, and being tailored for special-qsieving. Cost evaluated for 1024-bit composites. The predicted cost is higher than TWIRL's ($200M vs. $1.1M for 1024-bit composites in 1 year), but the technological challenges differ.
Sieving (historical)The sieving task used in number-theoretical algorithms (ranging from Eratosthenes's algorithm to finding prime to the Number Field Sieve) has a very regular structure, which can be exploited by automated mechanical or electronic means. During the last century, various such devices and been devised and built. These first such devices were used for factorization using Fermat's method, where the goal of sieving is to identify squares in an arithmetic progression by testing quadratic residuosity modulo various small primes. Later, similar sieving tasks arose in newer factoring algorithms such Continued Fraction and the Quadratic Sieve. These devices all predate the Number Field Sieve, but in principle they could be applied to it as well. In the following, we briefly survey various documented special-purpose sieving devices which are of historical interest.
This is a 128-bit, highly parallel special-purpose computer for factoring using the Continued Fraction method, built by Jeffrey Smith and Samuel Wagstaff in 1982-3 (presently held by Jeffrey Smith).
This is a 256-bit general-purpose computer designed by W. Rudd, D. A. Buell and D. M. Chiarull. It was to perform factorization 10 times faster than existing general-purpose computers, with a low construction cost.
This device, designed by C. Pomerance, J. W. Smith and R. Tuler, was built but never functioned properly and was superceded by the arrival of efficient general-purpose computers. It has been dismantled and its current whereabouts are unknown.
Linear Algebra Step of the Number Field Sieve
Kris Gaj, Tarek El-Ghazawi, Reconfigurable hardware implementation of mesh routing in number field sieve factorizationSpecial Purpose Hardware for Attacking Cryptographic Systems (SHARCS) 2005, February 2005. a href="http://cpe02.gmu.edu/rcm/publications/SHARCS_2005_paper.pdf"[extended abstract (pdf)] a href="http://cpe02.gmu.edu/rcm/publications/SHARCS_2005_talk.pdf"[slides (pdf)]
<li><span class="bib">Sashisu Bajracharya, Deapesh Misra,
(Revision of the earlier paper above.)
Points out, and resolve heuristically, pathological cases in the routing algorithm used by the two devices above. Suggest some improvements. Never built, but similar to the above FPGA prototype.
Elliptic Curve MethodThe ECM factoring algorithm can be used as a stand-alone factoring algorithm, but for factoring large RSA composites it is of interest mainly as a component in the relation collection step of the Number Field Sieve. In the latter, there is a trade-off between the amount of sieving (discussed above) and the amount of subseqent ECM-based smoothness testing; most past proposals chose parameters that make the cost of the smoothness testing negligible compared to that of the sieving, but this is suboptimal asymptotically and probably also concretely (if special-purpose hardware are used for both). The latter point is argued in the following:Proposed special-purpose ECM devices:Beyond these direct works, there is also extensive literature about efficient hardware implementation of elliptic curve arithematic, and much of it is applicable also in the cryptanalytic context of factoring via ECM.
Exhaustive Key Search
World War II CiphersToday special-purpose cryptanalytic devices are an exotic and often-ignored possibility, but in the dawn of computing, computational resources were so limited that special-purpose devices were the only feasible way to carry out useful tasks. One may even say that these devices
the dawn of computing, in the sense of providing motivation and experience for the subsequent construction of general-purpose computers. Several such devices were built and fruitfully employed by the Allies during the 2nd World War:
This list is not exhaustive, and neither are the references; comments and additions are very welcome.
In the description of the historical sieving devices, I have made extensive use of material composed