[1029] in cryptography@c2.net mail archive
Re: DES: Thank you! (what next?)
daemon@ATHENA.MIT.EDU (Paul Bradley)
Fri Jun 20 11:33:27 1997
Date: Fri, 20 Jun 1997 13:03:04 +0000 ( )
From: Paul Bradley <paul@fatmans.demon.co.uk>
To: Peter Trei <trei@process.com>
cc: cryptography@c2.net, trei@process.com
In-Reply-To: <199706191544.IAA28325@blacklodge.c2.net>
> The earlier efforts on 40 and 48 bit RC5 suggest that keysearch
> for RC5 is substantially slower than DES - perhaps 5-10 x slower. It's
> probable that the clients have not been fully optimized. RSA has
> another $10,000 prize for this crack.
Seeing as, from a publicity point of view, joe public doesn`t have any
idea what the block length of an algorithm is, an optimal block length
for cracking speed could be selected.
> 2. RSA 135
>
> We used about 1000x the cpu needed for the RSA 130 factorization. I'm
> not sure how the best current factorization systems scale with the
> modulus size (Rivest, Lenstra?) but I suspect that it's less than
> linear.
For numbers of this size the GNFS was fastest, I don`t know if the
constant has changed but (searching for book....) Schneier has the
asymptotic estimate at:
(1/3) (2/3)
(1.923) X (ln(n)) X (ln(ln(n)))
e
but that was about a year or so ago, it is probable that small
improvements have decreased the constant (1.923) a little.
I say was fastest, there were a lot of improvements made on the DLPVMPQS
(double large prime variant of the multiple polynomial quadratic sieve)
and I don`t really know for sure what the current state of the art is.
Lenstra would probably be able to englighten us.
> If this is so, then RSA 135 may be doable. RSA135 is roughly
> comparable to a 448 bit key. RSA also has a prize for this
> factorization.
The cypherpunks should stop working on cryptography and start working on
cryogenic suspension, then we can set the timer for say 10^10^100 years
from now, and wake to find a small pocket calculator has factored RSA-500
;-)...
Datacomms Technologies data security
Paul Bradley, Paul@fatmans.demon.co.uk
Paul@crypto.uk.eu.org, Paul@cryptography.uk.eu.org
Http://www.cryptography.home.ml.org/
Email for PGP public key, ID: FC76DA85
"Don`t forget to mount a scratch monkey"
