Abstracts of invited talks
- 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.