ñòð. 18 |

6.4 Constructing Cryptosystems

Any cryptosystem based on discrete logarithms can be easily extended to

elliptic curves. The basic principle is to replace the operation y = g" mod p

by Y = [z]Gmod p (the indication of the modulus here is not generally ac-

cepted but, in fact, all computations are carried out modulo p ) . One should,

however, remember that in case of elliptic curve with cardinality of working

subset q, the values of IC effectively lie in the interval 0 < IC < q . This is

because [q]G 0 and hence the integer factors in point multiplication are

=

reduced modulo q. Another difference is that y is a number but Y is a point

and it is usually required to convert a point into an integer. The simplest

way to do that is to use the x-coordinate of the point.

It is also possible to construct an analogue of RSA on elliptic curves. In

this case the curve is defined modulo a composite N . But we do not gain

any advantage here since the length of the modulus remains the same in

order to make its factorisation intractable.

Basics of Contemporary Cryptography for IT Practitioners

94

We demonstrate the technique of using elliptic curves by the examples

of the ElGamal cipher and DSA signature.

6 4 1 Elliptic Curve ElGamal Encryption

..

For the community of users of a network, an elliptic curve Ep(a, is chosen

b)

and a point G thereon such that G , [2]G,[3]G,. . . , [q]Gare different points

and [q]G= 0 for some prime q.

Every user U selects a number cu, 0 < cu < q to be his/her private

key and computes the point Du = [cu)Gwhich is the corresponding public

key. The common parameters and public keys are submitted to all users.

Suppose user A wants to send a message to user B. Assume that the

message is represented as a number m < p . A does the following:

selects a random integer k , 0 < k < q;

1

