17
$\begingroup$

Throughout the literature, it is stated that EC cryptosystems outperform RSA and Discrete logarithm cryptosystems, but I cannot understand how ECC would be more efficient than RSA and DL in terms of computation and storage.

Is there any pragmatic performance analysis comparing these cryptosystems so that I can understand?

$\endgroup$
2
  • $\begingroup$ See: crypto.stackexchange.com/questions/3958/… especially Thomas' answer there. $\endgroup$
    – mikeazo
    Jan 3, 2013 at 20:09
  • $\begingroup$ Actual performance may of course vary between implementations. You are better off doing a theoretical compare, as given by Thomas, as any other compare is bunk. Or implement a performance compare yourself and run it on your target platforms. $\endgroup$
    – Maarten Bodewes
    Jan 3, 2013 at 20:29

2 Answers 2

23
$\begingroup$

Simply put, elliptic curves allow you to use smaller fields.

Consider Diffie-Hellman: given $p$, $g$ and $x$, you compute $g^x \mod p$. To ensure security, you must use values of $x$ and $p$ which are large enough to defeat known attacks. In practice, $x$ will need to be at least 160-bit long, while $p$ will be a 1024-bit prime.

Now, the elliptic curve variant: you have a curve $E$ where point coordinates are elements of a field of cardinal $q$, and you compute $xG$ for an integer $x$ and a conventional point $G$. To achieve security, you need $x$ to be a 160-bit long integer, as with the plain DH case; however, it suffices that $q$ is also a 160-bit integer (e.g. a 160-bit prime). Computing $xG$ will require roughly ten times as many field operations than computing $g^x$, but these operations will be performed in a much smaller field, more than 6 times smaller. Since the elementary cost of a field operation is, in practice, quadratic in the field size, you infer that field operations modulo $q$ will be about 40 times faster than field operations modulo $p$. Even if you do ten times as many, you are still 4 times faster with the curve than with plain DH.

The performance ratio increases with higher security levels (e.g. a 224-bit curve will give you roughly the same security than a 2048-bit plain DH key, leading to a factor of more than 8 in favour of the curve).

For storage, elliptic curves are also better: a 224-bit curve point can be represented over 225 bits (and you can often lower that to 224, at least for Diffie-Hellman), whereas a 2048-bit integer uses, well, 2048 bits.

The RSA public operation (raising to the power $e$ modulo $n$, where $e$ is the public exponent) is still a tad faster than public key operations with ECC-powered algorithms, but for private key operations, curves win hands down (if properly implemented, of course).

$\endgroup$
1
  • $\begingroup$ I didn't quite get the difference between RSA vs Diffie-Hellman. Both of them have g^x (mod p) operation. But you say RSA < ECC < Diffie-Hellman in the the run time. Why is it so? $\endgroup$
    – satya
    Nov 19, 2018 at 18:49
5
$\begingroup$
  1. Both ECC and RSA have execution times proportional to the cube of the bitlength (n^3) of the RSA-Modulus or the Domain bitlength, respectively. So there is no difference in the asymptotic behaviour if you increase bit length.

  2. ECC needs roughly 10 multiplications per point operation. Point doubling and point addition in ECC, corresponding to squaring and multiplying in RSA, behave somewhat differently. See one of the Bernstein papers on this topic for a more detailed treatment. So at equal bit length ECC would be about an order of magnitude slower.

  3. The best attacks on RSA(general Number field sieve) have a complexity of n/3 (if n is bit length), the best attacks on ECC have n/2 (e.g. pollards rho algorithm). Thus ECC needs a lesser bit length that RSA for the same security level. The NSA published a table comparing bit lengths of comparable security level for ECC and RSA. They claim 256 bit ECC is as secure as 3072 bit RSA.

    Thus above some bit length ECC will always be faster than equal security RSA, below RSA will be faster. Where this crossover happens depends on the details of the implementations at hand.

  4. Increasing hardware performance and progress in factoring will enforce an ever rising bit length for future RSA applications. Thus we will certainly encounter the crossover even for marginal security in the future. As a rule of thumb you can expect ECC to be faster above may be 256 bit ECC vs. 3072 bit RSA.

If you want to see ECC run on your system, you can use e.g. the open source program "academic signature" and check performance for up to 1024 bit ECC domains.

Openssl may be a bit easier to run benchmarks on, but at present it will only give you up to 521 bit ECC and only allows domains specially fabricated by the NSA which contain speedy shortcuts and are regarded with caution by some experts..

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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