Elliptic Curve Cryptography

In this chapter, weā™ll discuss several cryptosystems based on elliptic curves,

especially on the discrete logarithm problem for elliptic curves. Weā™ll also

treat various related ideas, such as digital signatures.

One might wonder why elliptic curves are used in cryptographic situations.

The reason is that elliptic curves provide security equivalent to classical sys-

tems while using fewer bits. For example, it is estimated in [12] that a key

size of 4096 bits for RSA gives the same level of security as 313 bits in an

elliptic curve system. This means that implementations of elliptic curve cryp-

tosystems require smaller chip size, less power consumption, etc. Daswani and

Boneh [14] performed experiments using 3Comā™s PalmPilot, which is a small

hand-held device that is larger than a smart card but smaller than a laptop

computer. They found that generating a 512-bit RSA key took 3.4 minutes,

while generating a 163-bit ECC-DSA key to 0.597 seconds. Though certain

procedures, such as signature veriļ¬cations, were slightly faster for RSA, the

elliptic curve methods such as ECC-DSA clearly oļ¬er great increases in speed

in many situations.

6.1 The Basic Setup

Alice wants to send a message, often called the plaintext, to Bob. In

order to keep the eavesdropper Eve from reading the message, she encrypts

it to obtain the ciphertext. When Bob receives the ciphertext, he decrypts

it and reads the message. In order to encrypt the message, Alice uses an

encryption key. Bob uses a decryption key to decrypt the ciphertext.

Clearly, the decryption key must be kept secret from Eve.

There are two basic types of encryption. In symmetric encryption, the

encryption key and decryption key are the same, or one can be easily deduced

from the other. Popular symmetric encryption methods include the Data

Encryption Standard (DES) and the Advanced Encryption Standard (AES,

often referred to by its original name Rijndael). In this case, Alice and Bob

169

Ā© 2008 by Taylor & Francis Group, LLC

170 CHAPTER 6 ELLIPTIC CURVE CRYPTOGRAPHY

need to have some way of establishing a key. For example, Bob could send

a messenger to Alice several days in advance. Then, when it is time to send

the message, they both will have the key. Clearly this is impractical in many

situations.

The other type of encryption is public key encryption, or asymmetric

encryption. In this case, Alice and Bob do not need to have prior contact.

Bob publishes a public encryption key, which Alice uses. He also has a private

decryption key that allows him to decrypt ciphertexts. Since everyone knows

the encryption key, it should be infeasible to deduce the decryption key from

the encryption key. The most famous public key system is known as RSA

and is based on the diļ¬culty of factoring integers into primes. Another well-

known system is due to ElGamal and is based on the diļ¬culty of the discrete

logarithm problem.

Generally, public key systems are slower than good symmetric systems.

Therefore, it is common to use a public key system to establish a key that

is then used in a symmetric system. The improvement in speed is important

when massive amounts of data are being transmitted.

6.2 Diļ¬e-Hellman Key Exchange

Alice and Bob want to agree on a common key that they can use for ex-

changing data via a symmetric encryption scheme such as DES or AES. For

example, Alice and Bob could be banks that want to transmit ļ¬nancial data.

It is impractical and time-consuming to use a courier to deliver the key. More-

over, we assume that Alice and Bob have had no prior contact and therefore

the only communication channels between them are public. One way to estab-

lish a secret key is the following method, due to Diļ¬e and Hellman (actually,

they used multiplicative groups of ļ¬nite ļ¬elds).

1. Alice and Bob agree on an elliptic curve E over a ļ¬nite ļ¬eld Fq such

that the discrete logarithm problem is hard in E(Fq ). They also agree

on a point P ā E(Fq ) such that the subgroup generated by P has large

order (usually, the curve and point are chosen so that the order is a

large prime).

2. Alice chooses a secret integer a, computes Pa = aP , and sends Pa to

Bob.

3. Bob chooses a secret integer b, computes Pb = bP , and sends Pb to Alice.

4. Alice computes aPb = abP .

5. Bob computes bPa = baP .

Ā© 2008 by Taylor & Francis Group, LLC

171

SECTION 6.2 DIFFIE-HELLMAN KEY EXCHANGE

6. Alice and Bob use some publicly agreed on method to extract a key from

abP . For example, they could use the last 256 bits of the x-coordinate

of abP as the key. Or they could evaluate a hash function at the x-

coordinate.

The only information that the eavesdropper Eve sees is the curve E, the ļ¬nite

ļ¬eld Fq , and the points P , aP , and bP . She therefore needs to solve the

following:

DIFFIE-HELLMAN PROBLEM

Given P , aP , and bP in E(Fq ), compute abP .

If Eve can solve discrete logs in E(Fq ), then she can use P and aP to ļ¬nd

a. Then she can compute a(bP ) to get abP . However, it is not known whether

there is some way to compute abP without ļ¬rst solving a discrete log problem.

A related question is the following:

DECISION DIFFIE-HELLMAN PROBLEM

Given P , aP , and bP in E(Fq ), and given a point Q ā E(Fq ) determine

whether or not Q = abP .

In other words, if Eve receives an anonymous tip telling her abP , can she

verify that the information is correct?

The Diļ¬e-Hellman problem and the Decision Diļ¬e-Hellman problem can

be asked for arbitrary groups. Originally, they appeared in the context of

multiplicative groups FĆ— of ļ¬nite ļ¬elds.

q

For elliptic curves, the Weil pairing can be used to solve the Decision Diļ¬e-

Hellman problem in some cases. We give one such example.

Let E be the curve y 2 = x3 + 1 over Fq , where q ā” 2 (mod 3). By Proposi-

tion 4.33, E is supersingular. Let Ļ ā Fq2 be a primitive third root of unity.

Note that Ļ ā Fq since the order of FĆ— is q ā’ 1, which is not a multiple of 3.

q

Deļ¬ne a map

Ī² : E(Fq ) ā’ E(Fq ), (x, y) ā’ (Ļx, y), Ī²(ā) = ā.

It is straightforward to show, using the formulas for the addition law, that Ī²

is an isomorphism (Exercise 6.1).

Suppose P ā E(Fq ) has order n. Then Ī²(P ) also has order n. Deļ¬ne the

modiļ¬ed Weil pairing

en (P1 , P2 ) = en (P1 , Ī²(P2 )),

Ė

where en is the usual Weil pairing and P1 , P2 ā E[n].

Ā© 2008 by Taylor & Francis Group, LLC

172 CHAPTER 6 ELLIPTIC CURVE CRYPTOGRAPHY

LEMMA 6.1

Assume 3 n. If P ā E(Fq ) has order exactly n, then en (P, P ) is a primitive

Ė

nth root of unity.

PROOF Suppose uP = vĪ²(P ) for some integers u, v. Then

Ī²(vP ) = vĪ²(P ) = uP ā E(Fq ).

If vP = ā, then uP = ā, so u ā” 0 (mod n). If vP = ā, write vP = (x, y)

with x, y ā Fq . Then

(Ļx, y) = Ī²(vP ) ā E(Fq ).

Since Ļ ā Fq , we must have x = 0. Therefore vP = (0, Ā±1), which has order

3. This is impossible since we have assumed that 3 n. It follows that the

only relation of the form uP = vĪ²(P ) has u, v ā” 0 (mod n), so P and Ī²(P )

form a basis of E[n]. By Corollary 3.10, en (P, P ) = en (P, Ī²(P )) is a primitive

Ė

nth root of unity.

Suppose now that we know P, aP, bP, Q and we want to decide whether or

not Q = abP . First, use the usual Weil pairing to decide whether or not Q is a

multiple of P . By Lemma 5.1, Q is a multiple of P if and only if en (P, Q) = 1.

Assume this is the case, so Q = tP for some t. We have

en (aP, bP ) = en (P, P )ab = en (P, abP ) and en (Q, P ) = en (P, P )t .

Ė Ė Ė Ė Ė

Assume 3 n. Then en (P, P ) is a primitive nth root of unity, so

Ė

Q = abP āā’ t ā” ab (mod n) āā’ en (aP, bP ) = en (Q, P ).

Ė Ė

This solves the Decision Diļ¬e-Hellman problem in this case. Note that we

did not need to compute any discrete logs, even in ļ¬nite ļ¬elds. All that was

needed was to compute the Weil pairing.

The above method was pointed out by Joux and Nguyen. For more on the

Decision Diļ¬e-Hellman problem, see [13].

Joux [56] (see also [124]) has given another application of the modiļ¬ed

Weil pairing to what is known as tripartite Diļ¬e-Hellman key exchange.

Suppose Alice, Bob, and Chris want to establish a common key. The standard

Diļ¬e-Hellman procedure requires two rounds of interaction. The modiļ¬ed

Weil pairing allows this to be cut to one round. As above, let E be the curve

y 2 = x3 + 1 over Fq , where q ā” 2 (mod 3). Let P be a point of order n.

Usually, n should be chosen to be a large prime. Alice, Bob, and Chris do the

following.

1. Alice, Bob, and Chris choose secret integers a, b, c mod n, respectively.

2. Alice broadcasts aP , Bob broadcasts bP , and Chris broadcasts cP .

Ā© 2008 by Taylor & Francis Group, LLC

173

SECTION 6.3 MASSEY-OMURA ENCRYPTION

3. Alice computes en (bP, cP )a , Bob computes en (aP, cP )b , and Chris com-

Ė Ė

c

putes en (aP, bP ) .

Ė

4. Since each of the three users has computed the same number, they use

this number to produce a key, using some publicly prearranged method.

Recall that, since E is supersingular, the discrete log problem on E can be

reduced to a discrete log problem for FĆ— (see Section 5.3.1). Therefore, q

q2

should be chosen large enough that this discrete log problem is hard.

For more on cryptographic applications of pairings, see [57].

6.3 Massey-Omura Encryption

Alice wants to send a message to Bob over public channels. They have not

yet established a private key. One way to do this is the following. Alice puts

her message in a box and puts her lock on it. She sends the box to Bob. Bob

puts his lock on it and sends it back to Alice. Alice then takes her lock oļ¬

and sends the box back to Bob. Bob then removes his lock, opens the box,

and reads the message.

This procedure can be implemented mathematically as follows.

1. Alice and Bob agree on an elliptic curve E over a ļ¬nite ļ¬eld Fq such

that the discrete log problem is hard in E(Fq ). Let N = #E(Fq ).

2. Alice represents her message as a point M ā E(Fq ). (Weā™ll discuss how

to do this below.)

3. Alice chooses a secret integer mA with gcd(mA , N ) = 1, computes M1 =

mA M , and sends M1 to Bob.

4. Bob chooses a secret integer mB with gcd(mB , N ) = 1, computes M2 =

mB M1 , and sends M2 to Alice.

5. Alice computes mā’1 ā ZN . She computes M3 = mā’1 M2 and sends M3

A A

to Bob.

6. Bob computes mā’1 ā ZN . He computes M4 = mā’1 M3 . Then M4 = M

B B

is the message.

Letā™s show that M4 is the original message M . Formally, we have

M4 = mā’1 mā’1 mB mA M = M,

B A

but we need to justify the fact that mā’1 , which is an integer representing

A

the inverse of mA mod N , and mA cancel each other. We have mā’1 mA ā” 1

A

Ā© 2008 by Taylor & Francis Group, LLC

174 CHAPTER 6 ELLIPTIC CURVE CRYPTOGRAPHY

(mod N ), so mā’1 mA = 1 + kN for some k. The group E(Fq ) has order N ,

A

so Lagrangeā™s theorem implies that N R = ā for any R ā E(Fq ). Therefore,

mā’1 mA R = (1 + kN )R = R + kā = R.

A

Applying this to R = mB M , we ļ¬nd that

M3 = mā’1 mB mA M = mB M.

A

Similarly, mā’1 and mB cancel, so

B

