Cryptography Reference
In-Depth Information
Chapter 11
An Introduction to Elliptic Curve
Cryptography
Elliptic curves play a very important role in central areas of mathematics and, in
particular, in
arithmetic algebraic geometry
which, as suggested by its name, is a
meeting point for number theory, algebra and geometry. The study of elliptic curves
dates back to the nineteenth century and, to mention only a particularly relevant
milestone, they played a fundamental role in Andrew Wiles' proof of Fermat's Last
Theorem, completed in 1994.
The first connection between elliptic curves and cryptography was an indirect one
that arose in 1984, when Hendrik Lenstra discovered his integer factoring algorithm
that relies on elliptic curves (Elliptic Curve Method or ECM, for short). The running
time of this algorithm is dominated by the size of the smallest factor rather than by
the size of the integer being factored and ECM is not effective to factor, say, RSA
moduli
1
(ECM is, however, a useful ingredient for other factoring algorithms of
cryptographic interest, such as NFS). The discovery of ECM stimulated researchers
to investigate other possible applications of elliptic curves to cryptography and, as
a consequence, a strong connection between the two fields was established just one
year later. This happened in 1985, whenKoblitz [117] andMiller [142] independently
suggested the use of elliptic curve groups to implement cryptographic schemes that
rely on the difficulty of the DLP on these groups.
As we have seen in previous chapters, many cryptographic schemes, including
those that are DLP-based, live naturally in finite abelian groups. As we shall soon
see, elliptic curves provide an abundant source for these groups and hence a spe-
cific setting where these schemes may be implemented giving rise to elliptic curve
cryptography (ECC). The cryptographic theory developed in the preceding chapters
applies generically to elliptic curve-based schemes, for which the results obtained are
valid as far as the relevant assumptions—such as, for example, hardness of the DLP or
the DDH problem—hold. From this point of view it would not be strictly necessary to
go into the details of elliptic curve cryptography but, on the other hand, there are also
reasons to include some specific explanations as we are going to do in this chapter.
1
The largest factor it has found as of this writing is a 73-digit one discovered in March, 2010.
