. 1
( 2)



>>

Chapter 5
The Discrete Logarithm
Problem

Let p be a prime and let a, b be integers that are nonzero mod p. Suppose we
know that there exists an integer k such that

ak ≡ b (mod p).

The classical discrete logarithm problem is to ¬nd k. Since k + (p ’ 1) is
also a solution, the answer k should be regarded as being de¬ned mod p ’ 1,
or mod a divisor d of p ’ 1 if ad ≡ 1 (mod p).
More generally, let G be any group, written multiplicatively for the moment,
and let a, b ∈ G. Suppose we know that ak = b for some integer k. In this
context, the discrete logarithm problem is again to ¬nd k. For example, G
could be the multiplicative group F— of a ¬nite ¬eld. Also, G could be E(Fq )
q
for some elliptic curve, in which case a and b are points on E and we are
trying to ¬nd an integer k with ka = b.
In Chapter 6, we™ll meet several cryptographic applications of the discrete
logarithm problem. The security of the cryptosystems will depend on the
di¬culty of solving the discrete log problem.
One way of attacking a discrete log problem is simple brute force: try all
possible values of k until one works. This is impractical when the answer k
can be an integer of several hundred digits, which is a typical size used in
cryptography. Therefore, better techniques are needed.
In this chapter, we start by discussing an attack, called the index calculus,
that can be used in F— , and more generally in the multiplicative group of a
p
¬nite ¬eld. However, it does not apply to general groups. Then we discuss the
method of Pohlig-Hellman, the baby step, giant step method, and Pollard™s ρ
and » methods. These work for general ¬nite groups, in particular for elliptic
curves. Finally, we show that for special classes of elliptic curves, namely
supersingular and anomalous curves, it is possible to reduce the discrete log
problem to easier discrete log problems (in the multiplicative group of a ¬nite
¬eld and in the additive group of integers mod a prime, respectively).


143

© 2008 by Taylor & Francis Group, LLC
144 CHAPTER 5 THE DISCRETE LOGARITHM PROBLEM




5.1 The Index Calculus
Let p be a prime and let g be primitive root (see Appendix A) mod p,
which means that g is a generator for the cyclic group F— . In other words,
p
every h ≡ 0 (mod p) can be written in the form h ≡ g k for some integer k
that is uniquely determined mod p ’ 1. Let k = L(h) denote the discrete
logarithm of h with respect to g and p, so

g L(h) ≡ h (mod p).

Suppose we have h1 and h2 . Then

g L(h1 h2 ) ≡ h1 h2 ≡ g L(h1 )+L(h2 ) (mod p),

which implies that

L(h1 h2 ) ≡ L(h1 ) + L(h2 ) (mod p ’ 1).

Therefore, L changes multiplication into addition, just like the classical loga-
rithm function.
The index calculus is a method for computing values of the discrete log
function L. The idea is to compute L( ) for several small primes , then use
this information to compute L(h) for arbitrary h. It is easiest to describe the
method with an example.


Example 5.1
Let p = 1217 and g = 3. We want to solve 3k ≡ 37 (mod 1217). Most
of our work will be precomputation that will be independent of the number
37. Let™s choose a set of small primes, called the factor base, to be B =
{2, 3, 5, 7, 11, 13}. First, we ¬nd relations of the form

3x ≡ ±product of some primes in B (mod 1217).

Eventually, we ¬nd the following:

31 ≡ 3 (mod 1217)
324 ≡ ’22 · 7 · 13
325 ≡ 53
330 ≡ ’2 · 52
354 ≡ ’5 · 11
387 ≡ 13

These can be changed into equations for discrete logs, where now the congru-
ences are all mod p’1 = 1216. Note that we already know that 3(p’1)/2 ≡ ’1




© 2008 by Taylor & Francis Group, LLC
145
SECTION 5.1 THE INDEX CALCULUS

(mod p), so L(’1) = 608.

1 ≡ L(3) (mod 1216)
≡ 608 + 2L(2) + L(7) + L(13)
24
≡ 3L(5)
25
≡ 608 + L(2) + 2L(5)
30
≡ 608 + L(5) + L(11)
54
87 ≡ L(13)

The ¬rst equation yields L(3) ≡ 1. The third yields L(5) ≡ 819 (mod 1216).
The sixth yields L(13) ≡ 87. The fourth gives

L(2) ≡ 30 ’ 608 ’ 2 · 819 ≡ 216 (mod 1216).

The ¬fth yields L(11) ≡ 54 ’ 608 ’ L(5) ≡ 1059. Finally, the second gives

L(7) ≡ 24 ’ 608 ’ 2L(2) ’ L(13) ≡ 113 (mod 1216).

We now know the discrete logs of all the elements of the factor base.
Recall that we want to solve 3k ≡ 37 (mod 1216). We compute 3j · 37
(mod p) for several random values of j until we obtain an integer that can be
factored into a product of primes in B. In our case, we ¬nd that

316 · 37 ≡ 23 · 7 · 11 (mod 1217).

Therefore,

L(37) ≡ 3L(2) + L(7) + L(11) ’ 16 ≡ 588 (mod 1216),

and 3588 ≡ 37 (mod 1217).

The choice of the size of the factor base B is important. If B is too small,
then it will be very hard to ¬nd powers of g that factor with primes in B. If B
is too large, it will be easy to ¬nd relations, but the linear algebra needed to
solve for the logs of the elements of B will be unwieldy. An example that was
completed in 2001 by A. Joux and R. Lercier used the ¬rst 1 million primes
to compute discrete logs mod a 120-digit prime.
There are various methods that produce relations of the form g x ≡ product
of primes in B. A popular one uses the number ¬eld sieve. See [58].
The expected running time of the index calculus is approximately a constant

times exp( 2 ln p ln ln p) (see [81, p. 129]), which means that it is a subex-
ponential algorithm. The algorithms in Section 5.2, which are exponential


algorithms, run in time approximately p = exp( 1 ln p). Since 2 ln p ln ln p
2
is much smaller than 1 ln p for large p, the index calculus is generally much
2
faster when it can be used.




© 2008 by Taylor & Francis Group, LLC
146 CHAPTER 5 THE DISCRETE LOGARITHM PROBLEM

Note that the index calculus depends heavily on the fact that integers can
be written as products of primes. An analogue of this is not available for
arbitrary groups.
There is a generalization of the index calculus that works for ¬nite ¬elds,
but it requires some algebraic number theory, so we do not discuss it here.
In Section 13.4, we show how an analogue of the index calculus can be
applied to groups arising from hyperelliptic curves.




5.2 General Attacks on Discrete Logs
In this section, we discuss attacks that work for arbitrary groups. Since our
main focus is elliptic curves, we write our group G additively. Therefore, we
are given P, Q ∈ G and we are trying to solve kP = Q (we always assume
that k exists). Let N be the order of G. Usually, we assume N is known. For
simplicity, it is usually assumed that P generates G.




5.2.1 Baby Step, Giant Step

This method, developed by D. Shanks [107], requires approximately N

steps and around N storage. Therefore it only works well for moderate
sized N . The procedure is as follows.

1. Fix an integer m ≥ N and compute mP .

2. Make and store a list of iP for 0 ¤ i < m.

3. Compute the points Q ’ jmP for j = 0, 1, · · · m ’ 1 until one matches
an element from the stored list.

4. If iP = Q ’ jmP , we have Q = kP with k ≡ i + jm (mod N ).

Why does this work? Since m2 > N , we may assume the answer k satis¬es
0 ¤ k < m2 . Write k = k0 + mk1 with k0 ≡ k (mod m) and 0 ¤ k0 < m and
let k1 = (k ’ k0 )/m. Then 0 ¤ k1 < m. When i = k0 and j = k1 , we have

Q ’ k1 mP = kP ’ k1 mP = k0 P,

so there is a match.
The point iP is calculated by adding P (a “baby step”) to (i ’ 1)P . The
point Q ’ jmP is computed by adding ’mP (a “giant step”) to Q ’ (j ’
1)mP . The method was developed by Shanks for computations in algebraic
number theory.




© 2008 by Taylor & Francis Group, LLC
147
SECTION 5.2 GENERAL ATTACKS ON DISCRETE LOGS

Note that we did not need to know the exact order N of G. We only
required an upper bound for N . Therefore, for elliptic curves over Fq , we

could use this method with m2 ≥ q + 1 + 2 q, by Hasse™s theorem.
A slight improvement of the method can be made for elliptic curves by
computing and storing only the points iP for 0 ¤ i ¤ m/2 and checking
whether Q ’ jmP = ±iP (see Exercise 5.1).


Example 5.2
Let G = E(F41 ), where E is given by y 2 = x3 + 2x + 1. Let P = (0, 1) and
Q = (30, 40). By Hasse™s theorem, we know that the order of G is at most 54,
so we let m = 8. The points iP for 1 ¤ i ¤ 7 are

(0, 1), (1, 39), (8, 23), (38, 38), (23, 23), (20, 28), (26, 9).

We calculate Q ’ jmP for j = 0, 1, 2 and obtain

(30, 40), (9, 25), (26, 9),

at which point we stop since this third point matches 7P . Since j = 2 yielded
the match, we have

(30, 40) = (7 + 2 · 8)P = 23P.

Therefore k = 23.




5.2.2 Pollard™s ρ and » Methods
A disadvantage of the Baby Step, Giant Step method is that it requires a
lot of storage. Pollard™s ρ and » methods [87] run in approximately the same
time as Baby Step, Giant Step, but require very little storage. First, we™ll
discuss the ρ method, then its generalization to the » method.
Let G be a ¬nite group of order N . Choose a function f : G ’ G that
behaves rather randomly. Then start with a random element P0 and compute
the iterations Pi+1 = f (Pi ). Since G is a ¬nite set, there will be some indices
i0 < j0 such that Pi0 = Pj0 . Then

Pi0 +1 = f (Pi0 ) = f (Pj0 ) = Pj0 +1 ,

and, similarly, Pi0 + = Pj0 + for all ≥ 0. Therefore, the sequence Pi is
periodic with period j0 ’ i0 (or possibly a divisor of j0 ’ i0 ). The picture
describing this process (see Figure 5.1) looks like the Greek letter ρ, which
is why it is called Pollard™s ρ method. If f is a randomly chosen random
function (we™ll not make this precise), then we expect to ¬nd a match with j0

at most a constant times N . For an analysis of the running time for various
choices of function f , see [119].




© 2008 by Taylor & Francis Group, LLC
148 CHAPTER 5 THE DISCRETE LOGARITHM PROBLEM

A naive implementation of the method stores all the points Pi until a match

is found. This takes around N storage, which is similar to Baby Step, Giant
Step. However, as R. W. Floyd has pointed out, it is possible to do much better
at the cost of a little more computation. The key idea is that once there is a
match for two indices di¬ering by d, all subsequent indices di¬ering by d will
yield matches. This is just the periodicity mentioned above. Therefore, we
can compute pairs (Pi , P2i ) for i = 1, 2, . . . , but only keep the current pair;
we don™t store the previous pairs. These can be calculated by the rules

Pi+1 = f (Pi ), P2(i+1) = f (f (P2i )).

Suppose i ≥ i0 and i is a multiple of d. Then the indices 2i and i di¬er by a
multiple of d and hence yield a match: Pi = P2i . Since d ¤ j0 and i0 < j0 , it
follows easily that there is a match for i ¤ j0 . Therefore, the number of steps

to ¬nd a match is expected to be at most a constant multiple of N .
Another method of ¬nding a match is to store only those points Pi that
satisfy a certain property (call them “distinguished points”). For example, we
could require the last k bits of the binary representation of the x-coordinate to
be 0. We then store, on the average, one out of every 2k points Pi . Suppose
there is a match Pi = Pj but Pi is not one of these distinguished points.
We expect Pi+ to be a distinguished point for some with 1 ¤ ¤ 2k ,
approximately. Then Pj+ = Pi+ , so we ¬nd a match between distinguished
points with only a little more computation.
The problem remains of how to choose a suitable function f . Besides having
f act randomly, we need to be able to extract useful information from a match.
Here is one way of doing this. Divide G into s disjoint subsets S1 , S2 , . . . , Ss
of approximately the same size. A good choice for s seems to be around 20.
Choose 2s random integers ai , bi mod N . Let

Mi = ai P + bi Q.

Finally, de¬ne
if g ∈ Si .
f (g) = g + Mi
The best way to think of f is as giving a random walk in G, with the possible
steps being the elements Mi .
Finally, choose random integers a0 , b0 and let P0 = a0 P +b0 Q be the starting
point for the random walk. While computing the points Pj , we also record
how these points are expressed in terms of P and Q. If Pj = uj P + vj Q and
Pj+1 = Pj + Mi , then Pj+1 = (uj + ai )P + (vj + bi )Q, so (uj+1 , vj+1 ) =
(uj , vj ) + (ai , bi ). When we ¬nd a match Pj0 = Pi0 , then we have

uj0 P + vj0 Q = ui0 P + vi0 Q, hence (ui0 ’ uj0 )P = (vj0 ’ vi0 )Q.

If gcd(vj0 ’ vi0 , N ) = d, we have

k ≡ (vj0 ’ vi0 )’1 (ui0 ’ uj0 ) (mod N/d).




© 2008 by Taylor & Francis Group, LLC
149
SECTION 5.2 GENERAL ATTACKS ON DISCRETE LOGS