M4 = mā’1 M3 = mā’1 mB M = M.

B B

The eavesdropper Eve knows E(Fq ) and the points mA M , mB mA M , and

mB M . Let a = mā’1 , b = mā’1 , P = mA mB M . Then we see that Eve knows

A B

P, bP, aP and wants to ļ¬nd abP . This is the Diļ¬e-Hellman problem (see

Section 6.2).

The above procedure works in any ļ¬nite group. It seems that the method

is rarely used in practice.

It remains to show how to represent a message as a point on an elliptic curve.

We use a method proposed by Koblitz. Suppose E is an elliptic curve given by

y 2 = x3 +Ax+B over Fp . The case of an arbitrary ļ¬nite ļ¬eld Fq is similar. Let

m be a message, expressed as a number 0 ā¤ m < p/100. Let xj = 100m + j

for 0 ā¤ j < 100. For j = 0, 1, 2, . . . , 99, compute sj = x3 + Axj + B . If

j

(pā’1)/2

ā” 1 (mod p), then sj is a square mod p, in which case we do not

sj

need to try any more values of j. When p ā” 3 (mod 4), a square root of

(p+1)/4

sj is then given by yj ā” sj (mod p) (see Exercise 6.7). When p ā” 1

(mod 4), a square root of sj can also be computed, but the procedure is more

complicated (see [25]). We obtain a point (xj , yj ) on E. To recover m from

(xj , yj ), simply compute [xj /100] (= the greatest integer less than or equal

to xj /100). Since sj is essentially a random element of FĆ— , which is cyclic of

p

even order, the probability is approximately 1/2 that sj is a square. So the

probability of not being able to ļ¬nd a point for m after trying 100 values is

around 2ā’100 .

6.4 ElGamal Public Key Encryption

Alice wants to send a message to Bob. First, Bob establishes his public

key as follows. He chooses an elliptic curve E over a ļ¬nite ļ¬eld Fq such that

the discrete log problem is hard for E(Fq ). He also chooses a point P on E

(usually, it is arranged that the order of P is a large prime). He chooses a

secret integer s and computes B = sP . The elliptic curve E, the ļ¬nite ļ¬eld

Ā© 2008 by Taylor & Francis Group, LLC

175

SECTION 6.5 ELGAMAL DIGITAL SIGNATURES

Fq , and the points P and B are Bobā™s public key. They are made public.

Bobā™s private key is the integer s.

To send a message to Bob, Alice does the following:

1. Downloads Bobā™s public key.

2. Expresses her message as a point M ā E(Fq ).

3. Chooses a secret random integer k and computes M1 = kP .

4. Computes M2 = M + kB.

5. Sends M1 , M2 to Bob.

Bob decrypts by calculating

M = M2 ā’ sM1 .

This decryption works because

M2 ā’ sM1 = (M + kB) ā’ s(kP ) = M + k(sP ) ā’ skP = M.

The eavesdropper Eve knows Bobā™s public information and the points M1

and M2 . If she can calculate discrete logs, she can use P and B to ļ¬nd s,

which she can then use to decrypt the message as M2 ā’ sM1 . Also, she could

use P and M1 to ļ¬nd k. Then she can calculate M = M2 ā’ kB. If she cannot

calculate discrete logs, there does not appear to be a way to ļ¬nd M .

It is important for Alice to use a diļ¬erent random k each time she sends

a message to Bob. Suppose Alice uses the same k for both M and M . Eve

recognizes this because then M1 = M1 . She then computes M2 ā’ M2 =

M ā’ M . Suppose M is a sales announcement that is made public a day later.

Then Eve ļ¬nds out M , so she calculates M = M ā’ M2 + M2 . Therefore,

knowledge of one plaintext M allows Eve to deduce another plaintext M in

this case.

The ElGamal Public Key system, in contrast to the ElGamal signature

scheme of the next section, does not appear to be widely used.

6.5 ElGamal Digital Signatures

Alice wants to sign a document. The classical way is to write her signature

on a piece of paper containing the document. Suppose, however, that the

document is electronic, for example, a computer ļ¬le. The naive solution

would be to digitize Aliceā™s signature and append it to the ļ¬le containing the

document. In this case, evil Eve can copy the signature and append it to

another document. Therefore, steps must be taken to tie the signature to

Ā© 2008 by Taylor & Francis Group, LLC

176 CHAPTER 6 ELLIPTIC CURVE CRYPTOGRAPHY

the document in such a way that it cannot be used again. However, it must

be possible for someone to verify that the signature is valid, and it should

be possible to show that Alice must have been the person who signed the

document. One solution to the problem relies on the diļ¬culty of discrete

logs. Classically, the algorithm was developed for the multiplicative group of

a ļ¬nite ļ¬eld. In fact, it applies to any ļ¬nite group. Weā™ll present it for elliptic

curves.

Alice ļ¬rst must establish a public key. She chooses an elliptic curve E over

a ļ¬nite ļ¬eld Fq such that the discrete log problem is hard for E(Fq ). She also

chooses a point A ā E(Fq ). Usually the choices are made so that the order

N of A is a large prime. Alice also chooses a secret integer a and computes

B = aA. Finally, she chooses a function

f : E(Fq ) ā’ Z.

For example, if Fq = Fp , then she could use f (x, y) = x, where x is regarded

as an integer, 0 ā¤ x < p. The function f needs no special properties, except

that its image should be large and only a small number of inputs should

produce any given output (for example, for f (x, y) = x, at most two points

(x, y) yield a given output x).

Aliceā™s public information is E, Fq , f , A, and B. She keeps a private. The

integer N does not need to be made public. Its secrecy does not aļ¬ect our

analysis of the security of the system. To sign a document, Alice does the

following:

1. Represents the document as an integer m (if m > N , choose a larger

curve, or use a hash function (see below)).

2. Chooses a random integer k with gcd(k, N ) = 1 and computes R = kA.

3. Computes s ā” k ā’1 (m ā’ af (R)) (mod N ).

The signed message is (m, R, s). Note that m, s are integers, while R is a point

