Page 312 - Hardware Implementation of Finite-Field Arithmetic

292 Cha pte r T e n

that is,

(2,1) + (0,0) = (2,4)
2. Compute (2,4) − (2,1) = (2,4) + (2, − 1) = (2,4) + (2,4):

2
2
2
2
x = [(3 · 2 − 1)/2 · 4] − 2 · 2 = 2 − 4 = 0, y = [(3 · 2 − 1)/2 · 4](2 − 0) − 4
3 3
= 2 · 2 − 4 = 0,
that is,
(2,4) − (2,1) = (0,0)

10.4 Point Multiplication

10.4.1 Definition
Point multiplication is the basic operation of elliptic curve cryptography:
given a natural k and a point P of E(L),

kP = P + P + . . . + P (k times) ∀k > 0 and 0P = ∞ (10.22)

Assume that the number of points #E(L) of the chosen elliptic
curve can be factored under the form

#E(L) = nh (10.23)

where n is a prime and h (the cofactor) is small, so that n ≅ q [see
Eq. (10.9)]. Because the order of an element divides the order of the
group, the order of P is at most n, and the values of k should be limited
to the set {0, 1, . . . , n − 1}.

Example 10.2 Consider the same curve as in Example 10.1 and
compute k(2,4) for k in {1,2, . . . , 7}.

1(2,4) = (2,4)
2(2,4) = (2,4) + (2,4) = (0,0)
3(2,4) = (0,0) + (2,4) =− (0,0) – ( 2,1) =− ((0,0) + (2,1))
=− (2,4) = (2,1)
4(2,4) = 2(0,0) =∞

5(2,4) = (2,4)
6(2,4) = (0,0)
7(2,4) = (2,1)