. 18
( 36 .)


modulo a prime can be found, e.g. in [Menezes et al. (1996), Chap. 31.

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

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
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;
computes R = [k]G,P = [ICIDB= ( x , y ) ;
encrypts e = m x mod p ;
sends B the ciphertext ( R , e ) .

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
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
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

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

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).


Point P, integer m = ( m t m t - I . .. m1)2.
OUTPUT: Point Q = [m]P.

Q 0;
1. +

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

+ P;
IF m1 THEN Q +- Q
4. i =

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,
[i = 4 m4 = 0 : Q t [2]Q = [2]P;
[ i = 3 m3 = 1 : Q t [2lQ = [4]P, Q + Q P = [SIP;
[i = 2 m2 = 0 : Q t [2]Q= [lO]P;
[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
addition P = PI P where PI, P # 0 and PI # &P2 is computed by
2 2
Elliptic Curve Cryptosysterns 97

the formulas
k=-, Y2 - Y1
52 -21
˜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
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

- 2x1,
= k2
= k ( m - 23) - YI (mod P ) .

If P = 0 or y1 = 0 then P3 = 0.
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

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
( 36 .)