Cryptography Reference
In-Depth Information
For this reason ElGamal is rarely implemented in practice in the form that
we have just described. However, as we will shortly discuss, elliptic-curve-based
variants of ElGamal allow the size of the keys to become sufficiently small that,
despite this message expansion, they are often preferred over RSA for efficiency
reasons.
5.3.5
Elliptic Curve Cryptography
Elliptic Curve Cryptography
(ECC) is a phrase used to describe a suite of
cryptographic primitives and protocols whose security is based on special versions
of the discrete logarithm problem. Instead of using the numbers modulo
p
,
ECC is based on different sets of numbers. These numbers are associated
with mathematical objects called
elliptic curves
. There are rules for adding and
computing multiples of these numbers, just as there are for numbers modulo
p
.
We will not concern ourselves here with any of the details of elliptic curves or
how to combine the points on such a curve.
ECC includes a number of variants of cryptographic primitives that were
first designed for modular numbers. As well as variants of ElGamal encryption,
these include an elliptic-curve-based variant of the Diffie-Hellman key agreement
protocol (see Section 9.4.2), and an elliptic-curve-based variant of the Digital
Signature Algorithm (see Section 7.3.6).
The advantage of switching from numbers modulo
p
to points on an elliptic
curve is that it is believed that the discrete logarithm problem is
much harder
when applied to points on an elliptic curve. The important implication of this is
that an equivalent security level can be obtained for shorter keys if we use elliptic-
curve-based variants. We will show the approximate extent of this reduction in
Section 5.4.
The many advantages of shorter keys, both in terms of key management
and efficient computation (see Section 10.2), make elliptic-curve-based variants
highly attractive for many application environments. ECC primitives are being
increasingly adopted, especially in resource-constrained environments.
Since RSA and elliptic-curve-based variants of ElGamal are the most commonly
deployed public-key cryptosystems, in this section we present a brief comparison.
5.4.1
Popularity of RSA
Historically there is no doubt that RSAhas been by far themost popular public-key
cryptosystem. There are several possible reasons for this:
