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:

√