P59 P6
P58 P5
P4
P3
P2
P1
P0
Figure 5.1
Pollard™s Rho Method


This gives us d choices for k. Usually, d will be small, so we can try all
possibilities until we have Q = kP .
In cryptographic applications, N is often prime, in which case, d = 1 or
N . If d = N , we have a trivial relation (the coe¬cients of both P and Q are
multiples of N ), so we start over. If d = 1, we obtain k.


Example 5.3
Let G = E(F1093 ), where E is the elliptic curve given by y 2 = x3 + x + 1.
We™ll use s = 3. Let P = (0, 1) and Q = (413, 959). It can be shown that the
order of P is 1067. We want to ¬nd k such that kP = Q. Let

P0 = 3P + 5Q, M0 = 4P + 3Q, M1 = 9P + 17Q, M2 = 19P + 6Q.

Let f : E(F1093 ) ’ E(F1093 ) be de¬ned by

if x ≡ i (mod 3).
f (x, y) = (x, y) + Mi

Here the number x is regarded as an integer 0 ¤ x < 1093 and is then reduced
mod 3. For example,

f (P0 ) = P0 + M2 = (727, 589),

since P0 = (326, 69) and 326 ≡ 2 (mod 3).
We can de¬ne f (∞) = ∞ if we want. However, if we encounter f (∞), we
have found a relation of the form aP + bQ = ∞ and can ¬nd k easily (if the
relation isn™t something trivial like 1067P +2134Q = ∞). Therefore, we don™t
worry about ∞.




© 2008 by Taylor & Francis Group, LLC
150 CHAPTER 5 THE DISCRETE LOGARITHM PROBLEM

If we compute P0 , P1 = f (P0 ), P2 = f (P1 ), . . . , we obtain

P0 = (326, 69), P1 = (727, 589), P2 = (560, 365), P3 = (1070, 260),
P4 = (473, 903), P5 = (1006, 951), P6 = (523, 938), . . . ,
P57 = (895, 337), P58 = (1006, 951), P59 = (523, 938), . . . .

Therefore, the sequence starts repeating at P5 = P58 .
If we keep track of the coe¬cients of P and Q in the calculations, we ¬nd
that
P5 = 88P + 46Q and P58 = 685P + 620Q.
Therefore,
∞ = P58 ’ P5 = 597P + 574Q.
Since P has order 1067, we calculate

’574’1 597 ≡ 499 (mod 1067).

Therefore, Q = 499P , so k = 499.
We stored all of the points P0 , P1 , . . . , P58 until we found a match. Instead,
let™s repeat the computation, but compute the pairs (Pi , P2i ) and store nothing
except the current pair. We then ¬nd that for i = 53 there is the match
P53 = P106 . This yields

620P + 557Q = P53 = P106 = 1217P + 1131Q.

Therefore, 597P + 574Q = ∞, which yields k = 499, as before.

Pollard™s » method uses a function f as in the ρ method, but several
(1) (r)
random starting points P0 , . . . , P0 are used. We then get sequences de¬ned
by
() ()
Pi+1 = f (Pi ), 1 ¤ ¤ r, i = 0, 1, 2, . . . .
These can be computed by several computers in parallel. Points satisfying
certain conditions are called distinguished and are reported to a central com-
puter. When a match is found among the inputs from the various computers,
we have a relation that should allow us to solve the discrete log problem, as
in the ρ method. When there is a match between two sequences, these two
sequences will always match from that point on. We only need to look at
distinguished points because distinguished points should occur soon after a
match occurs.
When there are only two random starting points, we have two random
walks. Eventually they will have a point in common, and therefore they will
coincide thereafter. The picture of this process resembles the Greek letter »,
hence the name.
Sometimes the » method is described in terms of kangaroos jumping around
a ¬eld (this is the random walk). A variant of the » method with two random




© 2008 by Taylor & Francis Group, LLC
151
SECTION 5.2 GENERAL ATTACKS ON DISCRETE LOGS

walks records every 10th point, for example, in the ¬rst sequence and then
checks whether the second sequence matches any of these points. In this case,
the ¬rst sequence is called a tame kangaroo, and the second is called a wild
kangaroo. The idea is to use the tame kangaroo to catch the wild kangaroo. √
The » method is expected to ¬nd a match in at most a constant times N
steps. If it is run in parallel with many starting points, the running time can
be improved signi¬cantly.
Finally, we should point out a di¬erence between the baby step, giant step
method and the ρ and » methods. The baby step, giant step method is de-
terministic, which means that it is guaranteed to ¬nish within the predicted

time of a constant times N . On the other hand, the ρ and » methods are
probabilistic, which means that there is a very high probability that they
will ¬nish within the predicted time, but this is not guaranteed.




5.2.3 The Pohlig-Hellman Method
As before, P, Q are elements in a group G and we want to ¬nd an integer
k with Q = kP . We also know the order N of P and we know the prime
factorization
e
qi i
N=
i
e
of N . The idea of Pohlig-Hellman is to ¬nd k (mod qi i ) for each i, then use
the Chinese Remainder theorem to combine these and obtain k (mod N ).
Let q be a prime, and let q e be the exact power of q dividing N . Write k
in its base q expansion as

k = k0 + k1 q + k2 q 2 + · · ·

with 0 ¤ ki < q. We™ll evaluate k (mod q e ) by successively determining
k0 , k1 , . . . , ke’1 . The procedure is as follows.

|0 ¤ j ¤ q ’ 1 .
N
1. Compute T = j qP

N N
2. Compute q Q. This will be an element k0 qP of T .

3. If e = 1, stop. Otherwise, continue.

4. Let Q1 = Q ’ k0 P .
N N
5. Compute q 2 Q1 . This will be an element k1 qP of T .

6. If e = 2, stop. Otherwise, continue.

7. Suppose we have computed k0 , k1 , . . . , kr’1 , and Q1 , . . . , Qr’1 .




© 2008 by Taylor & Francis Group, LLC
152 CHAPTER 5 THE DISCRETE LOGARITHM PROBLEM

8. Let Qr = Qr’1 ’ kr’1 q r’1 P .

N N
9. Determine kr such that q r+1 Qr = kr qP .

10. If r = e ’ 1, stop. Otherwise, return to step (7).

Then
k ≡ k0 + k1 q + · + ke’1 q e’1 (mod q e ).
Why does this work? We have

N N
Q = (k0 + k1 q + · · · )P
q q
N N
= k0 P + (k1 + k2 q + · · · )N P = k0 P,
q q

since N P = ∞. Therefore, step (2) ¬nds k0 . Then

Q1 = Q ’ k0 P = (k1 q + k2 q 2 + · · · )P,

so
N N
Q1 = (k1 + k2 q + · · · ) P
q2 q
N N
= k1 P + (k2 + k3 q + · · · )N P = k1 P.
q q