on E. Also, note that Alice is not trying to keep the document m secret. If

she wants to do that, then she needs to use some form of encryption. Bob

veriļ¬es the signature as follows:

1. Downloads Aliceā™s public information.

2. Computes V1 = f (R)B + sR and V2 = mA.

3. If V1 = V2 , he declares the signature valid.

If the signature is valid, then V1 = V2 since

V1 = f (R)B + sR = f (R)aA + skA = f (R)aA + (m ā’ af (R))A = mA = V2 .

We have used the fact that sk ā” m ā’ af (R), hence sk = m ā’ af (R) + zN for

some integer z. Therefore,

skA = (m ā’ af (R))A + zN A = (m ā’ af (R))A + ā = (m ā’ af (R))A.

Ā© 2008 by Taylor & Francis Group, LLC

177

SECTION 6.5 ELGAMAL DIGITAL SIGNATURES

This is why the congruence deļ¬ning s was taken mod N .

If Eve can calculate discrete logs, then she can use A and B to ļ¬nd a.

In this case, she can put Aliceā™s signature on any message. Alternatively,

Eve can use A and R to ļ¬nd k. Since she knows s, f (R), m, she can then

use ks ā” m ā’ af (R) (mod N ) to ļ¬nd a. If d = gcd(f (R), N ) = 1, then

af (R) ā” m ā’ ks (mod N ) has d solutions for a. As long as d is small, Eve

can try each possibility until she obtains B = aA. Then she can use a, as

before, to forge Aliceā™s signature on arbitrary messages.

As we just saw, Alice must keep a and k secret. Also, she must use a

diļ¬erent random k for each signature. Suppose she signs m and m using the

same k to obtain signed messages (m, R, s) and (m , R, s ). Eve immediately

recognizes that k has been used twice since R is the same for both signatures.

The equations for s, s yield the following:

ks ā” m ā’ af (R) (mod N )

ks ā” m ā’ af (R) (mod N ).

Subtracting yields k(sā’s ) ā” mā’m (mod N ). Let d = gcd(sā’s , N ). There

are d possible values for k. Eve tries each one until R = kA is satisļ¬ed. Once

she knows k, she can ļ¬nd a, as above.

It is perhaps not necessary for Eve to solve discrete log problems in order to

forge Aliceā™s signature on another message m. All Eve needs to do is produce

R, s such that the veriļ¬cation equation V1 = V2 is satisļ¬ed. This means that

she needs to ļ¬nd R = (x, y) and s such that

f (R)B + sR = mA.

If she chooses some point R (there is no need to choose an integer k), she

needs to solve the discrete log problem sR = mA ā’ f (R)B for the integer s.

If, instead, she chooses s, then she must solve an equation for R = (x, y). This

equation appears to be at least as complex as a discrete log problem, though it

has not been analyzed as thoroughly. Moreover, no one has been able to rule

out the possibility of using some procedure that ļ¬nds R and s simultaneously.

There are ways of using a valid signed message to produce another valid signed

message (see Exercise 6.2). However, the messages produced are unlikely to

be meaningful messages.

The general belief is that the security of the ElGamal system is very close

to the security of discrete logs for the group E(Fq ).

A disadvantage of the ElGamal system is that the signed message (m, R, s)

is approximately three times as long as the original message (it is not necessary

to store the full y-coordinate of R since there are only two choices for y for

a given x). A more eļ¬cient method is to choose a public hash function H

and sign H(m). A cryptographic hash function is a function that takes

inputs of arbitrary length, sometimes a message of billions of bits, and outputs

values of ļ¬xed length, for example, 160 bits. A hash function H should have

the following properties:

Ā© 2008 by Taylor & Francis Group, LLC

178 CHAPTER 6 ELLIPTIC CURVE CRYPTOGRAPHY

1. Given a message m, the value H(m) can be calculated very quickly.

2. Given y, it is computationally infeasible to ļ¬nd m with H(m) = y. (This

says that H is preimage resistant.)

3. It is computationally infeasible to ļ¬nd distinct messages m1 and m2

with H(m1 ) = H(m2 ). (This says that H is strongly collision-free.)

The reason for (2) and (3) is to prevent Eve from producing messages with

a desired hash value, or two messages with the same hash value. This helps

prevent forgery. There are several popular hash functions available, for exam-

ple, MD5 (due to Rivest; it produces a 128-bit output) and the Secure Hash

Algorithm (from NIST; it produces a 160-bit output). We wonā™t discuss these

here. For details, see [81]. Recent work of Wang, Yin, and Yu [127] has found

weaknesses in them, so the subject is somewhat in a state of ļ¬‚ux.

If Alice uses a hash function, the signed message is then

(m, RH , sH ),

where (H(m), RH , sH ) is a valid signature. To verify that the signature

(m, RH , sH ) is valid, Bob does the following:

1. Downloads Aliceā™s public information.

2. Computes V1 = f (RH )B + sH RH and V2 = H(m)A.

3. If V1 = V2 , he declares the signature valid.

The advantage is that a very long message m containing billions of bits has a

signature that requires only a few thousand extra bits. As long as the discrete

log problem is hard for E(Fq ), Eve will be unable to put Aliceā™s signature on

another message. The use of a hash function also guards against certain other

forgeries (see Exercise 6.2).

A recent variant of the ElGamal signature scheme due to van Duin is very

eļ¬cient in certain aspects. For example, it avoids the computation of k ā’1 ,

and its veriļ¬cation procedure requires only two computations of an integer

times a point. As before, Alice has a document m that she wants to sign. To

set up the system, she chooses an elliptic curve E over a ļ¬nite ļ¬eld Fq and

a point A ā E(Fq ) of large prime order N . She also chooses a cryptographic

hash function H. She chooses a secret integer a and computes B = aA. The

public information is (E, q, N, H, A, B). The secret information is a. To sign

m, Alice does the following:

1. Chooses a random integer k mod N and computes R = kA.

2. Computes t = H(R, m)k + a (mod N ).

