Gnupg-users Digest, Vol 131, Issue 15
Michael Anders
micha137 at gmx.de
Wed Aug 13 10:38:26 CEST 2014
> 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 1024 160
> 112 112 2048 224
> 128 128 3072 256
> 256 256 ~15k 512
>
> 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 1024 160
112 2048 224
128 3072 256
192 7680 384
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
More information about the Gnupg-users
mailing list