An Introduction to Elliptic Curve Cryptography - Introduction to Cryptography with Maple - page 642

11.3 The Elliptic Curve Discrete Logarithm Problem

We have discussed the discrete logarithmproblem(DLP) inSect. 6.5 andwe have seen
that the hardness of this problem is a necessary condition for the security of a number
of cryptographic schemes. The DLPwas formulated in an arbitrary group G and some
of the algorithms to solve it which we have seen are generic in the sense that they
do not exploit any special properties of the group nor of the encoding of its elements
as strings, and hence work for arbitrary groups. It is then clear that the problem
can be specialized to elliptic curve groups (over finite fields) and that the generic
algorithms will work in these groups. However, the most efficient algorithms to solve
the DLP, namely, those collectively known as the index calculus method , use specific
information about the groups in which they are applied—only the multiplicative
groups of finite fields for now—to achieve subexponential complexity in contrast
with the fully exponential complexity of generic algorithms.
The purpose of this section is to briefly review the DLP in the concrete setting
of elliptic curve groups and, in particular, the aspects related to the hardness of
the problem and its cryptographic applications. First we recall the definition of the
problem and establish the basic notation:

F q , P ∈ ( F q )

Definition 11.3 Let E be an elliptic curve over a finite field E a

∈ ( F q )

point of order n , and Q generated by P .

An instance of the elliptic curve discrete logarithm problem (ECDLP) is to find the
element l

P a point in the subgroup of E

∈ Z n such that Q = lP . As usual we denote:

l = log P Q ,

and l is called the discrete logarithm of Q to the base P.

Remark 11.4 Note that, as we have seen in our general discussion in Sect. 6.5 , the
discrete logarithm is only definedmodulo the order n of P and hence wemay regard it
as an element of Z n , which can also be thought of as an integer in the interval [ 0 , n − 1 ] .

Thus the discrete log function defines a group isomorphism log P →Z n that,

as we have seen, is the inverse of the “discrete exponential isomorphism” which now,
since the group

: P

P is additive, is really the “multiplication isomorphism” assigning

∈ Z n the point kP ∈

to each k P .

The most basic algorithm to solve the ECDLP is the brute-force method that does
an exhaustive search and successively computes P until Q is found.

We may compare the ECDLP to the problem of computing the order of a point P ,
since the latter is just an instance of the former, namely, to compute log P O

, 2 P , 3 P ...

. There
is a crucial difference between the two problems though, which is the fact that if
we want to compute the order of a point and we assume that the factorization of
the group order is known, then Lagrange's theorem tells us that the point order is a
divisor of the group order and so, instead of computing the multiples of the point
by all positive integers we only have to compute the multiples by these divisors.