Elliptic Curve Cryptography - Elliptic Curves: Number Theory and Cryptography - page 173

(mod N ), so m − A m A =1+ kN for some k . The group E ( F q ) has order N ,
so Lagrange's theorem implies that NR = ∞ for any R ∈ E ( F q ). Therefore,

m − 1
A

m A R =(1+ kN ) R = R + k∞ = R.

Applying this to R = m B M , we find that

M 3 = m − 1 m B m A M = m B M.

A

Similarly, m − 1 and m B cancel, so

B

M 4 = m − 1 M 3 = m − 1

m B M = M.

B B

The eavesdropper Eve knows E ( F q )andthepoints m A M , m B m A M ,and
m B M .Let a = m − 1

A ,b = m − B ,P = m A m B M . Then we see that Eve knows
P, bP, aP and wants to find abP . This is the Di e-Hellman problem (see

Section 6.2).
The above procedure works in any finite 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 = x 3 + Ax + B over F p . The case of an arbitrary finite field F q is similar. Let
m be a message, expressed as a number 0 ≤ m<p/ 100. Let x j = 100 m + j
for 0 ≤ j< 100. For j =0 , 1 , 2 ,..., 99, compute s j = x j + Ax j + B .If
s ( p− 1) / 2

1(mod p ), then s j is a square mod p , in which case we do not
need to try any more values of j .When p

≡

j

3(mod4),asquarerootof
s j is then given by y j ≡ s ( p +1) / j (mod p ) (see Exercise 6.7). When p ≡ 1
(mod 4), a square root of s j can also be computed, but the procedure is more
complicated (see [25]). We obtain a point ( x j ,y j )on E . To recover m from
( x j ,y j ), simply compute [ x j / 100] (= the greatest integer less than or equal
to x j / 100). Since s j is essentially a random element of F p , which is cyclic of
even order, the probability is approximately 1/2 that s j is a square. So the
probability of not being able to find 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 finite field F q such that
the discrete log problem is hard for E ( F q ). 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 finite field