computes R = [k]G,P = [ICIDB= ( x , y ) ;

2

encrypts e = m x mod p ;

3

sends B the ciphertext ( R , e ) .

4

User B , upon receiving ( R ,e ) ,

5 computes Q = [cBIR= ( 2 ,y);

6 decrypts m' = ex-' mod p .

Let's give a justification of the protocol. Using the definitions of point

Q at Step 5 and point R at Step 2 we can write

The public key of user B , by definition, is DB = [cBIG. So we can see that

Q = [ k ] D g ,i.e. Q is the same point as P at Step 2 . Hence the coordinate

x at Step 3 equals that at Step 6 . Therefore m' = m.

The coordinate x of point Q remains secret for the adversary because

she does not know the secret number k . The adversary may try to recover

k from R but to do that she must solve the elliptic curve discrete logarithm

problem which is believed t o be impossible.

In the most likely use of the presented protocol, the message m will be

the secret key for some block or stream cipher. In this case it makes sense

to choose the curve parameters so that logq be about twice the length of

the cipher key.

Ellaptic Curve Cryptosystems 95

6.4.2 Elliptic Curve Digital Signature Algorithm

The algorithm presented here is quite analogous to digital signature algo-

rithm (DSA) described in Sec. 4.3 but exponentiations are replaced by point

multiplications on the curve. As in the preceding subsection, for the com-

munity of users, an elliptic curve Ep(a, is chosen and a point G thereon

b)

such that G, [2]G, [3]G, . . . , [q]G are different points and [q]G = 0 for

some prime q (the bitlength of p and q is 160 bits).

Every user U selects a number xu,0 < xu < q to be his/her private

key and computes the point Yu = [xu]G which is the corresponding public

key. The common parameters and public keys are submitted to all users.

To sign a message m user A does the following:

1 computes hash function h = h ( f i ) ;

2 selects a random integer k, 0 < k < q;

3 computes P = [k]G= (x,y);

4 computes T = 2 mod q (if T = 0, revert to Step 2);

+

5 computes s = k - l ( h T X A ) mod q (if s = 0, revert to Step 2);

6 signs on the message with the pair of numbers (T, s).

For verification of the signed message (m;s), any user who knows the

T,

public key YAdoes the following:

7 computes h = h(m);

8 verifies that 0 < r, s < q;

9 computes u1 = h . s-l mod q and uz = r . s-l mod q;

10 computes the composition of points P = [ul]G [uZ]YA= (x,

4- y);

11 verifies that P # 0 and x mod q = r .

The user rejects the signature if at least one test at Step 8 or 11 fails.

Otherwise, the user accepts the signature as authentic.

The proof of correctness for this protocol can be done in the same way

as in Sec. 4.3.

Efficient Implementation of Operations

6.5

In this section, we consider the main approaches to making efficient com-

putations on elliptic curves. As we have already discussed, the point mul-

tiplication by m, i.e. computing [m]Pwhere m is a large integer and P

is a point on the curve, can be performed using the same methods as for

exponentiation (upon replacement of ordinary modular multiplication by

Basics of Contemporary Cryptography for IT Practitioners

96

point addition). Here, for the sake of concreteness, we describe explicitly

one of the simplest methods - left-to-right point multiplication (cf. Algo-

rithm 2.4). There are other more efficient methods for exponentiation which

may be successfully applied to elliptic curve point multiplication. But the

gain is usually not so great (about 25%) and these methods g o beyond the

scope of our book (see their description in, e.g. [Menezes et al. (1996);

Blake et al. (1999)l).

Algorithm 6.1 POINT MULTIPLICATION (FROM LEFT TO RIGHT).

Point P, integer m = ( m t m t - I . .. m1)2.

INPUT:

OUTPUT: Point Q = [m]P.

Q 0;

1. +

FOR i = t , t - 1,.. . , l DO

2.

PIQ,

Q

3. +

+ P;

IF m1 THEN Q +- Q

4. i =

RETURN Q.

5.

This algorithm requires not more than t point additions and t point

doublings (on average, t doublings and t/2 additions).

Example 6.2 Letâ€™s demonstrate the work of the algorithm by computa-

tion of [21]P.Here 21 = (10101)2 = mlm2m3m4m5, t = 5 . We show what

happens on each iteration.

Q +- & + P = P;

[i = 5 m5 = 1 : Q t 0,

1

[i = 4 m4 = 0 : Q t [2]Q = [2]P;

1

+

[ i = 3 m3 = 1 : Q t [2lQ = [4]P, Q + Q P = [SIP;

1

[i = 2 m2 = 0 : Q t [2]Q= [lO]P;

1

[2]Q = [2O]P, Q + Q + P = [ZIP.

[i=lml=l]:Q +

For ease of exposition, reproduce here the formulas for point addition

and doubling derived in Sec. 6.2. Denote the points participating in these

operations by P = ( q , y l ) , P2 = (zz,y2), and P = ( 2 3 , ˜ ˜The point

).

3

I

+

addition P = PI P where PI, P # 0 and PI # &P2 is computed by

2 2

3

Elliptic Curve Cryptosysterns 97

the formulas

k=-, Y2 - Y1

52 -21

(6.14)

˜3 = k2 - X I - ˜ 2 ,

(mod P ) .

- YI

y3 = 23)

If PI = 0 then P3 = 0 + P 2 = P 2 , and similarly with P = 0. If PI = -P2

2

Finally, if PI = P 2 then we must perform doubling.

then P3 = 0.

The point doubling P 3 = [2]Plwhere PI # 0 and y1 # 0 is computed

by the formulas

k=- 32: +a

â€™

2Yl

(6.15)

- 2x1,

= k2

x3

= k ( m - 23) - YI (mod P ) .

˜3

If P = 0 or y1 = 0 then P3 = 0.

I

Computations by (6.14) and (6.15) have been considered in Example 6.1.

One speaks that in computations by (6.14) and (6.15) the u f i n e repre-

sentation of points is used, i.e. a point P is represented by its two coordi-

nates P = (IC, y ) . Point at infinity 0 has no such representation because

its coordinates must be 00. But recall that it plays the role of zero in point

operations. So, technically, in Algorithm 6.1 0 is simply a flag indicat-

ing that one should omit the operations Q t [2]Quntil the first addition

+

Q c Q P which is performed as an assignment Q + P.

The formulas (6.14) and (6.15) are used to perform computations at

Lines 3 and 4 of Algorithm 6.1 with obvious substitutions. Notice that if

computations on the curve are carried out in a subset of points of cardinality

q and q is prime (as we always assume) and factor m lies in the interval

0 < m < q then the conditions for point addition formulas (i.e. P I ,Pz # 0

and PI # *P2) and point doubling formulas (PI # 0 and y 1 # 0) are

automatically fulfilled at Lines 3 and 4 of Algorithm 6.1 and need not be

checked (provided the first doublings omitted and the first addition replaced

by assignment, as discussed above).

Now letâ€™s consider some issues of computational efficiency of point oper-

ations. Denote by M and I , respectively, the cost (time) of multiplication

and inversion modulo p. Then it follows from (6.14) and (6.15) that under

+

the affine point representation, the cost of point addition equals 11 3M

+

and the cost of doubling is 11 4 M (operations of addition with and mul-

Basics of Contemporary Cryptography for IT Practitioners

98

tiplication by small integers are of no noticeable effect to the cost).

The relation between the costs of multiplication and inversion may differ

depending on implementation, but I is always greater than M . If multipli-

cation is implemented by summations and shifts, it will be but a little faster

than inversion (by a factor of 2-3). In this case the use of affine representa-

tion is appropriate. But if the processor that performs computations is sup-

plied with embedded parallel multiplier (as, e.g. Pentiurn@) then inversion

may be significantly slower than multiplication. We can roughly estimate

the costs of corresponding computations. If t is the bitlength of numbers

then multiplication requires at most on the order of (t/32)2 = t2/1024 ma-

chine operations (the word size is 32 bits). On the other hand, the number

of iterations in the extended Euclidean algorithm which computes inversion,

is proportional to t by its nature. Even if we manage on each iteration to

implement linear in t computations with 32-bit numbers (which is possi-

ble) then we obtain the total complexity on the order of t(t/32) = t2/32

machine operations, i.e. one inversion will correspond to 32 multiplications.

In reality, each iteration of Euclidean algorithm involves several operations

and multiplication can be done with faster methods, so I > 32M.

Consider another approach to implementing point operations. We can

get rid of inversions at each step of Algorithm 6.1 if operating with coordi-

nates as rational numbers, making computations separately with numera-

ñòð. 18 |