Asymmetric Key sizes

[Paul Leyland]

> From: Brian Morrison [mailto:bdm@fenrir.demon.co.uk]
> There was a posting to sci.crypt (might have been 
> sci.crypt.research) a
> few days ago stating that the RSA-140 factoring challenge had been
> completed, this involves factoring a 140 digit number, a similar
> process to that required to break an RSA key.
> 
> I think that this development means that it is now possible to break
> 512 bit RSA keys, and reduces the security of 768 bit RSA keys. I
> certainly can't claim to be able to rigorously state this, 
> but that was the tone of the post.

It has been possible to break 512 bit keys for several years.  Back in 1994
we estimated that the same approach we used for RSA-129 (429 bits) would
work for a 512-bit key, albeit with about 90 times as much sieving and
several weeks on big iron for the linear algebra.  We also recognized back
then that GNFS would do the job with less effort.  Advances in algorithms
and technology have made a 512-bit key now about as hard as 429-bit key then
--- at least as far as the sieving goes.   The linear algebra is still much
harder.  As for 768-bit keys, they would appear to be resistant to any
reasonable attack with any reasonable amount of hardware.

> A search of Dejanews would probably locate the post in question.

I refer the honorable member to my previous reply.  8-)

Paul