Shamir factoring machine uninteresting?

[Anton Stiglic]

>From: "Perry E. Metzger" <perry at piermont.com>

> I find it odd that there has been so little comment on TWIRL. One
> would think that the crushing of 512 bit RSA keys and a strong
> demonstration of the weakness of 1024 bit RSA keys would have provoked
> some comment on the list.
>
> Any comments on why no one commented?

I'd say that most people are interested in such attacks only when they are
actually implemented.  So far the concept of TWIRL seems to be only
theoretical.

Some theoretical attacks attract attention because if implemented
successfully,
they would really change the way we think of crypto.   TWINKLE is such an
example (when the concept of TWINKLE first came out, allot of people
were talking about it), so is the work of D.J. Berstein on factoring.
But to decide whether or not a theoretical attack can be practical or not
is difficult and time consuming.  Take for example the XSL attack on
block ciphers such as AES, in which there seems to have been an error
(pointed out by Coppersmith) which invalidates the results, look at the
error in the proof of OAEP (a theoretical result which was widely accepted
for some time, but Shoup found an error in the proof).

The best demonstration is to actually implement it.

In the abstract of the TWIRL paper, it says that TWIRL can enable
the NFS sieving step more cost effectively, with 3-4 orders of magnitude
more than TWINKLE, but TWINKLE was never implemented (and if
I'm not mistaken, there is doubt about whether or not it can be
implemented?), and 3-4 orders is not that big of a magnitude.

The abstract also says that the NFS sieving step of 512-bit RSA keys
can be done in less then 10 minutes by a 10K device.  10K is not that
much to spend on research, so if this can really be implemented I'm thinking
that someone can do it soon.

Personally, I'll wait and see if someone comes up with a proof of concept,
and if so then I'll take the time to read the paper.  For now, I already
consider
512-bit RSA keys as insecure (because 512 bit integers have already been
factored, and I always allow for a cushion factor so I'm sure it can be
factored
even more efficiently).  For now, there are many other results which I would
like to read about which are of interest to me at the present time as a
cryptographer with an eye on implementation.  This is not to say that
I really respect the work of Shamir and I'm sure that the TWIRL paper has
some interesting results.

Cheers!

--Anton








---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com