Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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).
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.
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.
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.
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..
