Page 316 - Hardware Implementation of Finite-Field Arithmetic

296 Cha pte r T e n

Then choose
2
Z = X Z 2 (10.34)
3 1 1
so that
X = x Z = X + bZ (10.35)
4
4
3 3 3 1 1
2
2
3
Y = y Z = (X /Z ) Z + (X Z + X Y Z )X + X Z
2
3 3 3 1 1 3 1 1 1 1 1 3 3 3
4
= X Z + (X Z + X Y Z )X + X Z
3
1 3 1 1 1 1 1 3 3 3
4
3
4
3
= (X + X )Z + (X Z + X Y Z )X = bZ Z + (X Z + X Y Z )X
1 3 3 1 1 1 1 1 3 1 3 1 1 1 1 1 3
2
3
2
2
As (X , Y , Z ) satisfies Eq. (10.33) X Z + X Y Z = Y + aX Z + bZ 4
1 1 1 1 1 1 1 1 1 1 1 1
4
Y = bZ Z + (Y + aZ + bZ )X (10.36)
2
4
3 1 3 1 3 1 3
Thus, the point-doubling operation is executed with formulas in
Eqs. (10.34), (10.35), and (10.36). The corresponding computation prim-
itives are finite-field addition, multiplication, and squaring.
The point-adding formulas are somewhat more complex. If Z = 1
2
the final result is the following [HMV04]:
2
X = A + D + E Y = (E + Z )F + G Z = C 2 (10.37)
3 3 3 3
where
2
2
A = Y Z + Y B = X Z + X C = Z B D = B (C + aZ )
2
2 1 1 2 1 1 1 1
E = AC F = X + X Z G = (X + Y )Z 2
3 2 3 2 2 3
Once again the corresponding computation primitives are finite-
field addition, multiplication, and squaring.
The negation is computed as follows (Z ≠ 0):
− (X, Y, Z) = (X, XZ + Y, Z) (10.38)
Actually, the corresponding affine points are
2
− (X/Z, Y/Z ) and (X/Z, (XZ + Y)/Z ) = (X/Z, X/Z + Y/Z )
2
2
=− (X/Z, Y/Z )
2
[according to Eq. (10.15)].
To summarize, the elliptic curve operations are executed as fol-
lows: Substitute every curve point (x, y) by the projective point (x, y, 1),
substitute ∞ by (1, 0, 0), and execute all the necessary operations
within the projective domain. If the result of a sequence of operations