I know how to calculate the comparable symmetric strength of an RSA modulus: calculate the running time for a field sieve. This is how NIST gives approximate symmetric sizes for asymmetric algos in their publications: for RSA you can calculate running time of the field sieve:
$$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right)$$
What's the equivalent for ECDHE? Eg. what is the running time for the best known algorithm for attacking a given ECC curve?
RFC 4492 states:
the following table gives approximate comparable key sizes for symmetric- and asymmetric-key cryptosystems based on the best-known algorithms for attacking them.
Symmetric | ECC (binary curve) | ECC (prime curve) | DH/DSA/RSA |
---|---|---|---|
80 | 163 | 160 | 1024 |
112 | 233 | 224 | 2048 |
128 | 283 | 256 | 3072 |
192 | 409 | 384 | 7680 |
256 | 571 | 521 (not a typo) | 15360 |
How can I replicate the ECC column's numbers?
Edit: some some research, the paper mentioned in the RFC now 404s but a copy found at http://infoscience.epfl.ch/record/164526/files/NPDF-22.pdf mentions:
2.6.3. Attacks. A DLNFS equivalent or other subexponential method to attack EC systems has never been published. The most efficient method published to attack EC systems is Pollard’s parallelizable rho method, with an expected run time of 0.88√q group operations.
However I still don't know how to replicate the results: an elliptic curve has P and Q but how do I know what Q is, for, eg, secp521r1?
Edit: Deirdre Connolly on Twitter mentioned an approximation:
$log_2(0.88 \cdot \sqrt{2^{n}})$
Which matches the RFCs results. Will do some more research and post it as an answer in the next few days if she doesn't.