Cryptography Reference
In-Depth Information
than implementations of symmetric ciphers such as 3DES, they are considerably
smaller than RSA implementations.
The computational complexity of ECC is cubic in the bit length of the prime
used. This is due to the fact that modular multiplication, which is the main operation
on the bottom layer, is quadratic in the bit length, and scalar multiplication (i.e.,
with the Double-and-Add algorithm) contributes another linear dimension, so that
we have, in total, a cubic complexity. This implies that doubling the bit length of
an ECC implementation results in performance degradation by a factor of roughly
2
3
= 8. RSA and DL systems show the same cubic runtime behavior. The advantage
of ECC over the other two popular public-key families is that the parameters have to
be increased much more slowly to enhance the security level. For instance, doubling
the effort of an attacker for a given ECC system requires an increase in the length
of the parameter by 2 bits, whereas RSA or DL schemes require an increase of 20-
30 bits. This behavior is due to the fact that only generic attacks (cf. Sect. 8.3.3)
are known ECC cryptosystems, whereas more powerful algorithms are available for
attacking RSA and DL schemes.
9.6 Discussion and Further Reading
History and General Remarks
ECC was independently invented in 1987 by Neal
Koblitz and in 1986 by Victor Miller. During the 1990s there was much speculation
about the security and practicality of ECC, especially if compared to RSA. After a
period of intensive research, they appear nowadays very secure, just like RSA and
DL schemes. An important step for building confidence in ECC was the issuing of
two ANSI banking standards for elliptic curve digital signature and key establish-
ment in 1999 and 2001, respectively [6, 7]. Interestingly, in Suite B—a collection
of crypto algorithms selected by the NSA for use in US government systems—only
ECC schemes are allowed as asymmetric algorithms [130]. Elliptic curves are also
widely used in commercial standards such as IPsec or Transport Layer Security
(TLS).
At the time of writing, there still exist far more fielded RSA and DL applications
than elliptic curve ones. This is mainly due to historical reasons and due to the quite
complex patent situation of some ECC variants. Nevertheless, in many new applica-
tions with security needs, especially in embedded systems such as mobile devices,
ECC is often the preferred public-key scheme. For instance, ECC is used in the most
popular business handheld devices. Most likely, ECC will become more widespread
in the years to come. Reference [100] describes the historical development of ECC
with respect to scientific and commercial aspects, and makes excellent reading.
For readers interested in a deeper understanding of ECC, the topics [25, 24, 90,
44] are recommended. The overview article [103], even though a bit dated now,
provides a good state-of-the-art summary as of the year 2000. For more recent de-
velopments, the annual
Workshop on Elliptic Curve Cryptography (ECC)
is recom-
mended as an excellent resource [166]. The workshop includes both theoretical and
