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 )