Date: Wed, 05 May 1999 15:10:40 -0500
From: Bruce Schneier <schneier@counterpane.com>
Subject: Israeli scientist reports discovery of advance in code breaking

Factoring with TWINKLE

At Eurocrypt '99, Adi Shamir presented a new machine that could increase our
factoring speed by about 100-1000 times.  Called TWINKLE (The Weizmann
INstitute Key Locating Engine), this device brings 512-bit keys within the
realm of our ability to factor.

The best factoring algorithms known to date all work on similar principles.
First, there is a massive parallel search for equations with a certain
relation.  This is known as the sieving step.  Then, after a certain number
of relations are found, there is a massive matrix operation to solve a
linear equation and produce the prime factors.  The first step can easily be
paralleled--recently, 200 computers worked in parallel for about four weeks
to find relations to help factor RSA-140--but the second has to be done on a
single supercomputer: it took a large Cray about 100 hours and 810 Mbytes of
memory to factor RSA-140.

Shamir conceptualized a special hardware device that uses electro-optical
techniques to sieve at speeds much faster than normal computers.  He
encodes various LEDs with values corresponding prime numbers, and then uses
it to factor numbers.  The machine reminds me of the famous Difference
Engine of the 1800s.  Once the engineering kinks are worked out--and there
are considerable ones--this machine will be as powerful as 100-1000 PCs for
about $5000.  The basic idea is not new; a mechanical-optical machine built
by D.H. Lehmer in the 1930s did much the same thing (although quite a bit
slower).

As far as we know, Shamir's machine is never been built.  (I can't speak
for secret organizations.)  As I said, Shamir presented a conceptualization
and a sketch of a design, not a full set of engineering blueprints.  There
are all sorts of details still to be figured out, but none of them seem
impossible.  If I were running a multi-billion dollar intelligence
organization, I would turn my boffins loose at the problem.

The important thing to note is that this new machine does not affect the
matrix step at all.  And this step explodes in complexity for large
factoring problems; its complexity grows much faster than the complexity of
the sieving step.  And it's not just the time, it's the memory
requirements.  With a 1024-bit number, for example, the matrix step
requires something like ten terabytes of memory: not off-line storage, but
real computer memory.  No one has a clue how to solve that kind of problem.

This technique works just as well for discrete-logarithm public-key
algorithms (Diffie-Hellman, ElGamal, DSA, etc.) as it does for RSA.
(Although it is worth noting that the matrix problem is harder for
discrete-log problems than it is for factoring.)  The technique does not
apply to elliptic-curve-based algorithms, as we don't know how to use the
sieving-based algorithms to solve elliptic-curve problems.

In Applied Cryptography, I talked about advances in factoring coming from
four different directions.  One, faster computers.  Two, better networking.
Three, optimizations and tweaks of existing factoring algorithms.  And
four, fundamental advances in the science of factoring.  TWINKLE falls in
one and three; there is no new mathematics in this machine, it's just a
much faster way of doing existing mathematics.

Shamir's contribution is obvious once you understand it (the hallmark of a
brilliant contribution, in my opinion), and definitely changes the
landscape of what public-key key sizes are considered secure.  The moral is
that it is prudent to be conservative--all well-designed security products
have gone beyond 512-bit moduli years ago--and that advances in
cryptography can come from the strangest places.

Shamir's paper:
http://jya.com/twinkle.eps

Bruce Schneier, President, Counterpane Systems     Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN  55419  http://www.counterpane.com