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
1280-Bit RSA
All, I've got a perfect vs. good question. NIST is pushing RSA-2048. And I think we all agree that's probably a good thing. However, performance on RSA-2048 is too low for a number of real world uses. Assuming RSA-2048 is unavailable, is it worth taking the intermediate step of using RSA-1280? Or should we stick to RSA-1024? --Dan - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [TIME_WARP] 1280-Bit RSA
On Thu, 1 Jul 2010 06:46:30 +0200 Dan Kaminsky d...@doxpara.com wrote: All, I've got a perfect vs. good question. NIST is pushing RSA-2048. And I think we all agree that's probably a good thing. However, performance on RSA-2048 is too low for a number of real world uses. Assuming RSA-2048 is unavailable, is it worth taking the intermediate step of using RSA-1280? Or should we stick to RSA-1024? --Dan Dan, I looked at the GNFS runtime and plugged a few numbers in. It seems RSA Security is using a more conservative constant of about 1.8 rather than the suggested 1.92299... See: http://mathworld.wolfram.com/NumberFieldSieve.html So using 1.8, a 1024 bit RSA key is roughly equivalent to a 81 bit symmetric key. Plugging in 1280 yields 89 bits. I'm of the opinion that if you take action to improve security, you should get more than 8 additional bits for your efforts. For example, 1536 shouldn't be that much slower but gives 96 bits of security. For posterity, here is a table using 1.8 for the GNFS constant: RSASymmetric 256 43.7 512 59.8 768 71.6 1024 81.2 1280 89.5 1536 96.8 2048 109.4 3072 129.9 4096 146.5 8192 195.1 Brandon - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [TIME_WARP] 1280-Bit RSA
Dan, I looked at the GNFS runtime and plugged a few numbers in. It seems RSA Security is using a more conservative constant of about 1.8 rather than the suggested 1.92299... See: http://mathworld.wolfram.com/NumberFieldSieve.html So using 1.8, a 1024 bit RSA key is roughly equivalent to a 81 bit symmetric key. Plugging in 1280 yields 89 bits. I'm of the opinion that if you take action to improve security, you should get more than 8 additional bits for your efforts. For example, 1536 shouldn't be that much slower but gives 96 bits of security. Here's the actual data, in terms of transactions per second, I'm getting for a sample app: 512: 710.042382 1024: 187.187719 1280: 108.592265 1536: 73.314751 2048: 20.645645 2048 ain't happening. The relative diff between 1280 and 1536 is interesting though. For posterity, here is a table using 1.8 for the GNFS constant: RSASymmetric 256 43.7 512 59.8 768 71.6 1024 81.2 1280 89.5 1536 96.8 2048 109.4 3072 129.9 4096 146.5 8192 195.1 Do other cracking mechanisms have similar curves to GNFS (with different constants)? - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: [TIME_WARP] 1280-Bit RSA
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... From: p...@ox.ac.uk (Paul C Leyland) Newsgroups: sci.crypt Subject: Re: Questions about RSA. Message-ID: pcl.93feb16102...@rhodium.ox.ac.uk Date: 16 Feb 93 10:26:11 GMT References: 1993feb10.183246.29...@ee.ubc.ca Distribution: sci.crypt, alt.security Organization: Oxford University Computing Services, 13 Banbury Rd Oxford OX2 6NN Lines: 59 In-reply-to: jrusm...@ee.ubc.ca's message of 10 Feb 93 18:32:46 GMT In article 1993feb10.183246.29...@ee.ubc.ca jrusm...@ee.ubc.ca (RUSMISEL JASON DIRK) writes: ... 1) The article suggests that the length of 'n', (where n is the product of two large primes p and q, and n is the modulus used with the encryption and decrytion keys to decode and encode) be 200 digits. [page 125, top right] 200 digits base 10 is about 664 binary digits. Now, to the question. The program PGP provides various levels of key length, 384 bits, 512 bits and 1024 bits. How were these numbers decided on? I The PGP values are round numbers (3/8, 1/2 and 1) in kilobits. They are (handwaving furiously here) about the right size for testing, routine use and archival security. The RSA values are about the right size for routine use. realize that the state of computer technology at the time the RSA article was written was very different than it is now, but have there been significant advances in crypto breaking since 1978 that would make factoring such large numbers much easier? (Perhaps the Connection Machine.) Really I'm interested in a discussion of the design decisions/tradeoffs here. Let me try to justify the armwaving a little. First, we must realise that the larger the keys, the greater the run-time of the encryption and decryption process. Purists may nit pick, but roughly speaking doubling the number of digits in the key increases the run time eightfold. [Purists: I'm assuming a n-squared multiplication routine and the simple binary method of exponentiation]. So small moduli are good. So far as is known, the only way to find the RSA secret key (other than espionage, bribery, extortion, etc) is to factorize the modulus. Here large moduli are good. Roughly speaking *adding* a few bits to the length of the modulus raises the factorizing cost eightfold. Compare this to the encryption, where *doubling* costs us that much. The meaning of a few bits can also be argued over, but it is around 20 bits, depending on methods and the size of the number. Current state of the art described in the open literature factorizes 120-digit numbers in a time of order one year, using machines of order 1000mips performance. Again, purists can post better numbers if they wish. 384 bits is 116 digits so the PGP test keys can, with sufficient effort, be cracked with today's technology. 512 bits is well beyond current technology (155 digits) but *might* be accessible in a few years with better algorithms and faster machines and more of them working in parallel and ... (I'm handwaving again). 1024-bits, so far as is known should be ok for a few decades. I'd be happy to be proved wrong, as there's lots of other numbers I'd like to be able to factorize. Paul -- Paul Leyland p...@oxford.ac.uk | Hanging on in quiet desperation is Oxford University Computing Service | the English way. 13 Banbury Road, Oxford, OX2 6NN, UK | The time is come, the song is over. Tel: +44-865-273200 Fax: +44-865-273275 | Thought I'd something more to say. Finger p...@black.ox.ac.uk for PGP key| -- -- Jonathan Thornburg [remove -animal to reply] jth...@astro.indiana-zebra.edu Dept of Astronomy, Indiana University, Bloomington, Indiana, USA Washing one's hands of the conflict between the powerful and the powerless means to side with the powerful, not to be neutral. -- quote by Freire / poster by Oxfam - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
