Does the elliptic curve (EC) cryptosystem outperform RSA and DL cryptosystems?

Question

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?

Answer 1

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).