1280-Bit RSA

[James A. Donald]

On 2010-07-11 10:11 AM, Brandon Enright wrote:
 > On Fri, 9 Jul 2010 21:16:30 -0400 (EDT) Jonathan
 > Thornburg<jthorn at astro.indiana.edu>  wrote:
 >
 >> The following usenet posting from 1993 provides an
 >> interesting bit (no pun itended) of history on RSA key
 >> sizes.  The key passage is the last paragraph, asserting
 >> that 1024-bit keys should be ok (safe from key-factoring
 >> attacks) for "a few decades".  We're currently just under
 >> 1.75 decades on from that message.  I think the take-home
 >> lesson is that forecasting progress in factoring is hard,
 >> so it's useful to add a safety margin...
 >
 > This is quite interesting.  The post doesn't say but I
 > suspect at the factoring effort was based on using
 > Quadratic Sieve rather than GNFS. The difference in speed
 > for QS versus GNFS starts to really diverge with larger
 > composites.  Here's another table:
 >
 > RSA	GNFS	QS
 > ===========================
 > 256	43.68	43.73
 > 384	52.58	55.62
 > 512	59.84	65.86
 > 664	67.17	76.64
 > 768	71.62	83.40
 > 1024	81.22	98.48
 > 1280	89.46	111.96
 > 1536	96.76	124.28
 > 2048	109.41	146.44
 > 3072	129.86	184.29
 > 4096	146.49	216.76
 > 8192	195.14	319.63
 > 16384	258.83	469.80
 > 32768	342.05	688.62

The numbers in the second column of this table are the
equivalent strength of symmetrical encryption, that is to
say, against attackers armed with the GNFS, a 3072 bit RSA
key is as tough as a 128 bit symmetric key.
 >
 > Clearly starting at key sizes of 1024 and greater GNFS
 > starts to really improve over QS.  If the 1993 estimate for
 > RSA 1024 was assuming QS then that was roughly equivalent
 > to RSA 1536 today.  Even improving the GNFS constant from
 > 1.8 to 1.6 cuts off the equivalent of about 256 bits from
 > the modulus.
 >
 > The only certainty in factoring techniques is that they
 > won't get worse than what we have today.

Progress in cracking elliptic curves, however, does not seem
to be happening, probably because elliptic curves are truly
irregular.

  How do elliptic curves compare to RSA today?

According to
http://paper.ijcsns.org/07_book/200909/20090902.pdf

RSA	ECC	Sym
1024	160	80
2048	224	112
3072	256	128
4096	280	140

That is to say, a 3072 bit RSA key is as tough as an ECC key
based on a 256 bit field, which is as tough as a 128 bit
symmetric key.

ECC cryptosystems on 256 bit field are practical today.  3072
bit RSA systems are not.

It looks to me that Moore's law plus GNFS has decisively
tipped the balance in favor of elliptic curves - and if one
has patent worries, good elliptic curve algorithms were
published more than fifteen years ago.

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