Shamir's TWINKLE Factoring Machine

1 view
Skip to first unread message

Bruce Schneier

unread,
May 5, 1999, 3:00:00 AM5/5/99
to
At Eurocrypt this week, 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 terrabytes 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.

**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com

**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com

tomst...@my-dejanews.com

unread,
May 5, 1999, 3:00:00 AM5/5/99
to
<snip>

Thanks for the info, btw where could someone (maybe I :) ) find info on the
details of factoring a RSA number or a Discrete log?

I would just to like to know the technique and not nesscesarily all the
steps..

Is this covered in AC? (I will check later ...)

Tom

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own

lam...@bite.me.spammers

unread,
May 5, 1999, 3:00:00 AM5/5/99
to
schn...@counterpane.com (Bruce Schneier) writes:
>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 terrabytes of memory: not off-line
>storage, but real computer memory. No one has a clue how to solve
>that kind of problem.

Uh, give it time.

Right now I admin some 8 gig RAM machines. It's been maybe 15
years since 8 meg machines were this expensive (okay, I was 14 in
1985, sue me if i'm off by a few years). So presumably in 10-15
years we'll have 8 terabytes of RAM.

And I'm sure the NSA could build a machine with 8 terabytes of RAM
right now. Certainly within a few years. And would it be theoretically
possible to tune the algorithm so that it could be cache- and swap-friendly?
In which case you might be able to throw cheap RAM and disk at the problem
without a huge performance hit and it gets kind of frightening. Keep in
mind that in terms of tuning the algorithm the NSA already has tons of
mathematicians and computer scientists to throw at the problem if they
care about it...

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

Could there be mathematical advances which make the matrix problem for
the discrete-log problem equivalent to the factoring one? Does the NSA
know how to apply this technique to elliptic curve systems?

--
Lamont Granquist (lam...@u.washington.edu)
ICBM: 47 39'23"N 122 18'19"W

ca314159

unread,
May 5, 1999, 3:00:00 AM5/5/99
to
Bruce Schneier wrote:
>
> At Eurocrypt this week, 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.


Twinkle:
http://www.jya.com
___
http://www.bestweb.net/~ca314159/

dejanews problems

Bruce Schneier

unread,
May 6, 1999, 3:00:00 AM5/6/99
to
On 5 May 1999 22:18:42 GMT, lam...@bite.me.spammers wrote:

>schn...@counterpane.com (Bruce Schneier) writes:
>>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 terrabytes of memory: not off-line
>>storage, but real computer memory. No one has a clue how to solve
>>that kind of problem.
>
>Uh, give it time.
>
>Right now I admin some 8 gig RAM machines. It's been maybe 15
>years since 8 meg machines were this expensive (okay, I was 14 in
>1985, sue me if i'm off by a few years). So presumably in 10-15
>years we'll have 8 terabytes of RAM.

Indeed.

>And I'm sure the NSA could build a machine with 8 terabytes of RAM
>right now. Certainly within a few years. And would it be theoretically
>possible to tune the algorithm so that it could be cache- and swap-friendly?

This I don't know. It is certainly concievable, but at first glance
it seems impossible.

>>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.
>
>Could there be mathematical advances which make the matrix problem for
>the discrete-log problem equivalent to the factoring one?

I don't think so. For RSA, you can solve the linear equations in mod
2. For discrete log systems, you have to work modulo the
chracteristic of the field.

>Does the NSA
>know how to apply this technique to elliptic curve systems?

You'll have to ask them. Although there are rumors that the NSA is
using discrete log systems, which implies not. But they are only
rumors.

Bruce

David A Molnar

unread,
May 6, 1999, 3:00:00 AM5/6/99
to
lam...@bite.me.spammers wrote:
> right now. Certainly within a few years. And would it be theoretically
> possible to tune the algorithm so that it could be cache- and swap-friendly?

This is what bothers me most in terms of an entity like the NSA - they have the
time and people to investigate practical issues in implementing these algorithms.
These are optimizations which I haven't seen covered much in papers themselves
(maybe in block cipher land?) -- indeed, an article passed out in class last
week flat out admitted that no one in the public world had a large amount of
experience with implementing these things. The article was from the late '80s, so
perhaps things are a bit different now (wasn't there a large effort just
recently?), but it points to a problem.

OK, I found it : p.16 of "The Discrete Logarithm Problem" by Kevin S. McCurley. There's
no date on the paper, but the challenge in it matches the 1989 challenge on his
web page (which has been solved. darn. oh well, there's lots more. lattices anyone?)
BTW, this paper is a very readable introduction to the subject of discrete log
algorithms. I can't find it on his web site (http://www.swcp.com/~mccurley/index.html)
but maybe e-mail would help.


> Could there be mathematical advances which make the matrix problem for
> the discrete-log problem equivalent to the factoring one?

Where exactly does the "more difficult" lie? does it have to do with
the fact that discrete log algorithms require so much more space?

I want to say that the difference between the two is that we have a notion
of "smoothness" for primes, but no corresponding notion for discrete logs,
and therefore end up having to build a much larger table of discrete logs
than possible L(something)-smooth primes. Unfortunately I think I need to
go sit down and look at the algorithms again to pin that down.


>Does the NSA
> know how to apply this technique to elliptic curve systems?

Dunno. If I did I probably couldn't tell you. :-)

-David

DJohn37050

unread,
May 6, 1999, 3:00:00 AM5/6/99
to
The NSA representatives at ANSI X9F1 and at IEEE P1363 (these have been a few
different people) have consistently said that they like elliptic curve crypto.
Also, remember that the DSA was designed by NSA.
Don Johnson

Damian Weber

unread,
May 6, 1999, 3:00:00 AM5/6/99
to
>schn...@counterpane.com (Bruce Schneier) writes:
>>
>>Could there be mathematical advances which make the matrix problem for
>>the discrete-log problem equivalent to the factoring one?
>
> I don't think so. For RSA, you can solve the linear equations in mod
> 2. For discrete log systems, you have to work modulo the
> characteristic of the field.
Not modulo the characteristic of the field but modulo the order
of the multiplicative group of the finite field. This then reduces
to prime factors of that order which, when considering finite fields
of degree>=3, may well be greater than the characteristic.

This is why the matrix step in DL is likely to be harder than the one
in factoring.

-- Damian

Damian Weber

unread,
May 6, 1999, 3:00:00 AM5/6/99
to
In article <7gqqb2$e32$1...@news.fas.harvard.edu>,
David A Molnar <dmo...@fas.harvard.edu> writes:

> lam...@bite.me.spammers wrote:
>> Could there be mathematical advances which make the matrix problem for
>> the discrete-log problem equivalent to the factoring one?

> Where exactly does the "more difficult" lie? does it have to do with
> the fact that discrete log algorithms require so much more space?

it has to do with solving matrix equations mod large primes
instead of mod 2.

> I want to say that the difference between the two is that we have a notion
> of "smoothness" for primes, but no corresponding notion for discrete logs,
> and therefore end up having to build a much larger table of discrete logs
> than possible L(something)-smooth primes. Unfortunately I think I need to
> go sit down and look at the algorithms again to pin that down.

No, the smoothness notion refers to the relation collection
stage of modern factoring and index calculus algorithms which
is similar for both problems.

-- Damian


Damian Weber

unread,
May 6, 1999, 3:00:00 AM5/6/99
to
In article <7gqe2g$b5k$1...@nnrp1.deja.com>,

tomst...@my-dejanews.com writes:
>
> Thanks for the info, btw where could someone (maybe I :) ) find info on the
> details of factoring a RSA number or a Discrete log?
In the ASIACRYPT'96 proceedings you'll find the RSA-130
factorization.
In the CRYPTO'98 proceedings you'll find the solution
of McCurley's DL-challenge.

-- Damian

Medical Electronics Lab

unread,
May 6, 1999, 3:00:00 AM5/6/99
to

Is that because it's deep fun math or because it's good crypto?

Patience, persistence, truth,
Dr. mike

ca31...@bestweb.net

unread,
May 6, 1999, 3:00:00 AM5/6/99
to
In article <3731D0...@physiology.wisc.edu>,

Medical Electronics Lab <ros...@physiology.wisc.edu> wrote:
> DJohn37050 wrote:
> >
> > The NSA representatives at ANSI X9F1 and at IEEE P1363 (these have been a
few
> > different people) have consistently said that they like elliptic curve
crypto.
> > Also, remember that the DSA was designed by NSA.
>
> Is that because it's deep fun math or because it's good crypto?

Elliptic Curve Crypto FAQ:
http://ds.dial.pipex.com/george.barwood/ec_faq.htm


---
A swift objective kick, will distinguish many subjective beliefs.
http://www.bestweb.net/~ca314159/

Robert Harley

unread,
May 7, 1999, 3:00:00 AM5/7/99
to

schn...@counterpane.com (Bruce Schneier) writes:
> >Could there be mathematical advances which make the matrix problem for
> >the discrete-log problem equivalent to the factoring one?
>
> I don't think so. For RSA, you can solve the linear equations in mod
> 2. For discrete log systems, you have to work modulo the
> chracteristic of the field.

No, for DL you have to solve modulo the prime factors of the field
size minus one. These factors can be just about anything *except* the
characteristic!

Bye,
Rob.

DJohn37050

unread,
May 7, 1999, 3:00:00 AM5/7/99
to
Well, let's see now, a while back the annual NSA retreat was entirely devoted
to discussing ECC. I was not one, but the reason I know this is all the
attendees got a t-shirt that had an elliptic curve on it. Draw your own
conclusions.
Don Johnson

Hawkhaven

unread,
May 11, 1999, 3:00:00 AM5/11/99
to


On Thu, 6 May 1999, Bruce Schneier wrote: (in part)

> On 5 May 1999 22:18:42 GMT, lam...@bite.me.spammers wrote:
>
> >And I'm sure the NSA could build a machine with 8 terabytes of RAM

> >right now. Certainly within a few years. And would it be theoretically
> >possible to tune the algorithm so that it could be cache- and swap-friendly?
>

> This I don't know. It is certainly concievable, but at first glance
> it seems impossible.
>
>

> Bruce
> **********************************************************************
> Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
> 101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
> Free crypto newsletter. See: http://www.counterpane.com
>
>

if the machine can be run from something that has an os that could
changed, (a pc for example), then there probably wouldnt be any reason
why you wouldnt be able to use virtual ram...of course with that much
virtual ram it might run slower with the device than with convensional
methods...BTW, i realy enjoyed your book...

--Hawkhaven

"Win if you can, lose if you must, but always, always cheat!"

Bob Silverman

unread,
May 12, 1999, 3:00:00 AM5/12/99
to
In article <7gqg42$klk$1...@nntp6.u.washington.edu>,

lam...@bite.me.spammers wrote:
> schn...@counterpane.com (Bruce Schneier) writes:
> >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 terrabytes of memory: not off-line
> >storage, but real computer memory. No one has a clue how to solve
> >that kind of problem.

For factoring this is quite right. For discrete-logs it will be
3 orders of magnitude larger, i.e. 10 PetaBytes.

>
> Uh, give it time.
>
> Right now I admin some 8 gig RAM machines. It's been maybe 15
> years since 8 meg machines were this expensive (okay, I was 14 in
> 1985, sue me if i'm off by a few years). So presumably in 10-15
> years we'll have 8 terabytes of RAM.

Only if there is a need for machines with that much RAM, but I agree
it will probably be technically feasible.

However, everyone still ignores the fact that one must SOLVE this
matrix. Suppose we assume that we had the world's fastest CRAY today
with enough memory. It would still take "about" 60 Million WEEKS
to solve the matrix. And we do not as yet have techniques to solve
such matrices in parallel. processor-to-processor latency will be a
MAJOR bottleneck even if bandwidth is sufficient. And if one looks
at a shared-memory multiprocessor instead of message passing, then
bus-contention becomes a major problem.


>
> And I'm sure the NSA could build a machine with 8 terabytes of RAM
> right now. Certainly within a few years.

Dynamic RAM would be too slow. One needs 8-10 Tbytes of fast static
RAM (i.e. 1-2nsec register<-->memory latencies). Is there even that
much fast static RAM in existence today? And yes, it is probably
technically feasible. But what would it cost?

> And would it be theoretically
> possible to tune the algorithm so that it could be cache- and swap-
friendly?

The block Lanczos algorithm can be tuned to be cache friendly. But for
this sized matrix we are talking about a big big cache. I'd have to
do the arithmetic to estimate how big. Certainly in the Gbyte range.


>
> >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.)

MUCH harder. Instead of working mod 2, one must solve the matrix
modulo the order of the group or field. Furthermore, storage goes
way up. Instead of each matrix element being a single bit, it is now
the size of the field. (log_2 p for GF(p))

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

> Could there be mathematical advances which make the matrix problem
for
> the discrete-log problem equivalent to the factoring one?

Not for sieve based algorithms as we know them.

> Does the NSA
> know how to apply this technique to elliptic curve systems?

Noone does.


--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"


--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---

Reply all
Reply to author
Forward
0 new messages