To achieve secure cryptographic functionality such as encryption,
signature or authentication, one must rely on computational problems
that are presumed to be hard for the adversary. Alas, we know of no
appropriate problems that are provably hard, and moreover one usually
cannot know the all resources and machinations available to his
adversaries. Thus, we end up making various assumptions about the power
of the adversary and the way he can use this power to attack the
computational challenge. One of the ways in which these assumptions may
fail in practice (thereby compromising the practical security of the
cryptosystem) is when the attacker employs unexpected computational
devices tailored for the specific task. Such devices carry a couple of
advantages for the attacker: first, they can be significantly more
cost-effective than general-purpose computational devices (let alone
manual labor!) due to reduced overheads; and second, they may employ
more efficient algorithms made possible by the flexibility of their
physical construction. Special-purpose devices are not a magic solution
that will crack every problem, but often reduce costs by several orders
of magnitude compared to more traditional alternatives —
which may make the difference between an infeasible problem and one
that is well within reach.

Over time various special-purpose cryptanalytic devices have been
proposed and constructed, often with devastation results for the
security of the cryptosystem being attacked.This page catalogs various
such devices that have appeared in the open literature, classified by
purpose. The list is not exhaustive, and neither are the references;
comments and additions are very welcome.

("The Weizmann Institute Key Locating Engine")*TWINKLE*

First modern sieving device. Never built. Uses non-conventional electro-optical components for analog summation. Not attractive for large (≥768 bit) integers, due to need for large number of support PCs.- Adi
Shamir, Factoring
large numbers with the TWINKLE device,
Cryptographic Hardware and Embedded Systems (CHES) 1999, LNCS 1717,
2-12, Springer, 1999.[SpringerLink] [pdf]

Original proposal, in the context of the Quadratic Sieve. - Arjen K.
Lenstra,
Adi
Shamir, Analysis
and optimization of the TWINKLE factoring Device,
proc. Eurocrypt 2000, LNCS 1807, 35--52, Springer, 2000. [SpringerLink]

Analysis for the Number Field Sieve with 512-bit and 768-bit composites and lattice sieving. Design optimizations and variants.

- Adi
Shamir, Factoring
large numbers with the TWINKLE device,
Cryptographic Hardware and Embedded Systems (CHES) 1999, LNCS 1717,
2-12, Springer, 1999.[SpringerLink] [pdf]
- Mesh-based sieving

A class of highly-parallel electronic sieving devices based on mesh sorting or routing. Adapt ideas of D. J. Bernstein from the NFS linear algebra (see below) to sieving. Never built. Feasible cost for 1024-bit composites.- Willi Geiselmann, Rainer Steinwandt, A
dedicated sieving hardware,
proc. Public Key Cryptography (PKC) 2003, LNCS 2567, 254-266,
Springer, 2003. [SpringerLink]

Original proposal. Never built. - Willi Geiselmann, Rainer Steinwandt,Yet another sieving device, proc. CT-RSA 2004, LNCS 2964, 278--291, Springer, 2004. [pdf](extended version)

Extensive optimization and analysis for 768-bit composites. Never built.

- Willi Geiselmann, Rainer Steinwandt, A
dedicated sieving hardware,
proc. Public Key Cryptography (PKC) 2003, LNCS 2567, 254-266,
Springer, 2003. [SpringerLink]
- Pipelined sieving

A class of highly-parallel electronic sieving devices based on (essentially) unidirectional information flows and processing.("The Weizmann Institute Relation Locator")*TWIRL*

Highly-parallel electronic sieving device. Never built. Uses a pipelined architecture different from mesh-based sieving, with a lower cost. Never built. Feasible cost for 1024-bit composites.- Adi
Shamir, Eran Tromer,
, proc. Crypto 2003, LNCS 2729, 1-26, Springer, 2003. [pdf]*Factoring large numbers with the TWIRL device*

Original proposal.

- Arjen K.
Lenstra, Eran
Tromer, Adi Shamir, Wil Kortsmit, Bruce Dodson, James Hughes, Paul
Leyland,
, proc. Asiacrypt 2003, Springer, LNCS 2894, 331--346, Springer, 2003 [pdf]*Factoring estimates for a 1024-bit RSA modulus*

Analysis of Number Field Sieve parameters used in original proposal, and of cost with more recent (90nm) chip manufacturing technology.

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

