Re: 1280-Bit RSA
On 2010-07-11 10:11 AM, Brandon Enright wrote: On Fri, 9 Jul 2010 21:16:30 -0400 (EDT) Jonathan Thornburgjth...@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: RSAGNFSQS === 25643.68 43.73 38452.58 55.62 51259.84 65.86 66467.17 76.64 76871.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 1024160 80 2048224 112 3072256 128 4096280 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 majord...@metzdowd.com
Re: 1280-Bit RSA
Dan: You didn't mention the option of switching to elliptic curves. A 256-bit elliptic curve is probably stronger than 2048-bit RSA [1] while also being more efficient in every way except for CPU cost for verifying signatures or encrypting [2]. I like the Brainpool curves which comes with a better demonstration that they were generated with any possible back door than do the NIST curves [3]. Regards, Zooko [1] http://www.keylength.com/ [2] http://bench.cr.yp.to/results-sign.html [3] http://www.ecc-brainpool.org/download/draft-lochter-pkix-brainpool-ecc-00.txt - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 1280-Bit RSA
On 11-07-2010 01:11, Brandon Enright wrote: On Fri, 9 Jul 2010 21:16:30 -0400 (EDT) Jonathan Thornburg jth...@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.46111.96 1536 96.76124.28 2048 109.41 146.44 3072 129.86 184.29 4096 146.49 216.76 8192 195.14 319.63 16384258.83 469.80 32768342.05 688.62 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. Brandon - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com The exponent can be further lowered from that (somewhere between 1.6 and 1.7) --- RSA-768 took about 2^67 Opteron instructions to complete, and RSA-512 can be done in about 2^54 similar operations (it is in the realm of possibility for a single box over a few days/weeks). Best regards, Samuel Neves - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: 1280-Bit RSA
On Fri, 9 Jul 2010 21:16:30 -0400 (EDT) Jonathan Thornburg jth...@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.46111.96 1536 96.76124.28 2048 109.41 146.44 3072 129.86 184.29 4096 146.49 216.76 8192 195.14 319.63 16384258.83 469.80 32768342.05 688.62 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. Brandon - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
