Re: Gnupg-users Digest, Vol 131, Issue 15
I'm not sure, but didn't discrete-logarithm keys scale roughly equivalently to RSA? I think so, but I'm not sure... and The guidance from NIST is: [1] shannons of entropy needed [2] bits of symmetric key [3] bits of RSA/DSA/ELG [4] bits of ECDSA/ECetc. [1] [2] [3] [4] 80 80 1024160 112 112 2048224 128 128 3072256 256 256 ~15k512 The entropy of symmetric and ECDSA/ECetc. keys scales linearly with key length; the entropy of RSA/DSA/ELG keys scales logarithmically with key length. and However, I've also been cautioned by some big names in crypto that I shouldn't put too much stock in this: we know DLP must be at least as hard as integer factorization, but we don't have precise numbers for how much harder it has to be, and the tendency over the years has been for the two to slowly converge in difficulty. As of now the best guidance is to think DLP is at least as hard as IFP, but to be skeptical about how much harder. No witchcraft, just some simple math. Baltimore published: (http://www.nsa.gov/business/programs/elliptic_curve.shtml) symm. RSA ECC 80 1024160 112 2048224 128 3072256 192 7680384 256 15360 521 The generalized number field sieve(-RSA factoring) scales with bitlength to the 1/3 (http://en.wikipedia.org/wiki/General_number_field_sieve), new improvements by Joux et al (http://eprint.iacr.org/2013/400.pdf) set it to 1/4 but this so far seems limited to smaller numbers. ECC security scales with bitlength to the 1/2 (General DLP methods) If you set the scale to 160 bit ECC being at the same security level as 1024 bit RSA (presently considered marginal security) you arrive at the formula for the generalized number field sieve: n(RSA) = ((n(ECC)^1/2)/1.25)^3 The resulting table would look like this ECC(bitlength) RSA/elGamal 160 1024 256 2072 384 3807 512 5862 768 10769 1024 16579 If you presume Joux's results would apply to RSA factoring, the formula would look like: n(RSA) = ((n(ECC)^1/2)/15.9)^4 Now the resulting table would look like this ECC(bitlength) RSA/elGamal 160 1024 256 2621 384 5898 512 10486 768 23593 1024 41943 Interestingly NIST arrives at an estimate even in excess of the second table! So we might speculate that they either know of some improvement compared to the publicly known methods to factor RSA moduli, expect such improvement from other sources or else just want to push ECC. (I like ECC - google open source elliptic curve cryptography.)) Cheers Michael Anders ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Gnupg-users Digest, Vol 131, Issue 15
On 8/13/2014 4:38 AM, Michael Anders wrote: Baltimore published: Fort Meade is actually closer to Laurel than it is to Baltimore. (http://www.nsa.gov/business/programs/elliptic_curve.shtml) symm. RSA ECC 801024160 112 2048224 128 3072256 192 7680384 256 15360 521 Which shouldn't be any surprise, since NIST collaborates with them on determining these numbers. You'll notice that they exactly match NIST's recommendations, except that NIST doesn't list a 192-bit entry. Also, I think your 521 is actually 512. :) The generalized number field sieve(-RSA factoring) scales with bitlength to the 1/3 Nope. That's the computational complexity in a computational-theory sense, not the complexity in a cryptanalytic sense. Be real careful about thinking the two of them are connected; they're probably not. If it scaled with bit length to the 1/3 power, and if a 3072-bit RSA key corresponds to 128 shannons of entropy, a 15360-bit RSA key would only have 211 shannons -- not 256. Coming up with these tables is black magic at the best of times. For that reason, I hope you'll understand if I choose to rely on NIST rather than your numbers. :) smime.p7s Description: S/MIME Cryptographic Signature ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
RE: Gnupg-users Digest, Vol 131, Issue 15
Hi Robert, You are both correct. The hash strength=512 curve is called P-521. Thanks, Bob Cavanaugh -Original Message- From: Gnupg-users [mailto:gnupg-users-boun...@gnupg.org] On Behalf Of Robert J. Hansen Sent: Wednesday, August 13, 2014 6:08 AM To: gnupg-users@gnupg.org Subject: Re: Gnupg-users Digest, Vol 131, Issue 15 On 8/13/2014 4:38 AM, Michael Anders wrote: Baltimore published: Fort Meade is actually closer to Laurel than it is to Baltimore. (http://www.nsa.gov/business/programs/elliptic_curve.shtml) symm. RSA ECC 801024160 112 2048224 128 3072256 192 7680384 256 15360 521 Which shouldn't be any surprise, since NIST collaborates with them on determining these numbers. You'll notice that they exactly match NIST's recommendations, except that NIST doesn't list a 192-bit entry. Also, I think your 521 is actually 512. :) The generalized number field sieve(-RSA factoring) scales with bitlength to the 1/3 Nope. That's the computational complexity in a computational-theory sense, not the complexity in a cryptanalytic sense. Be real careful about thinking the two of them are connected; they're probably not. If it scaled with bit length to the 1/3 power, and if a 3072-bit RSA key corresponds to 128 shannons of entropy, a 15360-bit RSA key would only have 211 shannons -- not 256. Coming up with these tables is black magic at the best of times. For that reason, I hope you'll understand if I choose to rely on NIST rather than your numbers. :) ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