Therefore, we ¬nd k1 . Similarly, the method produces k2 , k3 , . . . . We have
to stop after r = e ’ 1 since N/q e+1 is no longer an integer, and we cannot
multiply Qe by the noninteger N/q e+1 . Besides, we do not need to continue
because we now know k mod q e .


Example 5.4
Let G = E(F599 ), where E is the elliptic curve given by y 2 = x3 + 1. Let
P = (60, 19) and Q = (277, 239). The methods of Section 4.3.3 can be used
to show that P has order N = 600. We want to solve Q = kP for k. The
prime factorization of N is

600 = 23 · 3 · 52 .

We™ll compute k mod 8, mod 3, and mod 25, then recombine to obtain k mod
600 (the Chinese Remainder Theorem allows us to do this).
k mod 8. We compute T = {∞, (598, 0)}. Since

N
(N/2)Q = ∞ = 0 · P ,
2




© 2008 by Taylor & Francis Group, LLC
153
SECTION 5.2 GENERAL ATTACKS ON DISCRETE LOGS

we have k0 = 0. Therefore,

Q1 = Q ’ 0P = Q.

Since (N/4)Q1 = 150Q1 = (598, 0) = 1 · N
2 P, we have k1 = 1. Therefore,

Q2 = Q1 ’ 1 · 2 · P = (35, 243).

Since (N/8)Q2 = 75Q2 = ∞ = 0 · N
2 P, we have k2 = 0. Therefore,

k = 0 + 1 · 2 + 0 · 4 + · · · ≡ 2 (mod 8).

k mod 3. We have T = {∞, (0, 1), (0, 598)}. Since

N
(N/3)Q = (0, 598) = 2 · P,
3
we have k0 = 2. Therefore,

k ≡ 2 (mod 3).

k mod 25. We have

T = {∞, (84, 179), (491, 134), (491, 465), (84, 420)}.

Since (N/5)Q = (84, 179), we have k0 = 1. Then

Q1 = Q ’ 1 · P = (130, 129).

Since (N/25)Q1 = (491, 465), we have k1 = 3. Therefore,

k = 1 + 3 · 5 + · · · ≡ 16 (mod 25).

We now have the simultaneous congruences
§
⎨ x ≡ 2 (mod 8)
x ≡ 2 (mod 3) .
©
x ≡ 16 (mod 25)

These combine to yield k ≡ 266 (mod 600), so k = 266.

The Pohlig-Hellman method works well if all of the prime numbers dividing
N are small. However, if q is a large prime dividing N , then it is di¬cult to
list the elements of T , which contains q elements. We could try to ¬nd the ki
without listing the elements; however, ¬nding ki is a discrete log problem in
the group generated by (N/q)P , which has order q. If q is of the same order of
magnitude as N (for example, q = N or q = N/2), then the Pohlig-Hellman
method is of little use. For this reason, if a cryptographic system is based on




© 2008 by Taylor & Francis Group, LLC
154 CHAPTER 5 THE DISCRETE LOGARITHM PROBLEM

discrete logs, the order of the group should be chosen so it contains a large
prime factor.
If N contains some small prime factors, then the Pohlig-Hellman method
can be used to obtain partial information on the value of k, namely a congru-
ence modulo a product of these small prime factors. In certain cryptographic
situations, this could be undesirable. Therefore, the group G is often chosen
to be of large prime order. This can be accomplished by starting with a group
that has a large prime q in its order. Pick a random point P1 and compute
its order. With high probability (at least 1 ’ 1/q; cf. Remark 5.2), the order
of P1 is divisible by q, so in a few tries, we can ¬nd such a point P1 . Write
the order of P1 as qm. Then P = mP1 will have order q. As long as q is
su¬ciently large, discrete log problems in the cyclic group generated by P
will resist the Pohlig-Hellman attack.




5.3 Attacks with Pairings
One strategy for attacking a discrete logarithm problem is to reduce it to an
easier discrete logarithm problem. This can often be done with pairings such
as the Weil pairing or the Tate-Lichtenbaum pairing, which reduce a discrete
logarithm problem on an elliptic curve to one in the multiplicative group of a
¬nite ¬eld.




5.3.1 The MOV Attack
The MOV attack, named after Menezes, Okamoto, and Vanstone [80], uses
the Weil pairing to convert a discrete log problem in E(Fq ) to one in F— . qm
Since discrete log problems in ¬nite ¬elds can be attacked by index calculus
methods, they can be solved faster than elliptic curve discrete log problems, as
long as the ¬eld Fqm is not much larger than Fq . For supersingular curves, we
can usually take m = 2, so discrete logarithms can be computed more easily
for these curves than for arbitrary elliptic curves. This is unfortunate from a
cryptographic standpoint since an attractive feature of supersingular curves
is that calculations can often be done quickly on them (see Section 4.6).
Recall that for an elliptic curve E de¬ned over Fq , we let E[N ] denote the
set of points of order dividing N with coordinates in the algebraic closure. If
gcd(q, N ) = 1 and S, T ∈ E[N ], then the Weil pairing eN (S, T ) is an N th root
of unity and can be computed fairly quickly. The pairing is bilinear, and if
{S, T } is a basis for E[N ], then eN (S, T ) is a primitive N th root of unity. For
any S, eN (S, S) = 1. For more properties of the Weil pairing, see Sections 3.3
and 11.2.




© 2008 by Taylor & Francis Group, LLC
155
SECTION 5.3 ATTACKS WITH PAIRINGS

Let E be an elliptic curve over Fq . Let P, Q ∈ E(Fq ). Let N be the order
of P . Assume that
gcd(N, q) = 1.
We want to ¬nd k such that Q = kP . First, it™s worthwhile to check that k
exists.


LEMMA 5.1
There exists k such that Q = kP if and only if N Q = ∞ and the Weil paring
eN (P, Q) = 1.

If Q = kP , then N Q = kN P = ∞. Also,
PROOF

eN (P, Q) = eN (P, P )k = 1k = 1.

Conversely, if N Q = ∞, then Q ∈ E[N ]. Since gcd(N, q) = 1, we have
E[N ] ZN • ZN , by Theorem 3.2. Choose a point R such that {P, R} is a
basis of E[N ]. Then
Q = aP + bR
for some integers a, b. By Corollary 3.10, eN (P, R) = ζ is a primitive N th
root of unity. Therefore, if eN (P, Q) = 1, we have

1 = eN (P, Q) = eN (P, P )a eN (P, R)b = ζ b .

This implies that b ≡ 0 (mod N ), so bR = ∞. Therefore, Q = aP , as desired.


The idea used to prove the lemma yields the MOV attack on discrete logs
for elliptic curves. Choose m so that

E[N ] ⊆ E(Fqm ).

