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:

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?

  • 2
    Your reasoning is in the good direction. Maybe Chapter 6 of this ECRYPT report is useful for you. – cygnusv May 11 '15 at 14:57
  • 3
    1) The number can't be right. 2048 bits RSA roughly corresponds to a 112 bit symmetric key or a 224 bit ECC key. 2) You wrote a + in the RSA formula where it should be a *. 3) The RSA formula is asymptotic, but you need concrete cost for the comparison. – CodesInChaos May 11 '15 at 14:58
  • @CodesInChaos: using * instead of + I get that a 2048-bit RSA key corresponds to a 273-bit key, which is still incorrect, but is better. I know that I need to use the concrete cost, however I do not have it (and I am interested in an approximation, not the exact value). – user16538 May 11 '15 at 15:21
  • well lenstra and verheul analysed this quite well in 2000. Their goal was to give numbers on the developement of keysizes but for this they needed some sort of model. The text is worth reading and then you may understand. – SEJPM May 11 '15 at 15:23
up vote 5 down vote accepted

Your calculation is broken.

First as pointed out correctly the expected run-time of GNFS (general number field sieve) is: $$\text{O}\left(\exp\left[\left(\sqrt[3]{64/9}+\text{O}\left(1\right)\right)\cdot \sqrt[3]{\ln n}\cdot (\ln \ln n)^{2/3}\right]\right).$$

So next you can't just set these $\text{O}$s equal, as $\text{O}\left(f\left(x\right)\right)$ means $\text{O}\left(f\left(x\right)\right)< kf\left(x\right)$ which means this is an asymptotic upper bound meaning you need some reference point to find out the "$k$".

Now you'd need some way of comparing the "strengths" of the algorithms. In the paper of Lenstra and Verheul this is done using a reasonable recent attack on the cryptosystems, yielding the information that 1024 / 512 bit RSA takes needs X MIPS-Years and breaking 128-bit ECC takes Y MIPS-Years. Now as you know the growth functions you can calculate how the effort grows to obtain the effort you want to meet. This effort can be set equal to get a complex relation, which can only be solved numerically.

First data point: 512-bit number needs $10^4$ MIPS-Years.
Second data point: 108-bit attacked in $8\cdot 10^6$ MIPS-Years.

Formulas:

\begin{array}{lcr} E_{\text{RSA}}\left[2^{512}\right]={10}^4 & \Longrightarrow & \frac{E_{\text{RSA}}\left[2^x\right]}{E_{\text{RSA}}\left[2^{512}\right]}=\frac{X}{{10}^4} \\ E_{\text{ECC}}\left[2^{{108}}\right]=8 \cdot {10}^6 & \Longrightarrow & \frac{E_{\text{ECC}}[2^y]}{E_{\text{ECC}}[2^{108}]}= \frac{X}{(8\cdot {10}^6)} \\ \end{array}

Solving this for $X$ yields $$\frac{(8\cdot {10}^6)\cdot E_{\text{ECC}}\left[2^y\right]}{E_{\text{ECC}}\left[2^{108}\right]}=\frac{10^4 E_{\text{RSA}}\left[2^x\right]}{E_{\text{RSA}}\left[2^{512}\right]},$$ where $E_X\left[Y\right]$ denotes the effort required to attack the number $Y$ of scheme $X$ in MIPS-Years.

For $E_{\text{ECC}}\left[2^x\right]$ this is defined: $E_{\text{ECC}}\left[2^x\right]=2^{x/2}$ and for RSA on simply inserts $2^y$ into the formula of paragraph 2 (without the $\text{O}$).

My calculations yielded a 168-bit EC-key for 2048-bit RSA key, which is correct according to the Lenstra and Verheul paper if you want to compare now. They also consider comparing with "cryptanalytic progress for ECC enabled" yielding ~200 bits.

  • If anyone got any idea of how to format this nicer please suggest. – SEJPM May 11 '15 at 16:35
  • You could ask on / take hints from the TEX site. – Maarten Bodewes May 11 '15 at 16:53
  • Nit: I believe that it's $\sqrt[3]{64/9}+\text{o}\left(1\right)$, as $C + O(1)$ is effectively the same as $O(1)$ – poncho Mar 29 at 19:07

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.