Theorem 8.2.31 (Lang-Trotter Procedure). Let F = _p, p > 5 and p prime, and let (_p): y² = x³ + ax + bbean elliptic curve over _p. Then

where is the Legendre symbol.

Proof. If f (x) = x³ + ax + b we have p values for x in _p. If f (x) = 0 then there is exactly one point (x, 0) on (_p). Here = 0.

Now let f(x) = 0. Then f(x) ϵ {1,-1}. Iff(x) = 1, thenf(x) is a quadratic residue modulo p so for x there are two points (x, y) and (x, −y) on (_p). Hence the number of points is + 1 = 2 since = 1 if f (x) is a quadratic residue modulo p.

Now let f (x)V = −1.Then f (x) is a quadratic non-residue modulo p so for x there is no point on (_p). Hence the number of points is + 1 = 0 since = −1 if f (x) is a quadratic non-residue modulo p. Now the result follows since we must add a 1 for the element O.

8.2.5 Calculating Points in Elliptic Curve Groups

In this section we describe efficient probabilistic algorithms to calculate points on an elliptic curve and to calculate their orders. The first algorithm is equivalent to the algorithm given in Chapter 6 to calculate square roots.

Theorem 8.2.32. Let F = _p with p > 5 a prime and (_p) : y² = x³ + ax + b be an elliptic curve over _p. Then a probabilistic algorithm for calculating a point (x, y) ϵ (_p) is given as follows.

(1)  Choose an arbitrary x ϵ _p and calculate f (x) = x³ + ax + b.

(2)  Iff (x) = 0 then (x, 0) ϵ (_p).

(3)  Repeat Step (1) as long as f (x) = 0. Such an x must exists since p > 5 and f (x) has at most 3 zeros in _p.

(4)  Calculate f(x) ϵ {1,-1} c _p. Check ifthe result is 1, that is, iff (x) is a square in

(5)  If the result is −1 then repeat steps (1) through (4) as long as we get the result 1 p-1 2

(6)  If f(x) = 0 and f(x) =1 then calculatey with y² = f(x) asfollows: p+1

(a)  If p = 3 (mod 4) then calculate y = f (x). Return the pair (x, y) and stop.

(b)  If p = 1 (mod 4) then write p − 1 = 2^s t with s > 2 and t odd.

Choose a random element u e_p and calculate u ² e{1, −1}. Repeat this as long as p-1 _T

Calculate v = u andy₁ = f(x) .Fori = 2,3,…,s calculate f(x) and define recursively c₀, c₁,…, c_s_₂ ϵ {0,1} with . “)s—if − −)s—i+1 . . −)s—1

Define c = c₀ + 2c₁ + ··· + 2^s-2c_s_₂ and y = y₁v^c. Then give the pair (x, y) and stop.

Proof. Since f (x) = x³ + ax + b has at most three zeros in _p and p > 5 it follows that there exists an x ϵ _p with f (x) = 0. The rest of the proof is done analogously to the proof of the algorithm for finding square roots modulo p given in Chapter 6. □

If we only want an elliptic curve (_p) with a pair P = (x₀, y₀) ϵ (_p) we may proceed as follows:

(1)  Choose x₀,y₀, a e_f randomly. Then define b = y − x − ax₀.

(2)  Calculate Δ = −4a³ − 27b².

(3)  Repeat (1) and (2) as long as Δ = 0.

Then (_p): y² = x³ + ax + b is an elliptic curve with (x₀, y₀) ϵ (_p).

We now consider the question of determining the order of a point P on an elliptic curve (_p).

Theorem 8.2.33 (Shank’s Baby Step-Giant-Step (BSGS) Algorithm for the order of elements in ϵ(_p)). LetF = _p,p > 5 and (_p) : y² = x³ + ax + b an elliptic curve over _p. LetP ϵ (_p) and B eN with B > p + 2 + 2 Vp. Then the following procedure calculates the order |P| = ord )(P) ofP in E(X_p).

(1)  Let p = min{k eN| k² > B}. (Then we have ² > B.) Calculate the points P, 2P,… ,pP and define P₁ = pP.

(2)  Calculate aP₁ forΔ = 1,…,p and check after each calculation if aP₁ ϵ {P, 2P,…, PP}. Ifthis is the casego to step (3).

