Cryptography Reference
In-Depth Information
Maturity
. RSA was one of the first public-key cryptosystems to be proposed and
was the first to gain widespread recognition. Thus, in many senses, RSA is the
'brand-leader'.
Lack of message expansion
. ElGamal involves message expansion by default,
which made its use potentially undesirable. Note that while 'textbook' RSA
does not, RSA-OAEP involves a degree of message expansion.
Marketing
. The use of RSA was marketed from an early stage by a commercial
company. Indeed, it was at one stage subject to patent in certain parts of the
world. ElGamal has not had such successful commercial backing. However,
ECC does, and there are a number of patents on ECC primitives.
5.4.2
Performance issues
In comparison with most symmetric encryption algorithms, neither RSA nor any
variants of ElGamal are particularly efficient. Themain problem is that in each case
encryption involves exponentiation. We saw in Section 3.2.3 that exponentiation
has complexity
n
3
. This means that it is easy to compute but is 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), whereas ElGamal variants need two. However, we already noted in
Section 5.3.4 that 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
for RSA. This is because running the Extended Euclidean Algorithm, which is
necessary for ElGamal-based decryption, is a more efficient computation than an
exponentiation, which is necessary for RSA decryption.
There has been a lot of work invested in trying to speed up the exponentiation
process in order tomake RSA and ElGamal variantsmore efficient. A combination
of clever engineering and mathematical expertise has led to faster implementa-
tions, but they are all slower than symmetric computations. For this reason none
of these public-key cryptosystems are normally used for bulk data encryption (see
Section 5.5).
5.4.3
Security issues
In order to compare different public-key cryptosystems, we first need to establish
a means of relating the security of one public-key cryptosystem to another.
KEY LENGTHS OF PUBLIC-KEY CRYPTOSYSTEMS
Just as for symmetric cryptosystems, the length of a private (decryption) key is an
important parameter of a public-key cryptosystem and is one that can be used to