Since all the points of E[N ] have coordinates in Fq = ∪j≥1 Fqj , such an m
exists. By Corollary 3.11, the group µN of N th roots of unity is contained in
Fqm . All of our calculations will be done in Fqm . The algorithm is as follows.
1. Choose a random point T ∈ E(Fqm ).
2. Compute the order M of T .
3. Let d = gcd(M, N ), and let T1 = (M/d)T . Then T1 has order d, which
divides N , so T1 ∈ E[N ].
4. Compute ζ1 = eN (P, T1 ) and ζ2 = eN (Q, T1 ). Then both ζ1 and ζ2 are
in µd ⊆ F— .
qm

5. Solve the discrete log problem ζ2 = ζ1 in F— . This will give k (mod d).
k
qm




© 2008 by Taylor & Francis Group, LLC
156 CHAPTER 5 THE DISCRETE LOGARITHM PROBLEM

6. Repeat with random points T until the least common multiple of the
various d™s obtained is N . This determines k (mod N ).


REMARK 5.2 At ¬rst, it might seem that d = 1 will occur very often.
However, the opposite is true because of the structure of E(Fqm ). Recall that

Zn1 • Zn2
E(Fqm )

for some integers n1 , n2 with n1 |n2 (possibly, n1 = 1, in which case the group
is cyclic). Then N |n2 , since n2 is the largest possible order of an element
of the group. Let B1 , B2 be points of orders n1 , n2 , respectively, such that
B1 , B2 generate E(Fqm ). Then T = a1 B1 + a2 B2 . Let e be a prime power
dividing N . Then f |n2 with f ≥ e. If a2 , then f divides M , the order of
T . Therefore, e |d = gcd(M, N ). Since the probability that a2 is 1 ’ 1/ ,
e
the probability is at least this high that the full power is in d. After a few
choices of T , this should be the case. (Note that our probability estimates
are low, since we never included the possible contribution of the a1 B1 term.)
Therefore, a few iterations of the algorithm should yield k.

Potentially, the integer m could be large, in which case the discrete log
problem in the group F— , which has order q m ’ 1, is just as hard as the
qm
original discrete log problem in the smaller group E(Fq ), which has order
approximately q, by Hasse™s theorem. However, for supersingular curves, we
can usually take m = 2, as the next result shows.
Let E be an elliptic curve over Fq , where q is a power of the prime number
p. Then
#E(Fq ) = q + 1 ’ a
for some integer a. The curve E is called supersingular if a ≡ 0 (mod p).
Corollary 4.32 says that this is equivalent to a = 0 when q = p ≥ 5.


PROPOSITION 5.3
Let E be an elliptic curve over Fq and suppose a = q + 1 ’ #E(Fq ) = 0. Let
N be a positive integer. If there exists a point P ∈ E(Fq ) of order N , then
E[N ] ⊆ E(Fq2 ).


PROOF The Frobenius endomorphism φq satis¬es φ2 ’ aφq + q = 0. Since
q
a = 0, this reduces to
φ2 = ’q.
q

Let S ∈ E[N ]. Since #E(Fq ) = q + 1, and since there exists a point of order
N , we have N |q + 1, or ’q ≡ 1 (mod N ). Therefore

φ2 (S) = ’qS = 1 · S.
q




© 2008 by Taylor & Francis Group, LLC
157
SECTION 5.3 ATTACKS WITH PAIRINGS

By Lemma 4.5, S ∈ E(Fq2 ), as claimed.

Therefore, discrete log problems over Fq for supersingular curves with a = 0
can be reduced to discrete log calculations in F— . These are much easier.
q2
When E is supersingular but a = 0, the above ideas work, but possibly
m = 3, 4, or 6 (see [80] and Exercise 5.12). This is still small enough to speed
up discrete log computations.



5.3.2 The Frey-R¨ ck Attack
u
Frey and R¨ck showed that in some situations, the Tate-Lichtenbaum pair-
u
ing „n can be used to solve discrete logarithm problems (see [41] and also
[40]). First, we need the following.

LEMMA 5.4
Let be a prime with |q ’ 1, |#E(Fq ), and 2 #E(Fq ). Let P be a
generator of E(Fq )[ ]. Then „ (P, P ) is a primitive th root of unity.

PROOF If „ (P, P ) = 1, then „ (uP, P ) = 1u = 1 for all u ∈ Z. Since
„ is nondegenerate, P ∈ E(Fq ). Write P = P1 . Then 2 P1 = P = ∞.
Since 2 #E(Fq ), there are no points of order 2 . Therefore P1 must have
order 1 or . In particular, P = P1 = ∞, which is a contradiction. Therefore
„ (P, P ) = 1, so it must be a primitive th root of unity.

Let E(Fq ) and P be as in the lemma, and suppose Q = kP . Compute
„ (P, Q) = „ (P, P )k .
Since „ (P, P ) is a primitive th root of unity, this determines k (mod ). We
have therefore reduced the discrete log problem to one in the multiplicative
group of the ¬nite ¬eld Fq . Such discrete log problems are usually easier to
solve.
Therefore, to choose a situation where the discrete log problem is hard, we
should choose a situation where there is a point of order , where is a large
q ’1. In fact, we should arrange that q m ≡ 1 (mod )
prime, and such that
for small values of m.
Suppose E(Fq ) has a point of order n, but n q ’ 1. We can extend our
¬eld to Fqm so that n|q m ’ 1. Then the Tate-Lichtenbaum pairing can be
used. However, the following proposition from [9] shows, at least in the case
n is prime, that the Weil pairing also can be used.

PROPOSITION 5.5
be a prime such that |#E(Fq ),
Let E be an elliptic curve over Fq . Let




© 2008 by Taylor & Francis Group, LLC
158 CHAPTER 5 THE DISCRETE LOGARITHM PROBLEM

E[ ] ⊆ E(Fq ), and q(q ’ 1). Then

E[ ] ⊆ E(Fqm ) if and only if q m ≡ 1 (mod ).


PROOF If E[ ] ⊆ E(Fqm ), then µ ⊆ Fqm by Corollary 3.11, hence q m ≡ 1
(mod ).
Conversely, suppose q m ≡ 1 (mod ). Let P ∈ E(Fq ) have order and let
Q ∈ E[ ] with Q ∈ E(Fq ). We claim that P and Q are independent points of
order . If not, then uP = vQ for some integers u, v ≡ 0 (mod ). Multiplying
by v ’1 (mod ), we ¬nd that Q = v ’1 uP ∈ E(Fq ), which is a contradiction.
Therefore {P, Q} is a basis for E[ ].
Let φq be the Frobenius map. The action of φq on the basis {P, Q} of
E[ ] gives us a matrix (φq ) , as in Section 3.1. Since P ∈ E(Fq ), we have
φq (P ) = P . Let φq (Q) = bP + dQ. Then

