Page 315 - Hardware Implementation of Finite-Field Arithmetic

An Example of Application—Elliptic Curve Cryptography 295

As a matter of fact, the preceding relation defines an equivalence
relation over the set of elements of L whose z-coordinate is nonzero:
3
two elements (X , Y , Z ) and (X , Y , Z ) are equivalent if they are
1 1 1 2 2 2
mapped to the same element of L , that is,
2
d
d
c
X /Z = X /Z and Y /Z = Y /Z (10.31)
c
1 1 2 2 1 1 2 2
Each equivalence class is called a projective point, while the
2
elements (x, y) of L are called affine points.
Consider now an elliptic curve, for example, a nonsupersingular
m
curve over L = GF(2 ) defined by Eq. (10.4), and assume that c = 1 and
d = 2 (López-Dahab projective coordinates, [LD99]). Substituting x by X/Z
and y by Y/Z in Eq. (10.4) the following equation is obtained:
2
3
3
2
2
3
4
Y /Z + XY/Z = X /Z + aX /Z + b (10.32)
2
equivalent to
2
2
2
Y + XYZ = X Z + aX Z + bZ (10.33)
3
4
It is the projective form of Eq. (10.4), and for every solution (x, y) of
Eq. (10.4), there corresponds an equivalence class of solutions (X, Y, Z)
of Eq. (10.33).
All the elements of the form (X, 0, 0) are also solutions of Eq. (10.33).
They are associated to the point at infinity ∞ in the two-dimension
domain.
The basic idea for avoiding divisions is to define the point-addition
and point-doubling operations using the projective coordinates.
Assume that the result of an operation involving two points (x , y )
1 1
and (x , y ) is (x , y ). In affine coordinates x and y are some of the
2 2 3 3 3 3
computed formulas presented in Sec. 10.3. Within those formulas
2
2
substitute x , y , x , y with X /Z, Y /Z , X /Z, Y /Z , so that x and
1 1 2 2 1 1 2 2 3
y are now expressed under the form x = N /D and y = N /D where
3 3 x x 3 y y
the numerators and denominators are functions of X , Y , Z , X , Y ,
1 1 1 2 2
and Z . The same point can be represented in the projective domain
2
2
under the form ((N /D )Z , (N /D )Z , Z ) where Z can be any non-
x x 3 y y 3 3 3
zero element. Then choose for Z an element so that D divides Z and
3 x 3
2
D divides Z .
y 3
As an example compute the doubling formulas. According to
Eq. (10.17)
λ= x + y /x = X /Z + (Y /Z )/(X /Z ) = (X Z + X Y Z )/( X Z )
2
2
3
2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
4
2
2
4
x = x + b/x = (X /Z ) + b/(X /Z ) = (X + bZ )/( X Z )
2
2
2
2
3 1 1 1 1 1 1 1 1 1 1
2
3
4
2 2
2
4
2
y = x + λx + x = (X /Z ) + (X Z + X Y Z )(X + bZ )/( X Z )
3 1 3 3 1 1 1 1 1 1 1 1 1 1 1
2
4
4
2
+ (X + bZ )/( X Z )
1 1 1 1