Page 319 - Hardware Implementation of Finite-Field Arithmetic

An Example of Application—Elliptic Curve Cryptography 299

so that
X = x Z + X Z (X Z + X Z ) + (X Z ) 2
A + B P A + B B A A B B A B A
= x Z + X X Z Z (10.48)
P A + B A B A B
According to Eq. (10.45)

2
2
x = (X /Z ) + b(Z /X ) = (X + b Z )/(X Z )
2
4
2
4
A + A A A A A A A A A
Let
Z = X Z (10.49)
2
2
A+A A A
so that
4
X = x Z = X + b Z (10.50)
4
A + A A + A A + A A A
Finally, according to Eq. (10.46),
y = (x + X /Z )[(X + x Z )(X + x Z )
A P A A A P A B P B
− 1
2
+ (x + y )Z Z ](x Z Z ) + y (10.51)
P P A B P A B P
10.4.3.4 Frobenius Map
The point-doubling operation can be avoided in the case of the two
m
following Koblitz curves over GF(2 ) ([Sol00], [HMV04]):
E : y + xy = x + 1 (10.52)
3
2
0
2
3
2
E : y + xy = x + x + 1 (10.53)
1
m
m
For that define the Frobenius map τ from E (GF(2 )) to E (GF(2 )),
c c
with c = 0 or 1:
2
2
τ(∞) = (∞) τ(x, y) = (x , y ) (10.54)
It can be demonstrated that
2
2P = − τ (P) + μτ(P)
(10.55)
with μ = 1 if c = 1 and μ = − 1 if c = 0
Thus the point-doubling operation amounts to squaring opera-
2
m
tions in GF(2 ) for computing τ(P) and τ (P) and a point-addition.
In fact a generalized version of Eq. (10.55) can be defined. Given
two integers a and b, define an application α = a + bτ from E (GF(2 ))
m
c
m
to E (GF(2 )):
c
α(P) = aP + bτ(P) (10.56)