1b
(φq ) = .
0d

From Theorem 4.10, we know that

Trace((φq ) ) ≡ a = q + 1 ’ #E(Fq ) (mod ).

Since #E(Fq ) ≡ 0 (mod ) by assumption, we have

1 + d ≡ q + 1 (mod ),

so d ≡ q (mod ). An easy induction shows that
m
’1
m
1 b qq’1
1b
= .
0 qm
0q

Since q ≡ 1 (mod ), by assumption, we have

φm = 1 on E[ ] ⇐’ (φq )m ≡ I (mod ) ⇐’ q m ≡ 1 (mod ).
q


Since E[ ] ⊆ E(Fqm ) if and only if φm = 1 on E[ ], by Lemma 4.5, this proves
q
the proposition.

If we have E[n] ⊆ E(Fqm ), then we can use the MOV attack or we can
use the Tate-Lichtenbaum pairing to reduce discrete log problems in E(Fqm )
to discrete log problems in F— . The Tate-Lichtenbaum pairing is generally
qm
faster (see [44]). In both cases, we pick arbitrary points R and compute their
pairings with P and kP . With high probability (as in Section 5.3.1), we obtain
k after using only a few values of R.




© 2008 by Taylor & Francis Group, LLC
159
SECTION 5.4 ANOMALOUS CURVES




5.4 Anomalous Curves
The reason the MOV attack works is that it is possible to use the Weil
pairing. In order to avoid this, it was suggested that elliptic curves E over Fq
with
#E(Fq ) = q

be used. Such curves are called anomalous. Unfortunately, the discrete log
problem for the group E(Fq ) can be solved quickly. However, as we™ll see be-
low, anomalous curves are potentially useful when considered over extensions
of Fq , since they permit a speed-up in certain calculations in E(Fq ).
The Weil pairing is not de¬ned on E[p] (or, if we de¬ned it, it would be
trivial since E[p] is cyclic and also since there are no nontrivial pth roots of
unity in characteristic p; however, see [10] for a way to use a Weil pairing in
this situation). Therefore, it was hoped that this would be a good way to
avoid the MOV attack. However, it turns out that there is a di¬erent attack
for anomalous curves that works even faster for these curves than the MOV
attack works for supersingular curves.
In the following, we show how to compute discrete logs in the case q = p.
Procedures for doing this have been developed in [95], [102], and [115]. Similar
ideas work for subgroups of p-power order in E(Fq ) when q is a power of p
(but in Proposition 5.6 we would need to lift E to a curve de¬ned over a larger
ring than Z).
Warning: The property of being anomalous depends on the base ¬eld.
If E is anomalous over Fq , it is not necessarily anomalous over any Fqn for
n ≥ 2. See Exercises 5.5 and 5.6. This is in contrast to supersingularity,
which is independent of the base ¬eld and is really a property of the curve
over the algebraic closure (since supersingular means that there are no points
of order p with coordinates in the algebraic closure of the base ¬eld).

The ¬rst thing we need to do is lift the curve E and the points P, Q to an
elliptic curve over Z.


PROPOSITION 5.6
Let E be an elliptic curve over Fp and let P, Q ∈ E(Fp ). We assume
E is in Weierstrass form y 2 = x3 + Ax + B. Then there exist integers
˜˜ ˜
A, B, x1 , x2 , y1 , y2 and an elliptic curve E given by

y 2 = x3 + Ax + B
˜ ˜

˜ ˜ ˜
such that P = (x1 , y1 ), Q = (x2 , y2 ) ∈ E(Q) and such that

˜ ˜ ˜ ˜
A ≡ A, B ≡ B, P ≡ P, Q ≡ Q (mod p).




© 2008 by Taylor & Francis Group, LLC
160 CHAPTER 5 THE DISCRETE LOGARITHM PROBLEM

PROOF Choose integers x1 and x2 such that x1 , x2 (mod p) give the x-
coordinates of P, Q. First, assume that x1 ≡ x2 (mod p). Choose an integer
˜
y1 such that P = (x1 , y1 ) reduces to P mod p. Now choose y2 such that
2 2
y2 ≡ y 1 (mod x2 ’ x1 ) and (x2 , y2 ) ≡ Q (mod p).

This is possible by the Chinese Remainder Theorem, since gcd(p, x2 ’ x1 ) = 1
by assumption.
Consider the simultaneous equations

y1 = x3 + Ax1 + B
2 ˜ ˜
1
y2 = x3 + Ax2 + B.
2 ˜ ˜
2

˜˜
We can solve these for A, B:
2 2 3 3
˜ = y2 ’ y1 ’ x2 ’ x1 , B = y1 ’ x3 ’ Ax1 .
2
˜ ˜
A 1
x2 ’ x1 x2 ’ x1
2 2
Since y2 ’ y1 is divisible by x2 ’ x1 , and since x1 , x2 , y1 , y2 are integers, it
˜ ˜ ˜ ˜
follows that A, and therefore B, are integers. The points P and Q lie on the
˜
curve E we obtain.
If x1 ≡ x2 (mod p), then P = ±Q. In this case, take x1 = x2 . Then
choose y1 that reduces mod p to the y-coordinate of P . Choose an integer
A ≡ A (mod p) and let B = y1 ’ x3 ’ Ax1 . Then P = (x1 , y1 ) lies on E. Let
2
˜ ˜ ˜ ˜ ˜
1
˜ ˜ ˜
Q = ±P . Then Q reduces to ±P = Q mod p.
Finally, 4A3 +27B 2 ≡ 4A3 +27B 2 ≡ 0 (mod p), since E is an elliptic curve.
˜ ˜
It follows that 4A3 + 27B 2 = 0. Therefore E is an elliptic curve.
˜ ˜ ˜


REMARK 5.7 If we start with Q = kP for some integer k, it is very
˜ ˜ ˜
unlikely that this relation still holds on E. In fact, usually P and Q are
˜ ˜
independent points. However, if they are dependent, so aP = bQ for some
nonzero integers a, b, then aP = bQ, which allows us to ¬nd k (unless bP =
∞). The amazing thing about the case of anomalous curves is that even when
˜ ˜
P and Q are independent, we can extract enough information to ¬nd k.

Let a/b = 0 be a rational number, where a, b are relatively prime integers.
Write a/b = pr a1 /b1 with p a1 b1 . De¬ne the p-adic valuation to be

vp (a/b) = r.

For example,

v2 (7/40) = ’3, v5 (50/3) = 2, v7 (1/2) = 0.

De¬ne vp (0) = +∞ (so vp (0) > n for every integer n).




© 2008 by Taylor & Francis Group, LLC
161
SECTION 5.4 ANOMALOUS CURVES