Ā© 2008 by Taylor & Francis Group, LLC

179

SECTION 6.6 THE DIGITAL SIGNATURE ALGORITHM

The signed document is (m, R, t).

To verify the signature, Bob downloads Aliceā™s public information and

checks whether

tA = H(R, m)R + B

is true. If it is, the signature is declared valid; otherwise, it is invalid.

6.6 The Digital Signature Algorithm

The Digital Signature Standard [1],[86] is based on the Digital Signature Al-

gorithm (DSA). The original version used multiplicative groups of ļ¬nite ļ¬elds.

A more recent elliptic curve version (ECDSA) uses elliptic curves. The algo-

rithm is a variant on the ElGamal signature scheme, with some modiļ¬cations.

We sketch the algorithm here.

Alice wants to sign a document m, which is an integer (actually, she usually

signs the hash of the document, as in Section 6.5). Alice chooses an elliptic

curve over a ļ¬nite ļ¬eld Fq such that #E(Fq ) = f r, where r is a large prime

and f is a small integer, usually 1,2, or 4 (f should be small in order to keep

the algorithm eļ¬cient). She chooses a base point G in E(Fq ) of order r.

Finally, Alice chooses a secret integer a and computes Q = aG. Alice makes

public the following information:

Fq , E, r, G, Q.

(There is no need to keep f secret; it can be deduced from q and r using

Hasseā™s theorem by the technique in Examples 4.6 and 4.7.) To sign the

message m Alice does the following:

1. Chooses a random integer k with 1 ā¤ k < r and computes R = kG =

(x, y).

2. Computes s = kā’1 (m + ax) (mod r).

The signed document is

(m, R, s).

To verify the signature, Bob does the following.

1. Computes u1 = sā’1 m (mod r) and u2 = sā’1 x (mod r).

2. Computes V = u1 G + u2 Q.

3. Declares the signature valid if V = R.

Ā© 2008 by Taylor & Francis Group, LLC

180 CHAPTER 6 ELLIPTIC CURVE CRYPTOGRAPHY

If the message is signed correctly, the veriļ¬cation equation holds:

V = u1 G + u2 Q = sā’1 mG + sā’1 xQ = sā’1 (mG + xaG) = kG = R.

The main diļ¬erence between the ECDSA and the ElGamal system is the

veriļ¬cation procedure. In the ElGamal system, the veriļ¬cation equation

f (R)B + sR = mA requires three computations of an integer times a point.

These are the most expensive parts of the algorithm. In the ECDSA, only two

computations of an integer times a point are needed. If many veriļ¬cations

are going to be made, then the improved eļ¬ciency of the ECDSA is valuable.

This is the same type of improvement as in the van Duin system mentioned

at the end of the previous section.

6.7 ECIES

The Elliptic Curve Integrated Encryption Scheme (ECIES) was invented

by Bellare and Rogaway [2]. It is a public key encryption scheme.

Alice wants to send a message m to Bob. First, Bob establishes his public

key. He chooses an elliptic curve E over a ļ¬nite ļ¬eld Fq such that the discrete

log problem is hard for E(Fq ), and he chooses a point A on E, usually of large

prime order N . He then chooses a secret integer s and computes B = sA.

The public key is (q, E, N, A, B). The private key is s.

The algorithm also needs two cryptographic hash functions, H1 and H2 ,

and a symmetric encryption function Ek (depending on a key k) that are

publicly agreed upon.

To encrypt and send her message, Alice does the following:

1. Downloads Bobā™s public key.

2. Chooses a random integer k with 1 ā¤ k ā¤ N ā’ 1.

3. Computes R = kA and Z = kB.

4. Writes the output of H1 (R, Z) as k1 k2 (that is, k1 followed by k2 ),

where k1 and k2 have speciļ¬ed lengths.

5. Computes C = Ek1 (m) and t = H2 (C, k2 ).

6. Sends (R, C, t) to Bob.

To decrypt, Bob does the following:

1. Computes Z = sR, using his knowledge of the secret key s.

2. Computes H1 (R, Z) and writes the output as k1 k2 .

Ā© 2008 by Taylor & Francis Group, LLC

181

SECTION 6.8 A PUBLIC KEY SCHEME BASED ON FACTORING

3. Computes H2 (C, k2 ). If it does not equal t, Bob stops and rejects the

ciphertext. Otherwise, he continues.

4. Computes m = Dk1 (C), where Dk1 is the decryption function for Ek1 .

An important feature is the authentication procedure in step (3) of the de-

cryption. In many cryptosystems, an attacker can choose various ciphertexts

and force Bob to decrypt them. These decryptions are used to attack the sys-

tem. In the present system, the attacker can generate ciphertexts by choosing

C and k2 and then letting t = H2 (C, k2 ). But the attacker does not know Z,

so he cannot use the same value k2 that Bob obtains from H1 (R, Z). There-

fore, it is very unlikely that t = H2 (C, k2 ) will equal t = H2 (C, k2 ). With

very high probability, Bob simply rejects the ciphertext and does not return

a decryption.

In our description of the procedure, we used hash functions for the au-

thentication. There are other message authentication methods that could be

used.

An advantage of ECIES over the Massey-Omura and ElGamal public key

methods is that the message is not represented as a point on the curve. More-

over, since a keyed symmetric method is used to send the message, we do not

need to do a new elliptic curve calculation for each block of the message.

6.8 A Public Key Scheme Based on Factoring

Most cryptosystems using elliptic curves are based on the discrete log prob-

lem, in contrast to the situation for classical systems, which are sometimes

based on discrete logs and sometimes based on the diļ¬culty of factorization.

The most famous public key cryptosystem is called RSA (for Rivest-Shamir-

Adleman) and proceeds as follows. Alice wants to send a message to Bob. Bob

secretly chooses two large primes p, q and multiplies them to obtain n = pq.

Bob also chooses integers e and d with ed ā” 1 (mod (p ā’ 1)(q ā’ 1)). He makes

n and e public and keeps d secret. Aliceā™s message is a number m (mod n).

