Comparison of RSA, ElGamal, and ECC

Since RSA and elliptic-curve-based variants of ElGamal are the most commonly deployed public-key cryptosystems, we present a brief comparison.

Popularity of RSA

There’s no doubt that historically RSA has been the most popular public-key cryptosystem by far. There are several possible reasons for this:

• Maturity: RSA was one of the first public-key cryptosystems to be proposed and was the first to gain widespread recognition. That’s why in many senses, RSA is the brand leader.

• Less message expansion: ElGamal involves message expansion by default, making its use potentially undesirable. The ‘textbook’ version of RSA has no message expansion, and RSA-OAEP has limited message expansion.

• Marketing: The use of RSA was marketed early by a commercial company. Indeed, it was, at one time, subject to patent in certain parts of the world. ElGamal has not had such successful commercial backing. However, ECC does, and there are several patents on ECC primitives.

Performance issues

Compared with most symmetric encryption algorithms, neither RSA nor any variants of ElGamal are particularly efficient. The main problem is that in each case, encryption involves exponentiation, which has complexity $n3$. This means that although it is easy to compute, it’s not as efficient as other more straightforward operations such as addition (complexity $n$) and multiplication (complexity $n^2$ ).

In this respect, RSA is more efficient for encryption than ElGamal variants since it only requires one exponentiation (and by choosing the exponent $e$ to have a certain format, this can be made to be a faster-than-average exponentiation computation). Meanwhile, ElGamal variants need two exponentiations. However, as we already noted, the computation of $C_1$ could be done in advance, and so some people argue that there is very little difference in computational efficiency.

In contrast, decryption is slightly more efficient for ElGamal variants than RSA. The decryption exponentiation is typically performed with a smaller exponent than for RSA. Suppose the exponent is carefully chosen, even with the additional ElGamal decryption costs of running the extended Euclidean algorithm. If the exponent is carefully chosen, then even with the additional ElGamal decryption costs of running the extended Euclidean algorithm, the result is typically a more efficient computation than an RSA decryption based on a much larger exponent.

There has been a lot of work invested in speeding up the exponentiation process to make RSA and ElGamal variants more efficient. Combining clever engineering and mathematical expertise has led to faster implementations, but they are all slower than symmetric computations. For this reason, none of these public-key cryptosystems are normally used for bulk data encryption.

Security issues

To compare different public-key cryptosystems, we first need to establish a means of relating the security of one public-key cryptosystem to another.