Page 317 - Hardware Implementation of Finite-Field Arithmetic

An Example of Application—Elliptic Curve Cryptography 297

2
is (X, Y, Z) with Z ≠ 0, the corresponding curve point is (X/Z, Y/Z ),
and if Z = 0 the result is ∞. Thus, the only finite field divisions are
those corresponding to the final projective-to-affine decoding.
If the point-multiplication is computed with Algorithm 10.2, the
second point-addition operand is always P, so that its initial projective
representation (x , y , 1) is not modified during the algorithm
P P
execution. This justifies the fact that the point-addition formulas
[Eq. (10.37)] have been defined with Z = 1. This is an example of
2
mixed coordinate representation: Q is represented in projective
coordinates, that is, under the form (X , Y , Z ), while P is represented
Q Q Q
in affine coordinates under the form (x , y ).
P P
10.4.3.3 Montgomery Algorithm
+
Assume again that k = k 2 t − 1 + k 2 t − 2 . . . + k 2 + k 2 , and define
0
1
t − 1 t − 2 1 0
the partial sums
s = 0
0
s = k 2 0
1 t − 1
1
s = k 2 + k 2 0 (10.39)
2 t − 1 t − 2
. . .
+
0
1
s = k 2 t − 1 + k 2 t − 2 . . . + k 2 + k 2 = k
t t − 1 t − 2 1 0
Thus,
s = 2s + k ∀j = 1, 2, . . . , t (10.40)
j j − 1 t - j
The algorithm consists of computing at each step s P and (s + 1)P
j j
in function of s P and (s + 1)P ([HMV04]). If k = 0 then
j − 1 j − 1 t - j
s P = 2(s P), (s + 1)P = (2s + 1)P = s P + (s + 1)P, (10.41)

j j − 1 j j − 1 j − 1 j − 1
and if k = 1 then
t - j
s P = (2s + 1)P = s P + (s + 1)P
j j − 1 j − 1 j − 1
(10.42)
(s + 1)P = (2s + 2)P = 2(s + 1)P
j j − 1 j − 1
Initially define
s P = ∞ and (s + 1)P =P (10.43)
0 0
The corresponding formal algorithm follows:

Algorithm 10.4—Montgomery point-multiplication algorithm
A := point_at_infinity; B := P;
for j in 1 .. t loop
if k(t-j) = 0 then A := 2A; B := A + B;
else A := A + B; B := 2B;