She computes c ā” me (mod n) and sends c to Bob. Bob computes m ā” cd

(mod n) to obtain the message. If Eve can ļ¬nd p and q, then she can solve

ed ā” 1 (mod (p ā’ 1)(q ā’ 1)) to obtain d. It can be shown (by methods similar

to those used in the elliptic curve scheme below; see [121]) that if Eve can

ļ¬nd the decryption exponent d, then she probably can factor n. Therefore,

the diļ¬culty of factoring n is the key to the security of the RSA system.

A natural question is whether there is an elliptic curve analogue of RSA. In

the following, we present one such system, due to Koyama-Maurer-Okamoto-

Vanstone. It does not seem to be used much in practice.

Alice want to send a message to Bob. They do the following.

Ā© 2008 by Taylor & Francis Group, LLC

182 CHAPTER 6 ELLIPTIC CURVE CRYPTOGRAPHY

1. Bob chooses two distinct large primes p, q with p ā” q ā” 2 (mod 3) and

computes n = pq.

2. Bob chooses integers e, d with ed ā” 1 (mod lcm(p + 1, q + 1)). (He could

use (p + 1)(q + 1) in place of lcm(p + 1, q + 1).)

3. Bob makes n and e public (they form his public key) and he keeps d, p, q

private.

4. Alice represents her message as a pair of integers (m1 , m2 ) (mod n).

She regards (m1 , m2 ) as a point M on the elliptic curve E given by

y 2 = x3 + b mod n,

where b = m2 ā’ m3 (mod n) (she does not need to compute b).

2 1

5. Alice adds M to itself e times on E to obtain C = (c1 , c2 ) = eM . She

sends C to Bob.

6. Bob computes M = dC on E to obtain M .

Weā™ll discuss the security of the system shortly. But, ļ¬rst, there are several

points that need to be discussed.

1. Note that the formulas for the addition law on E never use the value of

b. Therefore, Alice and Bob never need to compute it. Eve can compute

it, if she wants, as b = c2 ā’ c3 .

2 1

2. The computation of eM and dC on E are carried out with the formulas

for the group law on an elliptic curve, with all of the computations being

done mod n. Several times during the computation, expressions such

as (y2 ā’ y1 )/(x2 ā’ x1 ) are encountered. These are changed to integers

mod n by ļ¬nding the multiplicative inverse of (x2 ā’ x1 ) mod n. This

requires gcd(x2 ā’ x1 , n) = 1. If the gcd is not 1, then it is p, q, or n.

If we assume it is very hard to factor n, then we regard the possibility

of the gcd being p or q as very unlikely. If the gcd is n, then the slope

is inļ¬nite and the sum of the points in question is ā. The usual rules

for working with ā are followed. For technical details of working with

elliptic curves mod n, see Section 2.11.

By the Chinese Remainder Theorem, an integer mod n may be regarded

as a pair of integers, one mod p and one mod q. Therefore, we can regard

a point on E in Zn as a pair of points, one on E mod p and the other

on E mod q. In this way, we have

E(Zn ) = E(Fp ) ā• E(Fq ). (6.1)

For example, the point (11, 32) on y 2 = x3 + 8 mod 35 can be regarded

as the pair of points

(1, 2) mod 5, (4, 4) mod 7.

Ā© 2008 by Taylor & Francis Group, LLC

183

SECTION 6.8 A PUBLIC KEY SCHEME BASED ON FACTORING

Any such pair of points can be combined to obtain a point mod n. There

is a technicality with points at inļ¬nity, which is discussed in Section 2.11.

3. Using (6.1), we see that the order of E(Zn ) is #E(Fp ) Ā· #E(Fq ). By

Proposition 4.33, E is supersingular mod p and mod q, so we ļ¬nd (by

Corollary 4.32) that

#E(Fp ) = p + 1 and #E(Fq ) = q + 1.

Therefore, (p + 1)M = ā (mod p) and (q + 1)M = ā (mod q). This

means that the decryption works: Write de = 1 + k(p + 1) for some

integer k. Then

dC = deM = (1+k(p+1))M = M +k(p+1)M = M +ā = M (mod p),

and similarly mod q. Therefore, dC = M .

4. A key point of the procedure is that the group order is independent

of b. If Bob chooses a random elliptic curve y 2 = x3 + Ax + B over

Zn , then he has to compute the group order, perhaps by computing it

mod p and mod q. This is infeasible if p and q are chosen large enough

to make factoring n infeasible. Also, if Bob ļ¬xes the elliptic curve,

Alice will have diļ¬culty ļ¬nding points M on the curve. If she does

the procedure of ļ¬rst choosing the x-coordinate as the message, then

solving y 2 ā” m3 + Am + B (mod n) for y, she is faced with the problem

of computing square roots mod n. This is computationally equivalent to

factoring n (see [121]). If Bob ļ¬xes only A (the formulas for the group

operations depend only on A) and allows Alice to choose B so that her

point lies on the curve, then his choice of e, d requires that the group

order be independent of B. This is the situation in the above procedure.

If Eve factors n as pq, then she knows (p + 1)(q + 1), so she can ļ¬nd d with

ed ā” 1 (mod (p + 1)(q + 1)). Therefore, she can decrypt Aliceā™s message.

Suppose that Eve does not yet know the factorization of n, but she ļ¬nds

out the decryption exponent d. We claim that she can, with high probability,

factor n. She does the following:

1. Writes ed ā’ 1 = 2k v with v odd and with k ā„ 1 (k = 0 since p +1 divides

ed ā’ 1).

2 3

2. Picks a random pair of integers R = (r1 , r2 ) mod n, lets b = r2 ā’ r1 ,

and regards R as a point on the elliptic curve E given by y 2 = x3 + b .

3. Computes R0 = vR. If R0 = ā mod n, start over with a new R. If R0

is ā mod exactly one of p, q, then Eve has factored n (see below).

4. For i = 0, 1, 2, . . . , k, computes Ri+1 = 2Ri .

