I know and I have understood the details of RSA, elliptic curve cryptography, (EC)DH and (EC)DSA.

I keep reading everywhere that (if we don't consider non-deterministic computers) "ECC can achieve the same level of security as RSA, but with lower key sizes". While I can guess why this is true, how do we mathematically prove that?

Here's what I think:

• The fastest algorithm for the ECC discrete logarithm problem is the Baby-step Giant-step, which is $O(2^{b/2})$ (https://en.wikipedia.org/wiki/Baby-step_giant-step).
• The fastest algorithm for the RSA problem/integer factorization is $O(\exp((64 b / 9)^{1/3} + (\log b)^{2/3}))$ (http://en.wikipedia.org/wiki/Integer_factorization).

Here $b$ is the bit-length of the key/of the group order.

Therefore, an ECC key of $b_1$ bits has the same strength of an RSA key of $b_2$ bits when: $2^{b_1/2} \approx \exp((64 b_2 / 9)^{1/3} + (\log b_2)^{2/3})$.

Using that formula I can calculate that if I have a 4096-bit RSA key, I can achieve the same level of security with a 101-bit ECC key. But this number (101) does not convince me. It seems too low.

My question is: is my reasoning wrong? Is the number correct?

I know and I have understood the details of RSA, elliptic curve cryptography, (EC)DH and (EC)DSA.

I keep reading everywhere that (if we don't consider non-deterministic computers) "ECC can achieve the same level of security as RSA, but with lower key sizes". While I can guess why this is true, how do we mathematically prove that?

Here's what I think:

• The fastest algorithm for the ECC discrete logarithm problem is the Baby-step Giant-step, which is $O(2^{b/2})$ (https://en.wikipedia.org/wiki/Baby-step_giant-step).
• The fastest algorithm for the RSA problem/integer factorization is $O(\exp((64 b / 9)^{1/3} \cdot (\log b)^{2/3}))$ (http://en.wikipedia.org/wiki/Integer_factorization).

Here $b$ is the bit-length of the key/of the group order.

Therefore, an ECC key of $b_1$ bits has the same strength of an RSA key of $b_2$ bits when: $2^{b_1/2} \approx \exp((64 b_2 / 9)^{1/3} \cdot (\log b_2)^{2/3})$.

Using that formula I can calculate that if I have a 2048-bit RSA key, I can achieve the same level of security with a 273-bit ECC key. But this number (273) is too high.

My question is: is my reasoning wrong? Where is the mistake?