(3)  IfaP₁ = yPwitha ϵ {1,…,p} and y ϵ {1,…,p} then factor ap −y and find the smallest positive divisor of S with SP = 0. The value of S provides the order ofP.

Proof. Let n = |P|. Write n = ap + y with a ϵ {0,1,…,p − 1} and ye {0,1,…,p − 1}. Since

n = |P| < p + 1 + 2Vp < B < p²

it follows that

with a = a + 1 and y = p − y since P₁ = pP. Here a, y ϵ {1,…,p}. Hence in (2) we must have a match aP₁ = yP. □

We mention that there is a strong optimization of the BSGS algorithm given in the book by H. Cohn [Coh].

We now describe how to determine the order of the whole group (_p) if we have the order of an element P. Recall from Hasses’ Theorem that if p > 5 then

Theorem 8.2.34 (Shank's Method). Let F = _p,p > 5 and (_p) an elliptic curve over _p. Suppose there is a point P ϵ (_p) with order |P| = ord)(P) > 4Vp. Then there is exactly one multiple nP with n eN ofP in the interval [p +1 − 2 Vp,p + 1 + 2 Vp]. Then |(_p)| = n|P|.

If there exists such a point P with |P| > 4 Vp then following is a probabilistic algorithm to determine |(_p)|.

(1)  Choose a random P ϵ (_p).

(2)  Calculate the order |P| ofP with the help of the BSGS algorithm

(3)  Repeat (1) and (2) as long as |P| > 4 Vp.

(4)  Calculate the unique n eN with

Proof. We must only recall that 4Vp is the length of the involved interval. We get |(_p)| from Hasse’s Theorem and Lagrange’s Theorem. □

There is one problem in the Shank’s method; when there does not exist such a P ϵ (_p) with |P| > 4 Vp in (_p) for each elliptic curve (_p).

The idea is to use Shank’s method universally by constructing an elliptic curve (_p) which is closely related to (_p) and which contains a point P with |P| > 4 Vp in (_p).

To do this we need some deep results from the theory of elliptic curves. Let F = _p with p > 5 and (_p) : y² = x³ + ax + b an elliptic curve. Let d e be a quadratic non-residue modulo p so that d ² = − 1in _p. Now construct

(_p): y² = x³ + d²ax + d³b.

The curve (_p) is an elliptic curve because Δ = d⁶Δ = 0 in _p. The curve (_p) is called the twist of (_p).

Theorem 8.2.35. LetF = _p, p > 5,(_p) an elliptic curve over _pand(_p) beatwist of(_p). Then

(1)   |E(Zp)| + |E(Zp)| = 2p +2.

(2)  Ifp > 457 then (_p) or(_p) contains a pointP orP respectively with order |P| > 4 Vp in (_p) or |P| > 4 Vp| in (_p) respectively.

(3)  The number of suitable points is about _logf_{og p} where C is a constant.

Proofs are available in [Coh] and [Sc1].

Theorem 8.2.36(The Shank’s-Mestre Algorithm). Let F = _pwithp > 457and(_p): y² = x³ + ax + b an elliptic curve over _p. Then the following probabilistic algorithm

determines the order |(_p)|.

(1)  Find a d with d = −1 and define the twist

(_p): y² = x³ + d²ax + d³b.

Letf(x) = x³ + ax + b and f(x) = x³ + d²ax + d³b.

(2)  Choose randomly x ϵ {0,1,…,p − 1} and calculate f(x) in _p. Iff(x) = 0 then choose another x and repeat this until f (x) = 0. Iff(x) = 1 then calculate y e_p with y² = f (x) and setP = (x, y). Otherwise go to step (4).

(3)  Determine the order |P| ofP in (_p) with the BSGS algorithm. If |P| > 4 Vp then continue to Step (6). Otherwise go to Step (2).

(4)  Define x = dx. Iff (x)^v = −1 then

Calculate y ϵ _p with (y)² = f (x) and setP = (x, y) ϵ (_p).

(5)  Determine the order |P| ofP in (_p) with the BSGS algorithm. If |P|> 4 Vp then go to Step (6). Otherwise go to Step (2).

(6)  Determinen ϵ NsuchthatnP ornP respectively is in the interval [p + 1-2Vp, p + 1 + 2 Vp]. Then return nP or 2p + 2 − n|P| respectively and stop.

With practical improvements to the Shank’s-Mestre algorithm it is possible to calculate |(_p)| for prime numbers with 500 digits.

Another method to determine |(_p)| is to calculate the trace t of the Frobenius map, the Frobenius trace for short. Recall that t = p + 1 − |(_p)|. We briefly describe this method.

Let F = _p with p > 5 and let _p be the algebraic closure of _p. The Frobenius map ϕ : _{p p} given by x x^p is an injective field homomorphism by Fermat’s theorem and _p is the set of fixed points of ϕ, that is, the set {x | ϕ (x) = x} (see [CFR1] or [KKi]). Let (_p): y² = x³ + ax + b be an elliptic curve over _p and

the elliptic curve group over _p. Then (_p) c (_p) is a subgroup of (_p).

If n eN then we define

For n ϵ Ntheset E[n] is a subgroup of (_p).If k ϵ Zand k = 0then E[|k|]isthekernel of the group endomorphism

The Frobenious map ϕ induces a group endomorphism of (_p), denoted also by ϕ, and is called the Frobenius map on (_p) via ϕ : (_p) (_p) with

(x, y) (ϕ (x), ϕ (y)) = (x^p, /) if (x, y) ϵ E(Zp) and O O.

By the definition of the group operation in (_p) we get that ϕ is a group endomorphism. Also

E(Zp) = {P ϵ EZp) | ϕ (P) = P}