Ā© 2008 by Taylor & Francis Group, LLC

184 CHAPTER 6 ELLIPTIC CURVE CRYPTOGRAPHY

5. If for some i, the point Ri+1 is ā mod exactly one of p, q, then Ri =

(xi , yi ) with yi ā” 0 mod one of p, q. Therefore, gcd(yi , n) = p or q. In

this case, Eve stops, since she has factored n.

6. If for some i, Ri+1 = ā mod n, then Eve starts over with a new random

point.

In a few iterations, this should factor n. Since ed ā’ 1 is a multiple of #E(Zn ),

Rk = (ed ā’ 1)R = edR ā’ R = ā.

Therefore, each iteration of the procedure will eventually end with a point Rj

that is ā mod at least one of p, q. Let 2k be the highest power of 2 dividing

p + 1. If we take a random point P in E(Fp ), then the probability is 1/2 that

the order of P is divisible by 2k . This follows easily from the fact that E(Fp )

is cyclic (see Exercise 6.6). In this case, Rk ā’1 = 2k ā’1 vP = ā (mod p),

while Rk = 2k vP = ā (mod p). If the order is not divisible by 2k , then

Rk ā’1 = ā (mod p). Similarly, if 2k is the highest power of 2 dividing q + 1,

then Rk ā’1 = ā (mod q) half the time, and = ā (mod q) half the time.

Since mod p and mod q are independent, it is easy to see that the sequence

R0 , R1 , R2 , . . . reaches ā mod p and mod q at diļ¬erent indices i at least half

the time. This means that for at least half of the choices of random starting

points R, we obtain a factorization of n.

If R0 = ā mod p, but not mod q, then somewhere in the calculation of R0

there was a denominator of a slope that was inļ¬nite mod p but not mod q.

The gcd of this denominator with n yields p. A similar situation occurs if p

and q are switched. Therefore, if R0 is inļ¬nite mod exactly one of the primes,

Eve obtains a factorization, as claimed in step (3).

We conclude that knowledge of the decryption exponent d is computation-

ally equivalent to knowledge of the factorization of n.

6.9 A Cryptosystem Based on the Weil Pairing

In Chapter 5, we saw how the Weil pairing could be used to reduce the

discrete log problem on certain elliptic curves to the discrete log problem for

the multiplicative group of a ļ¬nite ļ¬eld. In the present section, weā™ll present

a method, due to Boneh and Franklin, that uses the Weil pairing on these

curves to obtain a cryptosystem (other pairings could also be used). The

reader may wonder why we use these curves, since the discrete log problem

is easier on these curves. The reason is that the properties of the pairing are

used in an essential way. The fact that the pairing can be computed quickly

is vital for the present algorithm. This fact was also important in reducing

the discrete log problem to ļ¬nite ļ¬elds. However, note that the discrete log

Ā© 2008 by Taylor & Francis Group, LLC

185

SECTION 6.9 A CRYPTOSYSTEM BASED ON THE WEIL PAIRING

problem in the ļ¬nite ļ¬eld is still not trivial as long as the ļ¬nite ļ¬eld is large

enough.

For simplicity, weā™ll consider a speciļ¬c curve, namely the one discussed in

Section 6.2. Let E be deļ¬ned by y 2 = x3 + 1 over Fp , where p ā” 2 (mod 3).

Let Ļ ā Fp2 be a primitive third root of unity. Deļ¬ne a map

Ī² : E(Fp2 ) ā’ E(Fp2 ), (x, y) ā’ (Ļx, y), Ī²(ā) = ā.

Suppose P has order n. Then Ī²(P ) also has order n. Deļ¬ne the modiļ¬ed

Weil pairing

en (P1 , P2 ) = en (P1 , Ī²(P2 )),

Ė

where en is the usual Weil pairing and P1 , P2 ā E[n]. We showed in Lemma 6.1

that if 3 n and if P ā E(Fp ) has order exactly n, then en (P, P ) is a primitive

Ė

nth root of unity.

Since E is supersingular, by Proposition 4.33, E(Fp ) has order p + 1. Weā™ll

add the further assumption that p = 6 ā’ 1 for some prime . Then 6P has

order or 1 for each P ā E(Fp ).

In the system weā™ll describe, each user has a public key based on her or

his identity, such as an email address. A central trusted authority assigns

a corresponding private key to each user. In most public key systems, when

Alice wants to send a message to Bob, she looks up Bobā™s public key. However,

she needs some way of being sure that this key actually belongs to Bob, rather

than someone such as Eve who is masquerading as Bob. In the present system,

the authentication happens in the initial communication between Bob and the

trusted authority. After that, Bob is the only one who has the information

necessary to decrypt messages that are encrypted using his public identity.

A natural question is why RSA cannot be used to produce such a system.

For example, all users could share the same common modulus n, whose fac-

torization is known only to the trusted authority (TA). Bobā™s identity, call it

bobid, would be his encryption exponent. The TA would then compute Bobā™s

secret decryption exponent and communicate it to him. When Alice sends

Bob a message m, she encrypts it as mbobid (mod n). Bob then decrypts us-

ing the secret exponent provided by the TA. However, anyone such as Bob who

knows an encryption and decryption exponent can ļ¬nd the factorization of n

(using a variation of the method of Section 6.8), and thus read all messages

in the system. Therefore, the system would not protect secrets. If, instead,

a diļ¬erent n is used for each user, some type of authentication procedure is

needed for a communication in order to make sure that the n is the correct

one. This brings us back to the original problem.

The system described in the following gives the basic idea, but is not secure

against certain attacks. For ways to strengthen the system, see [15].

To set up the system, the trusted authority does the following:

1. Chooses a large prime p = 6 ā’ 1 as above.

in E(Fp ).

2. Chooses a point P of order

Ā© 2008 by Taylor & Francis Group, LLC

186 CHAPTER 6 ELLIPTIC CURVE CRYPTOGRAPHY

3. Chooses hash functions H1 and H2 . The function H1 takes a string of