Let E be an elliptic curve over Z given by y 2 = x3 + Ax + B. Let r ≥ 1 be
˜ ˜ ˜
an integer. De¬ne
˜
˜
Er = {(x, y) ∈ E(Q) | vp (x) ¤ ’2r, vp (y) ¤ ’3r} ∪ {∞}.

These are the points such that x has at least p2r in its denominator and y
has at least p3r in its denominator. These should be thought of as the points
that are close to ∞ mod powers of p (that is, p-adically close to ∞).


THEOREM 5.8
Let E be given by y 2 = x3 + Ax + B, with A, B ∈ Z. Let p be prime and let
˜ ˜ ˜ ˜˜
r be a positive integer. Then
˜ ˜
1. Er is a subgroup of E(Q).
˜
2. If (x, y) ∈ E(Q), then vp (x) < 0 if and only if vp (y) < 0. In this case,
there exists an integer r ≥ 1 such that vp (x) = ’2r, vp (y) = ’3r.
3. The map
˜˜
»r : Er /E5r ’ Zp4r
(x, y) ’ p’r x/y (mod p4r )
∞’0

is an injective homomorphism (where Zp4r is a group under addition).
˜ ˜
4. If (x, y) ∈ Er but (x, y) ∈ Er+1 , then »r (x, y) ≡ 0 (mod p).

This will be proved in Section 8.1. The map »r should be regarded as a
˜˜
logarithm for the group Er /Er+1 since it changes the law of composition in
the group to addition in Zp4r , just as the classical logarithm changes the com-
position law in the multiplicative group of positive real numbers to addition
in R.
We need one more fact, which is contained in Corollary 2.33: the reduction
mod p map
˜ ˜
redp : E(Q) ’’ E (mod p)
˜
(x, y) ’ (x, y) when (x, y) ∈ E1
(mod p)
˜
E1 ’ {∞}
˜
is a homomorphism. The kernel of redp is E1 .
We are now ready for a theoretical version of the algorithm. We start with
an elliptic curve E over Fp in Weierstrass form, and we have points P and
Q on E. We want to ¬nd an integer k such that Q = kP (assume k = 0).
The crucial assumption is that E is anomalous, so #E(Fp ) = p. Perform the
following steps.




© 2008 by Taylor & Francis Group, LLC
162 CHAPTER 5 THE DISCRETE LOGARITHM PROBLEM

˜˜˜
1. Lift E, P, Q to Z to obtain E, P , Q, as in Proposition 5.6.
˜ ˜˜ ˜ ˜˜ ˜ ˜
2. Let P1 = pP , Q1 = pQ. Note that P1 , Q1 ∈ E1 since redp (pP ) =
˜
p · redp (P ) = ∞ (this is where we use the fact that E is anomalous).
˜ ˜ ˜˜˜
3. If P1 ∈ E2 , choose new E, P , Q and try again. Otherwise, let =
1
˜ ˜
»1 (P1 ) and 2 = »1 (Q1 ). We have k ≡ 2 / 1 (mod p).
˜ ˜ ˜
Why does this work? Let K = k P ’ Q. We have
˜ ˜ ˜
∞ = kP ’ Q = redp (k P ’ Q) = redp (K).
˜ ˜ ˜
Therefore K ∈ E1 , so »1 (K) is de¬ned and
˜ ˜
»1 (pK) = p»1 (K) ≡ 0 (mod p).

Therefore,
˜ ˜ ˜ ˜ ˜
’ = »1 (k P1 ’ Q1 ) = »1 (kpP ’ pQ) = »1 (pK) ≡ 0
k (mod p).
1 2

This means that k ≡ 2 / 1 (mod p), as claimed.
Note that the assumption that E is anomalous is crucial. If E(Fp ) has
˜˜ ˜
order N , we need to multiply by N to put P , Q into E1 , where »1 is de¬ned.
˜ ˜˜
The di¬erence K = k P ’ Q gets multiplied by N , also. When N is a multiple
˜ ˜
of p, we have »1 (N K) ≡ 0 (mod p), so the contribution from K disappears
from our calculations.
If we try to implement the above algorithm, we soon encounter di¬culties.
˜
If p is a large prime, the point P1 has coordinates whose numerators and
denominators are too large to work with. For example, the numerator and
denominator of the x-coordinate usually have approximately p2 digits (see
Section 8.3). However, we are only looking for x/y (mod p). As we shall see,
it su¬ces to work with numbers mod p2 . (It is also possible to use the “dual
numbers” Fp [ ], where 2 = 0; see [10].)
Let™s try calculating on E (mod p2 ). When we compute (x, y) = P1 = pP ,
˜ ˜ ˜
we run into problems. Since P1 ∈ E2 , we have p2 in the denominator of x, so
˜ ˜
P1 is already at ∞ mod p2 . Therefore, we cannot obtain information directly
˜
from calculating »1 (P1 ). Instead, we calculate (p ’ 1)P (mod p2 ), then add
˜ ˜
˜
it to P , keeping track of p in denominators.
The procedure is the following.
˜
˜˜
1. Lift E, P, Q to Z to obtain E, P = (x1 , y1 ), Q = (x2 , y2 ), as in Proposi-
tion 5.6.
2. Calculate
P2 = (p ’ 1)P ≡ (x , y ) (mod p2 ).
˜ ˜
˜
The rational numbers in the calculation of P2 should not have p in their
denominators, so the denominators can be inverted mod p2 to obtain
integers x , y .




© 2008 by Taylor & Francis Group, LLC
163
SECTION 5.4 ANOMALOUS CURVES

3. Calculate Q2 = (p ’ 1)Q ≡ (x , y ) (mod p2 ).
˜ ˜

4. Compute
y ’ y1 y ’ y2
m1 = p , m2 = p .
x ’ x1 x ’ x2
˜
5. If vp (m2 ) < 0 or vp (m1 ) < 0, then try another E. Otherwise, Q = kP ,
where k ≡ m1 /m2 (mod p).


Example 5.5
Let E be the elliptic curve given by y 2 = x3 +108x+4 over F853 . Let P = (0, 2)
and Q = (563, 755). It can be shown that 853P = ∞. Since 853 is prime, the
order of P is 853, so 853|#E(F853 ). Hasse™s theorem implies that #E(F853 ) =
853, as in Section 4.3.3. Therefore, E is anomalous. Proposition 5.6 yields

E : y 2 = x3 + 7522715x + 4,
˜ ˜ ˜
P = (0, 2), Q = (563, 66436).

We have

P2 = 852P ≡ (159511, 58855) (mod 8532 )
˜ ˜
Q2 = 852Q ≡ (256463, 645819) (mod 8532 ).
˜ ˜

˜
Note that even with a prime as small as 853, writing P2 without reducing
mod 8533 would require more than 100 thousand digits. We now calculate
58855 ’ 2 645819 ’ 66436
58853 58853
m1 = 853 = and m2 = 853 = .
159511 ’ 0 256463 ’ 563
187 187