and hence ϕ ((_p)) = (_p) (recall that ϕ (a) = a, ϕ (b) = b).

Theorem 8.2.37. LetF = _p,p > 5 and (_p) : y² = x³ + ax + bbean elliptic curve over _p.Let$ be the Frobenius map on (_p).Lett = p + 1 −|(_p)|. Then the following hold:

(1)  E([n]) s (_%, +) x (_n , +) for somϵ n₁, n₂ eN if n eN andpdoes not divide n

E([p^r]) s {O} ifp, thatis,(_p) is super singular and

E([p^r]) s (_pr, +) ifp does not divide t.

(2)  The map Z End((_p)) given byk [k] is an injective ring homomorphism. We call this the Tate pairing.

(3)   $² − [t]$ + [p] = [0] inEnd(E(Zp).

Proof. Here End((_p)) is the ring of endomorphisms of ((_p)) via k + l [k + l] where [k + l](P) = [k](P) + [l](P)forP ϵ ((_p))andkl k°lwhere [k°l](P) = [k]([l](P)) for P ϵ ((_p)). It is easy to check that End((_p)) is a ring with two binary operations.

A proof of (1) and (3) can be found in [Sil]. Here we prove (2). Certainly the map is a ring homomorphism. We have [k] = 0 if and only if kP = O for all P ϵ (_p)). By (1) there exist points in (_p)) with arbitrarily large orders in ((_p)). Hence k = 0 and the kernel of the ring homomorphism is trivial. □