bits of arbitrary length and outputs a point of order on E (see Exercise

6.8). The function H2 inputs an element of order in FĆ— and outputs

p2

a binary string of length n, where n is the length of the messages that

will be sent.

4. Chooses a secret random s ā FĆ— and computes Ppub = sP .

5. Makes p, H1 , H2 , n, P, Ppub public, while keeping s secret.

If a user with identity ID wants a private key, the trusted authority does the

following:

1. Computes QID = H1 (ID). This is a point on E.

2. Lets DID = sQID .

3. After verifying that ID is the identiļ¬cation for the user with whom he

is communicating, sends DID to this user.

If Alice wants to send a message M to Bob, she does the following:

1. Looks up Bobā™s identity, for example, ID =bob@computer.com (written

as a binary string) and computes QID = H1 (ID).

2. Chooses a random r ā FĆ— .

3. Computes gID = e (QID , Ppub ).

Ė

4. Lets the ciphertext be the pair

c = (rP, M ā• H2 (gID )),

r

where ā• denotes XOR (= bitwise addition mod 2).

Bob decrypts a ciphertext (u, v) as follows:

1. Uses his private key DID to compute hID = e (DID , u).

Ė

2. Computes m = v ā• H2 (hID ).

The decryption works because

e (DID , u) = e (sQID , rP ) = e (QID , P )sr = e (QID , Ppub )r = gID .

r

Ė Ė Ė Ė

Therefore,

m = v ā• H2 (Ė (DID , u)) = (M ā• H2 (gID )) ā• H2 (gID ) = M.

r r

e

Ā© 2008 by Taylor & Francis Group, LLC

187

EXERCISES

Exercises

6.1 Show that the map Ī² in Section 6.2 is an isomorphism (it is clearly

bijective; the main point is that it is a homomorphism).

6.2 (a) Suppose that the ElGamal signature scheme is used to produce

the valid signed message (m, R, s), as in Section 6.5. Let h be an

integer with gcd(h, N ) = 1. Assume gcd(f (R), N ) = 1. Let

s ā” sf (R )f (R)ā’1 hā’1 (mod N ),

R = hR,

m ā” mf (R )f (R)ā’1 (mod N ).

Show that (m , R , s ) is a valid signed message (however, it is un-

likely that m is a meaningful message, so this procedure does not

aļ¬ect the security of the system).

(b) Suppose a hash function is used, so the signed messages are of the

form (m, RH , sH ). Explain why this prevents the method of (a)

from working.

6.3 Use the notation of Section 6.5. Let u, v be two integers with gcd(v, N ) =

1 and let R = uA + vB. Let s ā” ā’v ā’1 f (R) (mod N ) and m ā” su

(mod N ).

(a) Show that (m, R, s) is a valid signed message for the ElGamal sig-

nature scheme. (However, it is unlikely that m is a meaningful

message.)

(b) Suppose a hash function is used, so the signed messages are of the

form (m, RH , sH ). Explain why this prevents the method of (a)

from working.

6.4 Let E be an elliptic curve over Fq and let N = #E(Fq ). Alice has a

message that she wants to sign. She represents the message as a point

M ā E(Fq ). Alice has a secret integer a and makes public points A and

B in E(Fq ) with B = aA, as in the ElGamal signature scheme. There

is a public function f : E(Fq ) ā’ Z/N Z. Alice performs the following

steps.

(a) She chooses a random integer k with gcd(k, N ) = 1.

(b) She computes R = M ā’ kA.

(c) She computes s ā” k ā’1 (1 ā’ f (R)a) (mod N ).

(d) The signed message is (M, R, s).

Bob veriļ¬es the signature as follows.

Ā© 2008 by Taylor & Francis Group, LLC

188 CHAPTER 6 ELLIPTIC CURVE CRYPTOGRAPHY

(a) He computes V1 = sR ā’ f (R)B and V2 = sM ā’ A.

(b) He declares the signature valid if V1 = V2 .

Show that if Alice performs the required steps correctly, then the ver-

iļ¬cation equation V1 = V2 holds. (This signature scheme is a variant

of one due to Nyberg and Rueppel (see [12]). An interesting feature is

that the message appears as an element of the group E(Fq ) rather than

as an integer.)

6.5 Let p, q be prime numbers and suppose you know the numbers m =

(p + 1)(q + 1) and n = pq. Show that p, q are the roots of the quadratic

equation

x2 ā’ (m ā’ n ā’ 1)x + n = 0

(so p, q can be found using the quadratic formula).

6.6 Let E be the elliptic curve y 2 = x3 + b mod p, where p ā” 2 (mod 3).

(a) Suppose E[n] ā E(Fp ) for some n ā” 0 (mod p). Show that n|p ā’ 1

and n2 |p + 1. Conclude that n ā¤ 2.

(b) Show that E[2] ā E(Fp ).

(c) Show that E(Fp ) is cyclic (of order p + 1).

6.7 Let p ā” 3 (mod 4) be a prime number. Suppose x ā” y 2 (mod p).

(a) Show that (y (p+1)/2 )2 ā” y 2 (mod p).

(b) Show that y (p+1)/2 ā” Ā±y (mod p).

(c) Show that x(p+1)/4 is a square root of x (mod p).

(d) Suppose z is not a square mod p. Using the fact that ā’1 is not a

square mod p, show that ā’z is a square mod p.

(e) Show that z (p+1)/4 is a square root of ā’z (mod p).

6.8 Let p = 6 ā’ 1 and E be as in Section 6.9. The hash function H1 in that

section inputs a string of bits of arbitrary length and outputs a point of

order on E. One way to do this is as follows.

(a) Choose a hash function H that outputs integers mod p. Input a

binary string B. Let the output of H be the y coordinate of a

point: y = H(B). Show that there is a unique x mod p such that

(x, y) lies on E.

(b) Let H1 (B) = 6(x, y). Show that H1 (B) is a point of order or 1

on E. Why is it very unlikely that H1 (B) has order 1?

Ā© 2008 by Taylor & Francis Group, LLC