Abridged and more accessible version of the original proposal.

- Adi
Shamir, Eran Tromer,
- Willi Geiselmann, Rainer Steinwandt, Non-Wafer-Scale Sieving Hardware for the NFS: Another Attempt to Cope with 1024-bit,
proc. EUROCRYPT 2007, LNCS 4515, 466-481, Springer, 2007. [SpringerLink]
[slides (pdf)]

Removes the need for full-wafer circuits, in favor of a network of smaller chips (at a silicon cost increase of x2.5-3). Never built.

*CAIRN 2*

Tetsuya Izu,, Jun Kogure, Takeshi Shimoyama, CAIRN 2: An FPGA Implementation of the Sieving Step in the Number Field Sieve Method , proc. Cryptographic Hardware and Embedded Systems (CHES) 2007, LNCS 4727, 364-377, Springer, 2007. [SpringerLink]

FPGA implementation following a similar approach. Built and used to perform the sieving for a 423-bit Special Number Field Sieve instance in 30 days. Claims scalability up to 768-bit composites (in terms of memory requirements), though performance is not analyzed.

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-

- Jens Franke, Thorsten Kleinjung, Christof Paar, Jan Pelzl, Christine Priplata, Colin Stahlke, SHARK — a realizable special hardware sieving device for factoring 1024-bit integers, proc. Workshop on Special Purpose Hardware for Attacking Cryptographic Systems (SHARCS) 2005, February 2005. [paper (pdf)] [slides (pdf)]

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

- Employing mechanical devices for the sieving task was apparently first proposed by Frederick William Lawrence in 1896.
- Frederick William Lawrence, Factorisation of numbers, Quarterly Journal of Pure and Applied Mathematics, vol. 28, 285--311, 1896
- In 1912, following the publication of a French translation of the
above, three
prototype devices were independently built by André
Gérardi (the translator),
Maurice Kraitchik, and by Pierre and Eugène Olivier Carissan.
These three devices were rough prototypes that relied on a human
observer and suffered from mechanical difficulties.

- Jeffrey Shallit, Hugh C. Williams, François Morain, Discovery of a lost factoring machine, The Mathematical Intelligencer, vol. 17 no. 3, 41-47, 1995. [web page] [slides (ps)]
*Machine á Congruences*

This device, built by Eugène Olivier Carissan in 1919 as an improvement upon his brother's earlier design, is the first known sieving machine that operated successfully. It consists of 14 concentric brass rings, and employs electrical switches to identify events corresponding to (likely) squares in the Fermat method. It presently resides at the Conservatoire Nationale des Arts Métiers, Paris.

- Jeffrey Shallit, Hugh C. Williams, François Morain, Discovery of a lost factoring machine, The Mathematical Intelligencer, vol. 17 no. 3, 41-47, 1995. [web page] [slides (ps)]

- Lehmer's mechanical sieves

In the 1920's and 1930's, D. N. Lehmer and D. H. Lehmer built several mechanical sieving devices, employing various approaches: bicycle chains (1926, replica at the Computer History Museum), gears and photoelectric detectors (1932, presently at the Computer History Museum) and movie films (1936). In the 1970's, D. H. Lehmer also built electronic sieving devices using delay lines and shift registers (1970's).- D. N. Lehmer, Hunting big game in the theory of numbers, Scripta Mathematica I, 229-235, September

- [html]

- D. H. Lehmer, A photo-electric number sieve, American Mathematical Monthly, vol. 40, 401-406, 1933
- D. H. Lehmer, The mechanical combination of linear forms, The American Mathematical Monthly, vol. 35, 114--121, 1928. a href="http://ed-thelen.org/comp-hist/Lehmer-NS-01.html"[html]
- Michael R. Williams, Lehmer Sieves, in Ed Thelen, Facts and stories about
Antique (lonesome) Computers. a
href="http://ed-thelen.org/comp-hist/Mike-Williams-Lehmer.html"[html]

- Ed Thelen, Lehmer Factoring Machines, in Ed Thelen, Facts and stories about Antique (lonesome) Computers. a href="http://ed-thelen.org/comp-hist/lehmer-sieve-photoelectric.html"[web site]
*Extended Precision Operand Computer*, AKA*"Georgia Cracker"*

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).- Jeffrey W. Smith, Samuel S. Wagstaff, Jr., An extended precision
operand computer, proc. 21st Southeast Region. ACM Conference, 209-216, 1983

