**Dan Bernstein**(University of Illinois at Chicago)

*Building circuits for integer factorization*

Abstract:

"I'll present my latest work on {\it verifiable\/} upper bounds for the money and time needed to factor 1024-bit integers. One important observation is that the switch from conventional computers to mesh computers produces even larger gains for the elliptic-curve method than for the number-field sieve."

**Arjen Lenstra**(Lucent Technologies)

*Actual and proposed special purpose hardware devices for integer factorization*

Abstract:

Special purpose hardware devices for integer factorization have a long and interesting history. Of the many proposed devices several were actually built, and some of those have even successfully factored integers! In this talk some of the actual and most of the currently contemplated devices will be discussed, including a comparison of their expected performance.

**Jean-Jacques Quisquater**(Universite Catholique de Louvain)

*Exhaustive Key Search of the DES: Updates and Refinements*

Abstract:

Exhaustive key search is the simplest attack against a cryptosystem, but it is sometimes the most realistic. This is specially true for carefully designed block ciphers for which advanced cryptanalysis (e.g. linear, differential) is not applicable. In this paper, we first update the cost of an exhaustive key search of the Data Encryption Standard (DES) using Field Programmable Gate Arrays (FPGAs). Then we illustrate how a time-memory tradeoff attack can be mounted for a similar cost, with much more dramatic consequences.

(Joint work with Francois-Xavier Standaert)**Anthony E. Sale**(Hon FBCS leader of the Colossus Rebuild Project)

*The First Digital Electronic Code Cracker?*

The rebuilt and working WW II Colossus Mk 2 electronic computer.

Abstract:

Tony Sale will describe the highly successful Bletchley Park attack on the Lorenz telegraphic cipher used by the German High Command in World War II. This led to the design by Dr Tommy Flowers, of the electronic valve code breaking computer, Colossus. Eventually 10 Mk 2 Colossi were built and working in Bletchley Park by 1945.

Tony will then describe the rebuilding, over 10 years, of a 2,500 valve Mk 2 Colossus from minimal information, getting it actually working and breaking ciphers just as it did in WW II. He will end by showing a video of the rebuilt Colossus actually breaking a cipher text.

Web site: www.codesandciphers.org.uk**Adi Shamir**(Weizmann Institute)

*Special-Purpose Hardware for Factoring: the NFS Linear Algebra Step*

Abstract:

The best factoring algorithm for RSA keys is the Number Field Sieve, which has two main steps: A sieving step which finds many smooth numbers along with their factorizations, and a linear algebra step which finds a relationship between these factorizations. The most common implementation of the linear algebra step uses Wiedemann's algorithm which computes the product of successive powers of a sparse matrix A and a random vector V. In July 2002 D. Bernstein proposed an efficient implementation of this algorithm using a two dimensional sorting network. In this talk I'll describe an improved implementation which uses a two dimensional routing network, and compare several variants of each approach. (Joint work with Eran Tromer).**Rainer Steinwandt**(Universität Karlsruhe)

*A systolic design for supporting Wiedemann's algorithm*

Abstract:

The talk discusses a systolic hardware design for supporting matrix-by-vector multiplications as occurring in Wiedemann's algorithm for computing kernel vectors of a sparse matrix over a finite field. Unlike recent hardware proposals that have been made for computations over GF(2) to speed up the linear algebra step of the NFS, the design considered in the talk is not based on the use of a sorting- or routing-mesh. In addition to GF(2) also small prime fields GF(*p*) with*p*>2 are considered. (Joint work with Willi Geiselmann, Adi Shamir and Eran Tromer)**Eran Tromer**(Weizmann Institute)

*Special-Purpose Hardware for Factoring: the NFS Sieving Step*

Abstract:

In the quest for the factorization of larger integers, the present bottleneck is the sieving step of the Number Field Sieve algorithm. Several special-purpose hardware architectures have been proposed for this step: TWINKLE (based on electro-optics), mesh circuits (based on two-dimensional systolic arrays) and TWIRL (based on parallel processing pipelines). This talk will review these architectures, and their various approaches to exploiting the flexibility of custom hardware. (Joint work with Adi Shamir)**Michael Wiener**

*Cryptanalytic Hardware Architecture Optimized for Full Cost*

Abstract:

Traditionally, attack costs are measured in total processor time, but we get a more accurate picture by including costs related to other components such as memory. We call this measure of attack cost the "full" cost. We present a cryptanalytic architecture whose full cost is asymptotically optimal for a broad range of cryptanalytic attacks, from discrete logarithms and factoring to meet-in-the-middle attacks on multiple encryption and hash functions. In some cases the optimized full cost works out to be the same as the optimized traditional processor cost, but in other cases the optimal attack based on only the processor cost cannot be achieved when the full cost of all components is considered.