Gnupg-users Digest, Vol 131, Issue 15

[Michael Anders]

>  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