- Carl Pomerance,
Jeffrey W. Smith, Samuel S. Wagstaff, Jr., New
ideas for factoring large integers, proc. CRYPTO'83, Plenum
Press, 81--85, 1984

**"A High Performance Factoring Machine"**

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.- W. G. Rudd, Duncan
A. Buell, Donald M. Chiarulli, A high performance
factoring machine, proc. 11th International Conference on
Computer Architecture, 297-300, ACM, 1983.

("quadratic sieve motor")*Quasimodo*

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.

- Carl Pomerance, Jeffrey W. Smith, Randy Tuler, A pipeline architecture for factoring large integers with the quadratic sieve algorithm, SIAM Journal on Computing, vol. 17, 387-403, 1988. a href="http://locus.siam.org/SICOMP/volume-17/art_0217023.html"[pdf]
- Carl Pomerance, A Tale of Two Sieves,
Notices of the AMS, 1473-1485, 1996 a
href="http://www.ams.org/notices/199612/pomerance.pdf"[pdf]

**Mesh-based**- Daniel J. Bernstein, Circuits for Integer Factorization: a Proposal, manuscript,
- [pdf]

Observed that the NFS linear algebra step has a huge input that is accessed repeatedly. When implemented on traditional computers, very few (often one) processors are accessing that huge input, which is inherently inefficient -- at any moment, most of the storage is idle. Also makes related observations on the NFS sieving step (see above). Proposed an implementation using mesh sorting, which reduces the asymptotic cost. Design given on a abstract level; subsequent analysis (see below) shows that a naive implementation would have prohibitive cost for 1024-bit composites. - Arjen K.
Lenstra, Adi
Shamir, Jim Tomlinson, Eran Tromer,
, proc. Asiacrypt 2002, LNCS 2501, 1-26, Springer, 2002. a href="http://theory.csail.mit.edu/~tromer/papers/meshc.pdf"[pdf]*Analysis of Bernstein's factorization circuit*

Analyzed the above paper by Bernstein, asymptotically and concretely. Proposed an alternative concrete design that improves efficiency by various algorithmic and technological means. High-level parallel, wafer-scale electronic device consisting of an array of cells, executing mesh routing. Feasible cost, but technologically challenging, for 1024-bit composites. A variant prototyped on FPGA (see below). - Willi
Geiselmann, Rainer
Steinwandt, Hardware
to solve sparse systems of linear equations over GF(2),
Cryptographic Hardware and Embedded Systems (CHES) 2003, LNCS 2779,
51--61, Springer, 2003. a
href="http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2779&spage=51"[SpringerLink]

Improves the above by adding splitting into smaller and semi-independent chips. This variant was prototyped on FPGA:

Kris Gaj, Tarek El-Ghazawi,`<li><span class="bib">Sashisu Bajracharya, Deapesh Misra,`

Field Programmable Technology (FPT) 2004, December 2004. a href="http://cpe02.gmu.edu/rcm/publications/FPT_2004.pdf"[pdf]*Reconfigurable hardware implementation of mesh routing in number field sieve factorization*

- Willi
Geiselmann, Hubert
Köpfer, Rainer Steinwandt, Eran Tromer,
, proc. International Conference on Information Technology (ITCC) 2005, to appear. a href="http://theory.csail.mit.edu/~tromer/papers//lawrap.pdf"[pdf]*Improved routing-based linear algebra for the Number Field Sieve*

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

- Willi Geiselmann, Adi
Shamir, Rainer Steinwandt, Eran Tromer,
, preliminary version, March 2005. [pdf]*Scalable Hardware for Sparse Systems of Linear Equations, with Applications to Integer Factorization*

Highly-parallel electronic device, based on a pipelined architecture (reminiscent of the TWIRL sieving device). More efficient than the above mesh-based devices, and more technologically feasible due to smaller chips and better scalability. Feasible cost for 1024-bit composites. Never built.

- Willi Geiselmann, Adi
Shamir, Rainer Steinwandt, Eran Tromer,
- Dan Bernstein, Factorization myths, talk at Algorithmic Number Theory Symposium (ANTS) VI, June 2004. a href="http://cr.yp.to/talks.html#2004.06.14"[slides and transcript]
- Richard P. Brent, Factorization of the
tenth and eleventh Fermat numbers, Report TR-CS-96-02, Computer
Sciences Laboratory, Australian National University, Canberra, 1996. a
href="ftp://nimbus.anu.edu.au/pub/Brent/rpb161tr.dvi.gz"[paper
(dvi.gz)]