Therefore, k ≡ m1 /m2 ≡ 234 (mod 853).

Let™s prove this algorithm works (the proof consists mostly of keeping track
of powers of p, and can be skipped without much loss). The following notation
is useful. We write O(pk ) to represent a rational number of the form pk z with
vp (z) ≥ 0. Therefore, if a, b ∈ Z and k > 0, then a = b + O(pk ) simply
means that a ≡ b (mod pk ). But we are allowing rational numbers and we
are allowing negative k. For example,
23
1
+ O(7’1 )
=
49 98
since
23 1 13
= + .
98 49 7 2
The following rule is useful:
a
a
= + O(pk ) when vp (b) = 0, vp (a) ≥ 0, and k > 0.
b + O(pk ) b




© 2008 by Taylor & Francis Group, LLC
164 CHAPTER 5 THE DISCRETE LOGARITHM PROBLEM

To prove it, simply rewrite the di¬erence b+pk z ’ a . (Technical point: This
a
b
actually should say that a/(b + O(p )) can be changed to (a/b) + O(pk ). The
k

problem with “=” is that the right side sometimes cannot be changed back
to the left side; for example, let the right side be 0 with a = ’pk .)
Write P2 = (p ’ 1)P = (u, v), with u, v ∈ Q (this is not yet mod p2 ). Then
˜ ˜

u = x + O(p2 ), v = y + O(p2 ).

Let
˜ ˜ ˜ ˜
(x, y) = P1 = pP = P + P2 = (x1 , y1 ) + (u, v).
Then
2
2
y ’ y1 + O(p2 )
v ’ y1
’ u ’ x1 = ’ u ’ x1 .
x=
x ’ x1 + O(p2 )
u ’ x1

˜ ˜ ˜ ˜
We have P1 ∈ E1 and usually we have P1 ∈ E2 . This means that x ’ x1
2
is a multiple of p, but not of p (note: y ≡ y1 (mod p) since otherwise
(p ’ 1)P = P , which is not the case). We™ll assume this is the case. Then

y ’ y1 + O(p2 ) y ’ y1 + O(p2 )
1
= x ’x1
x ’ x1 + O(p2 ) p + O(p)
p

y ’ y1
1
= + O(p)
x ’x1
p p
1
m1 + O(p0 ).
=
p

Note that vp (m1 ) = 0. Since vp (u) ≥ 0 and vp (x1 ) ≥ 0, we obtain
2
m2
1 1
m1 + O(p0 ) + O(p’1 ).
’ u ’ x1 =
x= 2
p p

˜
Similarly, the y-coordinate of P1 satis¬es

m31
y = ’ 3 + O(p’2 ).
p

Therefore,

x 1 1
= »1 (P1 ) = »1 (x, y) = p’1 = ’
˜ + O(p) ≡ ’ (mod p).
1
y m1 m1

Similarly,
1
˜
= »1 (Q1 ) ≡ ’ (mod p).
2
m2




© 2008 by Taylor & Francis Group, LLC
165
SECTION 5.5 OTHER ATTACKS

˜ ˜ ˜ ˜
If vp (m2 ) < 0, then Q1 ∈ E2 by Theorem 5.8, hence either P1 ∈ E2 or k = 0.
We are assuming these cases do not happen, and therefore the congruence
just obtained makes sense. Therefore,
m1
2

k≡ (mod p),
m2
1

as claimed. This shows that the algorithm works.
Anomalous curves are attractive from a computational viewpoint since cal-
culating an integer multiple of a point in E(Fq ) can be done e¬ciently. In
designing a cryptosystem, one therefore starts with an anomalous curve E
over a small ¬nite ¬eld Fq and works in E(Fqk ) for a large k. Usually it is
best to work with the subgroup generated by a point whose order is a large
prime number. In particular, will be much larger than p, hence not equal
to p. Therefore, the above attack on anomalous curves does not apply to the
present situation.
Let E be an elliptic curve over Fq such that #E(Fq ) = q. Then the trace
of the Frobenius φq is a = 1, so

φ2 ’ φq + q = 0.
q

This means that q = φq ’ φ2 . Therefore
q

2 2
q(x, y) = (xq , y q ) + (xq , ’y q ) for all (x, y) ∈ E(Fq ).

The calculation of xq , for example, can be done quickly in a ¬nite ¬eld. There-
fore, the expense of multiplying by q is little more than the expense of one
addition of points. The standard method of computing q(x, y) (see Section 2.2)
involves more point additions (except when q = 2; but see Exercise 5.8). To
calculate k(x, y) for some integer k, expand k = k0 + k1 q + k2 q 2 + · · · in base
q. Compute ki P for each i, then compute q i ki P . Finally, add these together
to obtain kP .




5.5 Other Attacks
For arbitrary elliptic curves, Baby Step/Giant Step and the Pollard ρ and
» methods seem to be the best algorithms. There are a few cases where index
calculus techniques can be used in the jacobians of higher genus curves to
solve discrete logarithm problems on certain elliptic curves, but it is not clear
how generally their methods apply. See [45], [46], [79]. See also [113] for a
discussion of some other index calculus ideas and elliptic curves.
An interesting approach due to Silverman [112] is called the xedni calcu-
lus. Suppose we want to ¬nd k such that Q = kP on a curve E over Fp .




© 2008 by Taylor & Francis Group, LLC
166 CHAPTER 5 THE DISCRETE LOGARITHM PROBLEM

˜
Proposition 5.6 shows that we can lift E, P , and Q to an elliptic curve E
˜ ˜ ˜ ˜
over Z with points P and Q. If we can ¬nd k with Q = k P , then Q = k P .
˜ ˜
However, it is usually the case that P and Q are independent, so no k ex-
ists. Silverman™s idea was to start with several (up to 9) points of the form
ai P + bi Q and lift them to a curve over Q. This is possible: Choose a lift
to Z for each of the points. Write down an arbitrary cubic curve containing
lifts of the points. The fact that a point lies on the curve gives a linear equa-
tion in the coe¬cients of the cubic equation. Use linear algebra to solve for
these coe¬cients. This curve can then be converted to Weierstrass form (see
Section 2.5.2). Since most curves over Q tend to have at most 2 independent
points, the hope was that there would be relations among the lifted points.
These could then be reduced mod p to obtain relations between P and Q, thus
solving the discrete log problem. Unfortunately, the curves obtained tend to
have many independent points and no relations. Certain modi¬cations that
should induce the curve to have fewer independent points do not seem to
work. For an analysis of the algorithm and why it probably is not successful,
see [55].




Exercises
5.1 Suppose G is a subgroup of order N of the points on an elliptic curve over
a ¬eld. Show that the following algorithm ¬nds k such that kP = Q:

. 1
( 2)



>>