IP: Israeli scientist reports discovery of advance in code breaking -- some more from RISKS

[Dave Farber <farber () cis upenn edu>]

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