This is mostly a conventional PC-based implementation of the Number Field Sieve, but uses the Dubner Cruncher digital signal processing accelerator (an ISA card) for fast large integer multiplication.

- Jens Franke, Thorsten
Kleinjung, Christof Paar, Jan Pelzl, Christine Priplata, Martin
Šimka,
Colin Stahlke, An
efficient hardware architecture for factoring integers with the
Elliptic Curve Method,
proc. Workshop on Special Purpose Hardware for Attacking
Cryptographic
Systems (SHARCS) 2005, February 2005. a
href="http://www.crypto.ruhr-uni-bochum.de/imperia/md/content/texte/publications/conferences/ecm.pdf"[paper
(pdf)] a
href="http://www.ruhr-uni-bochum.de/itsc/tanja/SHARCS/talks/ECM.pdf"[slides
(pdf)]

A compact hardware design for the ECM algorithm, allowing highly parallel implementations. Implemented on FPGA+microcontroller, and cost of an ASIC implementationis estimated. Application to Number Field Sieve (and specifically, the SHARK device above) is discussed. - Giacomo de Meulenaer, François Gosset, Guerric Meurice de Dormale, Jean-Jacques Quisquater, Integer Factorization Based on Elliptic Curve Method: Towards Better Exploitation of Reconfigurable Hardware, IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM07), 197--207, IEEE Computer Society Press, 2007
[IEEExplore]

```
<li><span class="bib">Sashisu Bajracharya, Deapesh Misra,
```

Kris Gaj, Tarek El-Ghazawi, (Revision of the earlier paper above.)

- Hypothetical DES cracking via
custom ASICs

- Michael J. Wiener, Efficient DES Key Search, presented at the rump session of Crypto '93, reprinted in Practical Cryptography for Data Internetworks, W. Stallings, editor, IEEE Computer Society Press, pp. 31-79, 1996 [on-line]
- Michael J. Wiener, Efficient DES Key Search — an update, CryptoBytes, vol. 3 no. 2, 6-8, RSA Laboratories [on-line]

- M. Blaze, W. Diffie, R. Rivest, B. Schneier, T.
Shimomura, E. Thompson, M. Weiner, Minimal Key
Lengths for Symmetric Ciphers to Provide Adequate Commercial Security —
A Report by an Ad Hoc Group of Cryptographers and Computer Scientists,
1996 [on-line]

Cost estimate exhaustive search for custom ASIC-based devices, FPGA-based devices, and distributed computing. - DES Cracker

Electronic Frontier Foundation, Cracking DES, O'Reilly, 1998 [on-line] [web site] [sourcecode]

Broke 56-bit DES keys in a few days by exhaustive search using 36,864 custom-produced ASIC chips. Built by the Electronic Frontier Foundation in 1998 for under US$ 250K.

- Bomba

[Wikipedia]

Electro-mechanical computers for breaking the German cipher Enigma. Built by Polish General Staff's Cipher Bureau in 1938 and successfully broke encryptions employing the basic variant of Enigma. - Bombe

Donald Davies, The Bombe — a Remarkable Logic Machine, Cryptologia, vol. 23 no. 2, 108-138, April 1999 [online]

[Wikipedia] [Jerry Proc]

Electro-mechanical computers for breaking advanced variants of the German cipher Enigma. Built by the British Government Codes & Ciphers School at Bletchley Park (via British Tabulating Machine Company) during 1940-1945. Over Over 200 such machines were built and and operated with great success.

- Heath
Robinson
and Colossus

Tony Sale, Lorenz ciphers and the Colossus [web site]

[Wikipedia]

Electro-mechanical computers for breaking the German cipher Lorenz. Built by the British Government Codes & Ciphers School at Bletchley Park (via the British Post Office's research center) circa 1943. Overall 10 such machines were built and operated with great success. Rebuilt from 1994 by Tony Sale and the Colossus Team.

This list is not exhaustive, and neither are the references; comments and additions are very welcome.

Acknowledgments. In the description of the historical sieving devices, I have made extensive use of material composed by Arjen K. Lenstra and Jeffrey Shallit. All errors are, of course, my own.