Chapter 6
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