Re: [TLS] Re: Russ Housley: Fwd: problems with draft-ietf-tls-openpgp-keys-10.txt

On Sat, 1 Jul 2006 17:17:01 -0700, "Kyle Hamilton" <aerowolf@gmail.com>
wrote:
> 
> The largest RSA composite number ever known to be factored was 200
> digits long.  (Source:
> http://www.crypto-world.com/FactorAnnouncements.html )  This was
> announced in May 2005, and took from "shortly before Christmas 2003"
> to October 2004 (about 10 months), plus December 2004 to May 2005
> (about 6 months).  This took about 170 Pentium 1GHz CPU-years, and
> approximately (with their clusters) 80 machines working for those 16
> months.  This means that 768 bit general RSA is in sight (if Moore's
> Law continues to hold and advances in factoring mathematics continue
> unabated, it should be less than 3 years from now before a 768-bit RSA
> composite is factored).
> 
> The largest number ever factored by the special number sieve was 274
> digits long.  This is larger than 768-bit RSA, and suggests that
> 1024-bit RSA composites that are of the special form could be
> factorable at this point or in the fairly near future.
> 
> This is why I recommend exploring options other than RSA for identity
> keys.  Why do you disagree with this recommendation?
> 
The effort with GNFS is not linear in modulus length; furthermore, a lot
of memory is needed for the row reduction.  Have a look at sections 2.4
and 2.5 of RFC 3766.  Also see table 5, and note that an 8719-bit modulus
is roughly equivalent to a 200-bit symmetric key, which NSA rates as
suitable for Top Secret data.

That said, I agree that 1024-bit RSA is not suitable for protecting
long-lived secrets.  2048-bit or 3072-bit RSA seems *way* out of reach,
barring a major theoretical breakthrough in factoring algorithsm.  I won't
even engage in guessing games about when Moore's Law will break down, but
I think we can agree that transistors smaller than a single atom are,
shall we say, unlikely, and that puts an upper bound on density no matter
what we do.

		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

_______________________________________________
TLS mailing list
TLS@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/tls