<<

. 19
( 36 .)



>>

tor and denominator. The following transformation of variables is the most
beneficial:
Y
X
x+-, y+-. (6.16)
23
22

A point on the curve is represented by a triplet ( X ,Y, ) and one speaks of
2
transition to weighted projective representation (for simplicity, we shall omit
the word “weighted”). Conversion from affine to projective coordinates is
quite simple:

b , Y , 1) (6.17)
(Xc,Y) *
+



After that all computations are carried out in projective coordinates (with-
out computing inversions). The reverse conversion from projective to &ne
coordinates is done as follows:

(6.18)
( X ,y, 2 ) -4 ( X / Z 2 ,Y / Z 3 )
1



+
and costs 11 4M (one computation of Z-l, two multiplications for ob-
taining 2-2 and Z-3 and, finally, two multiplications X 2 - 2 and Y Z W 3 ) .
Ellaptic Cume Cryptosystems 99


Derive the formulas for point addition in projective representation. First
in Eq. (6.14) for 5 3 , transform variables according to (6.16). After reducing
to a common denominator and cancelling we obtain




From this we find the expressions for X3 and Z3 taking, respectively, the
numerator and the square root from denominator of the right side of (6.19).
To obtain an expression for Y3, resort to a trick that allows to save one
+ +
multiplication. Notice that P I P2 = Pz Pl and hence


Y2 - Y1
/ 2.
- Y2)
Y3 = ( ( E l - 53)- - y 1 + (x2 - x3)=
5 2 - x1 -21
52



Transform variables according to (6.16) and, instead of Z3, use its represen-
tation from (6.19). After reducing to a common denominator, cancelling,
and reducing the similar terms we obtain




Based on Eqs. (6.19) and (6.20), write Algorithm 6.2.
As it follows from the algorithm™s description, the cost of addition in
projective coordinates equals 16M. We do not count simple operations of
addition, subtraction, as well as multiplication and division by 2 (to explain
how to compute v/2 mod p notice that if v is even then v/2 mod p = v/2
+
+
(right shift per 1 bit); if v is odd then v/2 mod p = (v p)/2 mod p , v p
+
even, so v/2 mod p = (v p)/2).
If one of the points, say, Pz is given in afine coordinates, i.e. 2 2 = 1
then the cost of addition decreases to 11M. It is called mixed addition.
Algorithm 6.1 is constructed so that mixed additions can always be used,
i.e. the cost of computations at Line 4 equals 11M.
IT Practitioners
100 Basics of Contemporary Cryptography for


Algorithm 6.2 ADDITION IN PROJECTIVE REPRESENTATION.

INPUT: Pi = ( X i , Y i l z i ) , P2 = (Xa,Y2,22),
# #
0 Pl
Pl,P2 *p2
1

+
P = (X3, Y3,23) = Pi
OUTPUT: P
2
3
(all computations are modulo p )

2M
2M

2M
2M



2M
3M

3M
16M




+
Example 6.3 Compute the sum (5,l) (4,6) in projective coordinates
for the curve of Example 6.1 (all operations are modulo 7).
101
Elliptic C u r v e C r y p t o s y s t e m s


To check the result convert point to affine representation. For that
P
3
purpose compute

6-1 =6, 6-2 =6.6 =1, 6-3 = 1 . 6 = 6 .
We finally obtain

P3 = (2 * 1 , 2 . 6) = (2,5)

which coincides with the result of Example 6.1.
Note that condition PI, P # 0 is equivalent to 2 1 ˜ 2 2 0 and condition
#
2
P # 4 9 2 equivalent to X1 # X2.
I
To derive the formulas for doubling a point in projective representation
substitute (6.16) in (6.15):

(6.21)




which leads to the following Algorithm 6.3.

Algorithm 6.3 DOUBLING IN PROJECTIVE REPRESENTATION.

Pi = (Xi, Y1, Z,), Pi # 0
INPUT:
OUTPUT: P3 = (X3,Y3,23) = [2]P1

+ a214
A1 = 3 ,
xz 4M
2M
=4X1Y?
1M
2 3 = 2Y121
x = A? - 2x2 1M
3
1M
A3 = SY?
1M
Y = X l ( X 2 - X3) - A3
3 ˜




10M



We can see that the cost of doubling in projective coordinates equals
+
10M. But if the curve parameter a = -3 then X1 = 3(X1 - 2f)(X1 2,”)
and the cost of doubling decreases to 8M.
Notice once again that in all the above algorithms computations are
performed modulo p . Therefore much depends on the efficiency of modular
Basics of Contemporary Cryptography for IT Practitioners
102


arithmetic. For randomly selected moduli, the best to the date approach is
the use of Montgomery representation for integers [Montgomery (1985)], see
also [Menezes et al. (1996)]. In Montgomery representation, multiplication
modulo p is equivalent to two ordinary multiplications.


Counting Points on Elliptic Curve
6.6

In this section, we consider the algorithm by Ren6 Schoof suggested in
[Schoof (1995)] for finding #Ep(a, i.e. the number of points whose coor-
b),
dinates satisfy the curve equation (6.10) and are positive integers less than
p (plus point at infinity 0). Schoof's algorithm was the first polynomial-
time algorithm for counting points, its complexity is estimated as O(log6p )
modular operations. This algorithm forms a basis for all modern methods
used for random curves.
We begin with the theorem proved by Helmut Hasse in 1933 (proofs for
all theorems may be found in [Silverman (1986)I).
Theorem 6.1 (Hasse) #Ep(a, satisfies the inequalities
b)

+ 1 - 2JiT I # E p ( a , b ) I P + 1 + 2 4 5 .
P
It is useful to represent #Ep(a,b) the form
in

#Ep(a,b) = p + l - t . (6.23)

Parameter t in (6.23) can be zero, positive or negative integer and is
called the trace of Frobenius for Ep(a,b). If we could find t we would be
able to obtain the number of points on curve by Eq. (6.23). The trace of
F'robenius is remarkably related to the modulus p .
Theorem 6.2 For all complex numbers x and y satisfying the curue equa-
tion (6.10) the equality holds

(6.24)
(addition in the formula means composition of points).
Now our task is to solve Eq. (6.24) with respect to the unknown t.
Notice that the point composition of the form Q = [m]P can be expressed
through the coordinates of point P. For instance,
Elliptic Curve Cryptosystems 103


x4 - 2ax2 - 8bx + a 2
( 7
4y2
=
+ 20bx3 - 5a2x2 - 4abx - 8b2 - a3
+
x6 5ax4
8Y3
+
The point [ 3 ] ( xy ) can be obtained as [ 2 ] ( 2y ) ( x ,y) by substituting the
,
,
obtained coordinates for the point [ 2 ] ( x , y )in Eqs. (6.5), (6.7), (6.8) (the
interested reader may do that). The process of obtaining expressions for
subsequent points seems much too complicated, nevertheless, it can be de-
scribed by the following simple recurrence scheme:

= 0,
$0
$1 = 1,
$2 = 2Y 1
+ +
$3 = 3x4 6ax2 12bx - a 2 ,
+
20bx3 - 5a2x2 - 4abx - 8b2 - a 3 ) ,
$4 = 4y(x6 f 5ax4

m 2 2,
- $rn-I1cI$+1,
$2m+1= $m+2$$
>2.
$m-2$˜&+1)$m/2˜, m
= ($m+2$&-1-
$2m

For m 2 2 and P = ( x ,y )



<<

. 19
( 36 .)



>>