From the above theorem we have the reason for calling the number t = p + 1 − |((_p)| the trace of the Frobenius map.

Based on the above theorem, Schoof (see [Sc1] and [Sc2]) developed a probabilistic algorithm to determine the trace t of the Frobenius map. If we know t then we have the order |(_p| of (_p) via |(_p)| = p +1 − t. For more details see also [KKi]. SchooF′s algorithm works especially well ifwe find a point P ϵ (_p )with|P| = p. The algorithm deals with [t] and uses that k [k] is injective.

The theorem is also the reason that super singular elliptic curves (_p) are not suitable for cryptographic purposes.

8.3 Elliptic Curve Cryptography

We now apply the ElGamal method to the group of an elliptic curve to obtain the elliptic curve cryptosystem. We restrict ourselves to odd prime numbers p > 5 and the corresponding finite fields _p.

Consider the elliptic curve (in Weierstrass form) over _p given by

(_p): y² = x³ + ax + b, a, b e_p

with Δ = −4a³ − 27b² = 0 in _p.

Now let

E(Zp) = E(Zp) u {O}

be the elliptic curve group of (_p). The basic idea is to use the ElGamal method, and its dependence on the corresponding discrete log problem, in (_p), this is, given P ϵ (_p) and nP ϵ (_p) find n.

We now define the elliptic curve encryption scheme which we will abbreviate by ECES. This is also known as the Elliptic Curve ElGamal Cryptosystem or the Meneses-Vanstone Cryptosystem.

ECES Preparation

(1)  Choose a large odd prime p with p > 5 and a, b e_p such that

ϵ(_p) : y² = x³ + ax + b

is an elliptic curve.

(2)  Choose an injective efficiently invertible (on the image) map p : M (_p) from the set M of plain text units to (_p). We describe such a choice below.

(3)  Choose a point P ϵ ϵ(_p).

(4)  Choose a secret integer d eZ and calculate dP ϵ (_p).

Encryption and Decryption in ECES

(1)  The public key is (P, dP) ϵ (_p) x (_p) and the elliptic curve (_p) itself. The secret key is d.

(2)  Encryption: Let m ϵ M be a plain text message unit. Calculate Q = p (m). Choose a random integer k eZ and define

c = (kP, Q + k(dP)) ϵ ((_p))² = C.

This is the encrypted message unit

(3)  Decryption: Let c = (c₁, c₂) ϵ C be a ciphertext unit. Calculate Q = c₂ − dc₁ and m = p^-1(Q) the preimage of Q.

Recall that Q ϵ (_p) if Q = p(m) and (c₁, c₂) = (kP, Q + k(dP)).

Theorem 8.3.1. ECECprovides a valid cryptosystem.

Proof. Let (c₁, c₂) = (kP, Q + k(dP)). Then c₂ − dc₁ = Q = p(m). □

Notice that if the discrete log problem for (_p) is solvable, that is if we can calculate d from (P, dP) then the ECES is broken.

We now show how to construct an injective, efficiently invertible map M (_p).

Let (_p) : y² = x³ + ax + b be an elliptic curve over _p with p > 5. By Hasse’s theorem (see last section) we have

|(_p)| ϵ [p +1 − 2 Vp,p + 1 + 2 Vp] n N.

There are efficient probabilistic algorithms to generate points of (_p) (see Theorem 8.2.10). We need many points in (_p).

(1)  Choose k eN such that the permitted probability of error is < .

(2)  Let M = {0,1,…, M}.We should have p > (M + 2)k.

(3)  Define an injective map:

V : Mx{1,…,k}_p by (m,j) mk + j.

Recall that 0 < mk + j < p because p > (M + 2)k.

(4)  Let x = W(m, 1). Calculate f (x) = x³ + ax + b and check if there exists y e_p with y² = f(x). If this is the case then choose y so that y ϵ {0,1,…,^p-1} and define p (m) = (x, y).

We note that f (x) is a quadratic residue modulo p for about half of the f (x) with f (x) = 0 and x e_p gives 0,1 or 2 points on the elliptic curve.

(5)  If x = W(m, 1) and there is no y ϵ _p with y² = f (x)thentryx = W(m, 2), x = W(m, 3) and so on.

With probability > 1 − we find an element x ϵ {F(m, 1),…, V(m, k)} with f (x) = y² for some y ϵ _p.

If j with 1 < j < k is the smallest integer j such that x = W(m, j) and f (x) = y² for somey ϵ _p − such aj exists with probability > 1 − 2 − then choosey ϵ {0,…, ^p-r} and define p (m) = (x, y).

(6)   If (x, y) ϵ Im(p) c (_p) then we may recover m efficiently. If x = mk + j then m = m = i^- because k eN and p > (M + 2)k.

8.4 Cryptoanalysis of Elliptic Curve Cryptosystems

We now examine the cryptoanalysis of elliptic curve based cryptosystems. First we look at some general ideas.

Recall that (_p) andP are public. An attacker has to calculate |(_p)| or |P|.

(1)  ECES is not secure if |(_p)| has only small prime factors (see the section on the reduction of the DLP to groups of prime power order in Chapter 6). Hence |(_p)| should have at least one large prime factor.

(2)  Analogously |P| should have at least one large prime factor.

(3)  ECES is not secure if |P| = p. Here we can determine |(_p)| effectively via the trace t of the Frobenius map using what is called SchooF′s algorithm (see [Sc1] and [Sc2]).

Elliptic curves that have passed all known attacks so far can be found at the website http://www.ecc-brainpool.org/ecc-standards.htm.

8.5 The MOV-Algorithm

In this section we look at the MOV algorithm for attacking elliptic curve cryptosystems. This algorithm, named after Menezes, Okamoto and Vanstone, who developed it (see [MOV]), is a probabilistic algorithm to determine the discrete logarithm in the group (F) of an elliptic curve over a finite field. The MOV algorithm reduces the elliptic curve discrete log problem (ECDSP) to the discrete log problem (DLP) in the multiplicative group of an extension field P_qt of the base field and then solves the DLP using a known best algorithm. It was originally believed that to solve the ECDLP required exponential time. However, using the MOV algorithm for elliptic curves it can be solved in probabilistically subexponential time. The theoretical background and a more detailed description of the MOV algorithm can be found in [Sil].

To start, let F be a field of characteristic p > 5. We note that the concepts can also be described with modifications for fields of characteristic 2 or 3 but here we only considerp > 5. Let

ϵ(F) : y² = x³ + ax + b

be an elliptic curve over F and (F) = (F) u O be the corresponding elliptic curve group.

For each P, Q ϵ (F) we take a formal symbol [P] with [P] = [Q] ifP = Q.A divisor D of (F) is defined by the formal sum

with all n_P eZ and at most finitely many n_P = 0. Together with the sum £ nP [P] + £ mP[P] = £ (nP + mP)[P]

the set of divisors of E(P) is a free abelian group.

Let F be the algebraic closure of F and let R((F)) be the field of rational functions of (F). Recall that O is the point at infinity.

Let f ϵ R((F))* so that f ϵ R((F)) and f = O. The divisor of f is defined by

with n_P eZ, n_P > 0ifP ϵ (F) is a zero off with multiplicity n_P and n_P < 0ifP ϵ (F) is a pole of f with multiplicity |n_P|. A divisor D of (F) is called a principal divisor if D = div(f) for some f ϵ R((F))*.

The degree of a divisor D = £_Pϵ;g(_F) n_P[P] is defined by

and the sum of the divisor D is defined by

Theorem 8.5.1. Letf ϵ R((F))*.

(1)  We have div(f) = O if and only iff ϵ F and f = O.

(2)  We havϵ deg(div(f)) = 0.

(3)  A divisor D = X_PeE(_F) n_P[P] is a principal divisor if and only if we have deg(D) = 0 and sum(D) = O.

We now describe the Weil-pairing. Let m > 1 be a natural number with p not a divisor of m. We call P ϵ (F) an m-torsion point if mP = O. The point at infinity O is an m-torsion point for all m. The m-torsion subgroup (F)[m] of (F) is the set of all m-torsion points of (F), that is,

(F)[m] = {P ϵ (F); mP = O}.

This is clearly a subgroup of (F) since (F) is abelian.

Definition 8.5.2. Given P, Q ϵ (F)[m], we let f_P,fQ ϵ R((F))* such that div(f_P) = m[P] − m[O] and div(/Q) = m[Q] − m[O]. The Weil-pairing e_m(P, Q) of P and Q is defined by

for S ϵ (F)[m] with S $ {O, P, −Q, P − Q}.

Notice that if P, Q ϵ (F)[m] then mP = mQ = O. Then by Theorem 8.4.1.1 there exist rational functions f_P, fQ ϵ R((F)* with div(f_P) = m[P] − m[O] and div(fQ) = m[Q] − m[O] which are related to the divisors m[P] − m[O] and m[Q] − m[O] respectively. P is a zero of f_P with multiplicity m and O is a pole off_P with multiplicity m. The analogous statement holds for fQ. This shows that the Weil-pairing e_m(P, Q) is defined and non-zero for S $ {O, P,-Q, P − Q}.

Further notice that the Weil-pairing is well-defined, that is, independent of the choice of the rational functions f_P, fQ and independent of the choice of the point S $ {O, P,-Q, P − Q}.

Theorem 8.5.3 (Properties of the Weil-Pairing).

(1)  e_m(P, Q)^m = 1 for all P, Q ϵ (F)[m]

(2)  em(P1 + P2, Q) = em(P1, Q)em(P2, Q) and _

em(P, Q1 + Q2) = em(P, Q1)em(P, Q2) forallP,P1,P2, Q1, Q2 ϵ (F)[m]

(3)  e_m(P,P) = 1 forallP ϵ (F)[m]

(4)  Ife_m(P, Q) = 1 for all Q ϵ (F)[m] thenP = O.

The Weil-pairing e_m is a map

em : (F)[m] x (F)[m] $m c F*

where 4>_m is the group of the m-th roots of unity in F*. There is an efficient algorithm to calculate the Weil-pairing (see [Sil]).

We now describe the embedding degree K . This is important for the running time of the probabilistic algorithm to determine the discrete logarithm in (F).

Note that if k eN with k > 1 then _p embeds into the finite field P_q, q = p^K. With this embedding, any elliptic curve (_p) can be considered as an elliptic curve E(F_q), that is if P = (a, b) is a point on (_p) then P can be considered as a point on E(P_q).

Theorem 8.5.4. Let(_p) be an elliptic curve and let I >Vp + 1 be a prime number (p > 5 prime). If(_p) contains an element P of order I then (_p)[l] s (_f, +) = _e.

Proof. Since (_p) contains an element P of order I the subgroup (_p)[l] contains at least I elements. We now show that (_p)[l]) contains at least I elements and hence (_p)[l]) is isomorphic to _f.

Assume that there are more than I elements in (_p)[l]. The element P generates acyclicsubgroup (P) of order I in (_p)[l]. Hence there exists an element Q ϵ (_p)[l] which cannot be written as aP with a ϵ {0,1,…,l − 1}. The element Q also generates a cyclic subgroup (Q) of order I in (_p)[l] and we have (P) n (Q) = {O}. Recall that I is a prime number. Each element of the form aP + bQ with b e{0,1,…,l − 1} is also in (_p)[l]. Hence (_p)[l] has at least I² elements. We have I² > p + 1 + 2 Vp. On the other hand, the number of elements of (_p) is by Hasse’s Theorem in the interval [p +1 − 2 Vp, p +1 + 2 Vp] which gives a contradiction and therefore there is no such Q. It follows that (_p)[l] = (P) s _f. □

Using this we get the following theorem.

Theorem 8.5.5. There isaK eN, K > 1 with

E(WpjK )[m] sZm x_m

for all j > 1.

Definition 8.5.6. The embedding degree for m is the smallest natural number K > 1 such that for all j > 1we have

E(W_PJK )[m] =Zm xZm.

Theorem 8.5.7. Let i = p be aprime number. lf(_p) contains an element of order I then the embedding degree K of(_p) for i is given by one of the following cases:

(1)  K = 1 and this can only happen if i< VP + 1-

(2)  p = 1 (mod i) and K = i.

(3)  p is not congruent to 1 (mod i) and K is the smallest natural number r with p^r = 1 (modi).

We now describe the MOV-algorithm for the discrete logarithm in (_p), where p > 5 is a prime number. Let P ϵ (_p) of order 1>Vp +1 where i is a prime number with i = p.Let K be the embedding degree of (_p) for i.

Let Q = kP where k is the discrete logarithm of Q for the base P in (_p), especially 1 < k < i. We consider the following steps to calculate k:

(1)  Calculate N = |E(Ey )|

(2)   Choose an element T ϵ E(Ey) with T $ (_p). If T’ = (N)T = O then repeat this step with a different T. If T’ = O then continue on to setp (3).

(3)  Calculate the values g = e_e(P, T’) and b = e_e(Q, T’) of the Weil-pairing.

(4)  Solve the discrete log problem b = g^k in Ey.

This is a probabilistic algorithm to solve the discrete log problem in (_p) in subexponential time. This probabilistic algorithm is correct as we can see from the following remarks:

(1)  In Step (1) we have to calculate N = |E(Ey)|. We discussed several methods to calculate |(_p)| and these methods can be extended to calculate |E(Ey)|. This can be done polynomially in log(p^k). For details we refer to [HPS].

(2)   In Step (2) we need an element T ϵ E(Ey) with T ϵ (_p) and T’ = (N)T = O. It is easy to see that there are T ϵ E(Ey) with T ϵ (_p) by Theorems 8.4.4 and 8.4.5. We have K > 2 since 1>Vp +1. Now

by Hasse’s Theorem. These give that N > n sincep > 5 and K > 2.

To construct such a T with the additional property that T’ = (N )T = O is computationally much more complicated. However, it exists and can be constructed polynomially in log(p^K) (see [SZSI]).

(3)   We may calculate g = e_e(P, T’) and b = e_e(Q, T’). T’ is not of the form rP. If this would be the case then we would already have T = sP from T’ = (N )T which contradicts T’ = O because (N )P = O. Hence we may consider P and T’ as a basis of the two-dimensional vector space X_e x2₍ s E(W_PK )[i].

Assume that g = 1. Then P = O by Theorem 8.4.2 which contradicts P = O. Recall that e_e(P, P) = 1 and e_e(P, aT’) = 1 for all a. Therefore we have g = 1. Then g^l = 1 and g generates the subgroup in GF(p^K )* of the l-th roots of unity.

(4)  From Q = kP we get b = g^k by Theorem 8.5.2. Hence k is also the discrete logarithm for the base g in Ey .The discrete logarithmproblem in Ey can be solved subexponentially in log(p^K), for instance with the index calculus method for Ey (see [CP]). It follows that altogether the MOV-algorithm is subexponential and bounded by the running time of the index calculus method.

We end with some closing comments on the MOV-algorithm.

First of all, the MOV-algorithm for (_p) with p > 5 is advantageous if the running time is smaller than the running time of Pollard’s p −method for (_p) (see Chapter 6). Computational experiments show that this happens if 2 < K < 6 for the embedding degree of (_p).

Second, the MOV-algorithm can be extended for E(W_q), q = pⁿ, p > 5.

Next, C. Diem has recently shown in [Di1] that the discrete logarithm problem in (_p) can be solved probabilistically in an expected time of e^O(logp). His algorithm is based on an extension of the index calculus method for (_p). In fact Diem further has a strong extension for E(P_q), q = pⁿ,p > 5. Most importantly he proved that there exists an infinite sequence (F¡) of fields, F¡ = F_q, q¡ = pⁿ¡ with p prime such that the discrete logarithm problem for all E(F¡) can be solved probabilistically in subexponential expected time (in the bit length of the group size).

8.6 The Elliptic Curve Digital Signature

In Chapter 4 we described the Digitial Signature Algorithm and then in Chapter 7 the RSA version of this. In this final section of Chapter 8, we present an elliptic curve analogue of DSA which puts the protocol within an elliptic curve group, rather than in . This analogue is called the Elliptic Curve Digital Signature Algorithm abbreviated ECDSA. In 2006 this was certified by the United States National Bureau of Standards and Technology for use in the US administration.This was the third signature algorithm certified in this way, after DSA and the RSA signature Method.

In the ECDSA a signed message m ϵ M is to be sent from party A to party B. To do this we proceed as follows.

Phase I: The key generation

(1)  A chooses a large prime number p > 5 and an elliptic curve E(Z_p).

(2)  A finds a point P ϵ (_p) whose order is a prime number q = p.

(3)   A chooses randomly x ϵ {1,…,q − 1} and calculates Q = xP. The public key of A is then Q and the secret key of A is x.

(4)  A chooses a hash function h : M {1,2,…, N} with N sufficiently large.

Phase II: A now signs the message as follows

(1)  A chooses randomly k ϵ {1,…,q − 1} and calculates kP = (x₁, yj ϵ (_p).

(2)  A calculates the number r = x₁ (mod q) with 0 < r < q − 1. If r = 0 then A repeats II (1) and II (2) until he finds an r = 0.

(3)  Let r = 0. Using the extended Euclidean algorithm A finds a number I with 1 < l< q − 1 and Ik = 1 (modq).

(4)  A calculates the number s = l(h(m) + xr) (mod q) with 0 < s < q − 1. If s = 0 then A starts again with step II (1).

(5)  Now let r = 0 and s = 0. A adds the signature (r, s) to the message and sends everything to B.

Phase III: B verifies the signature

(1)  B takes an authenticated copy of the public key Q of A.

(2)  Bchecks if r,s e{1,…,q − 1}.

(3)  B calculates w = s^-1 (mod q) and h(m) ϵ {1,…, N}.

(4)  B calculates u₁ = h(m)w (modq) andu₂ = rw (mod q).

(5)  B calculates u₁P + u₂Q = (x₀,y₀) ϵ (_p) andv = x₀ (modq), 0 < v < q − 1.

(6)  B accepts the signature if v = r.

We note that this signature is manageable. The probability for r = 0 in Step II (2) is about 1. Analogously the probability for s = 0 in Step II (4) is about 1 and hence very small. Therefore the loops in phase II are finite with probability 1.

Number theoretically we can show that the ECDSA is correct. First, modulo q we have

v = x₀ = u₁P + u₂Q = h(m)wP + rwQ = s^-1(h(m) + rx)P = k(h(m) + rx)^-1(h(m) + rx)P = kP = x₁ = r.

Therefore B accepts the correct signature.

If r = 0 in Step II (2) then we would get s = £h(m) (mod q) in Step (8) and (r, s) would not depend on the knowledge of x.

If s = 0 in Step I (4) then B could not calculate w in Step III (3).

We now examine the cryptanalysis of this digital signature protocol.

(1)  We have roughly q « p. To obtain similar security as in DSA q should have about 160 bits. The signature then has about 320 bits.

(2)  To get (k, x) from (r, s) we must get x from Q = xP, that is, we must solve the discrete log problem in the subgroup (P) of (_p).

(3)  The prime numbers p and q should not be equal. Otherwise the Froebenius trace is congruent to 1 modulo p and we would be able to calculate the discrete logarithm efficiently.

(4)  The elliptic curve should not be a super singular curve.

(5)  For each user we could choose (_p) and P differently. But then (a, b, p) should be in the public key of A.

8.7 Exercises

8.1    Construct fields with 4 and 9 elements explicitly. Show their addition and multiplication tables.

8.2    Let K be a field of characteristic unequal to 2 or 3. Given an equation of the form

with a₁,a₂, a₃,a₄,a₆ ϵ K.

Then there is a transformation

x a₁x + a₂y + a₃, y p₁x + fi₂y + fi₃

with a₁, a₂, a₃,fi₂, fi₃ ϵ K which transforms (*) into the Weierstrass form

y² = x³ + ax + b

with a, b ϵ K.

8.3    Let K be a field and K its algebraic closure. Show that the polynomial x³ + ax + b with a, b ϵ K has a multiple zero if and only if 4a³ + 27b² = 0.

Take care that your argument is correct if K has characteristic 2 or 3.

8.4    Let K be a finite field with |K| = q. Show that there are exactly q² −q polynomials of the form x³ + ax + b with a, b ϵ K which have no multiple zeros in any extension field of K.

8.5    Let y² = x³ + x + 6bea curve over ₁₁. Show that

(a)  y² = x³ + x +6 is an elliptic curve over ₁₁.

(b)  (₁₁) is cyclic of order 13.

8.6    Let y² = x³ + x be a curve over ₅. Show that

(a)  y² = x³ + x is an elliptic curve over ₅.

(b)  (₅) is isomorphic to the Klein 4-group ₂ x ₂.

8.7    Determine all possible groups (₅) for elliptic curves over ₅. Give all possible orders for a group (₅).

8.8    Let K be an algebraically closed field of characteristic unequal to 2 or 3. Let E(K) be an elliptic curve over K. Show that

{P ϵ E(K) | 3P = O}u O

is isomorphic to the group ₃ x₃.

8.9    Describe in detail the Diffie-Hellman key exchange protocol for elliptic curves.

8.10    Let p be a prime number with p = 3 (mod 4) and let (_p) be an elliptic curve over _p. Find a polynomial time algorithm which constructs a point (x, y) on (_p) for a given x e_p if such a point exists.

Use this algorithm to find a point (2, y) on

y² = x³ + x +1

over _p with p = 111119.

Hint: Use the construction of square roots in _p for p = 3 (mod 4).