<<

. 17
( 36 .)



>>

(6.7)
23=k -51-˜2.

Substitute the expression for 2 3 into the line equation (6.6) and find the
+
y-coordinate of point R', yi = y1 k(x3 - XI), and by changing the sign,
we obtain

- Y1. (6.8)
Y3 = &l - z3)

So we have found the coordinates of the point of interest R.
Consider now the case when P = Q and resulting point R = [2]P
(Fig. 6.5). By differentiating both sides of (6.1) with respect to X , we
obtain
2YY' = 3x2 a .
+

The angular coefficient of the tangent line equals the value of derivative in
point P,



Further argumentation is analogous to the former case and the coordinates
of point R are determined by the same formulas (6.7) and (6.8). Notice
that if the y-coordinate of point P is zero then the tangent line passes in
parallel to the vertical axis and [2]P= 0.
By using the derived formulas for point composition and accepted con-
ventions as to point at infinity one may verify the following properties of
points on elliptic curve:
+ +
(1) P Q = Q P for all points P, Q E E ;
++
++
(2) P (Q S ) = ( P Q) S for all points P, Q, S E E ;
+
(3) there exists a null element 0 (point at infinity) such that P 0 =
+
0 P = P for all P E E ;
(4) for every point P E E there exists an opposite point -P E E such that
P+(-P)=0.
The listed properties of points match the properties of integer numbers
under the summation operation. Therefore point composition is often called
P
point addition and operation [2] point doubling.
Elliptic Curve Cryptosystems 89


The analogy with the integers being continued, it is convenient to in-
troduce the following notation. For integer m

[m]P=P+P+...+P



-
'-
m
[O]P 0 ,
=
[-m]P= -(P + P + . . . + P )
m


Now we are ready to take the first step toward the cryptographic use
of elliptic curves. We can see that computation of point composition (see
Eqs. (6.5), (6.9), (6.7), and (6.8)) involves only the operations of addition,
subtraction, multiplication, and division of numbers. It means that all
the above equalities will hold if we operate with integer numbers modulo
a prime p . In this case, addition and multiplication are done modulo p ,
+
the difference u - u is calculated as u ( p - 21) mod p , and division 21/21 is
performed by multiplying u by u ' modp (the primality of the modulus
-
guarantees that for any positive integer u < p there exists a number u ' -
such that u21-l mod p = 1).
As a result, we obtain a curve

E: Y2=X3+aX+b (modp). (6.10)

In Eq. (6.10), variables X, Y and coefficients a , b take on integer values
and all computations are carried out modulo p . In accordance with (6.4),
coefficients a , b are subject to the constraint

+ 27b') # 0. (6.11)
(4a3 mod p

The set Ep(a,b) consists of all points (z,y), 0 5 z,y < p , satisfying
Eq. (6.10) and the point at infinity 0 . Denote the number of points in
E,(a,b) by #E,(a,b). This quantity is of great importance for crypto-
graphic applications of elliptic curves.

Example 6.1 Consider the curve

Y 2= X 3 + 2X +6
E7(2,6) : (mod 7 ) . (6.12)

Check condition (6.11):

+ 27.6' +6 . 1 =3 # 0 (mod 7 ) .
=4.1
4.23
Basics of Contemporary Cryptography for IT Practitioners
90


So this curve is non-singular. Let™s find a (random) point in E7(2, Let
6).
2 = 5. Then




and y = 1 (mod 7) or y = -1 = 6 (mod 7). We have found two points:
(5,1) and (5,6). Let™s find more points by computing compositions. First
find [2](5,1). Using (6.9), (6.7), and (6.8), we compute
0
3.52+2
=-=O (mod 7 ) ,
k=
2
2.1
23=0-2.5=4 (mod7),
y3=0.(5-4)-1=6 (mod7).

We obtain [2](5,1) = (4,6) (one can verify that the point obtained belongs
to the curve by substituting its coordinates in Eq. (6.12)). Find a point
+
[3](5,1) = (5,l) (4,6). Using (6.5), (6.7), and (6.8), we compute

k = - -6-- 1 - 5 - 5 . 6 = 2
- (mod7),
4- 5 6

= 2™ - 5 - 4 = 2
23 (mod 7 ) ,
y3 = 2 . (5 - 2) - 1 = 2 . 3 - 1 = 5 (mod 7 ) .

We obtain [3](5,1) = (2,5). So we have found four points. For crypto-
graphic use of the curve we must know the total number of points in the
set E7(2, We shall find the answer in Sec. 6.6.
6).

Some words about the properties of the set of points E,(a,b): It is
obvious that this set is finite since it consists of only points with integer
coordinates 0 5 2 , y < p . There exists a direct analogy between Ep(a, b)
and the set of integer powers reduced modulo p . Thus Ep(a,b) has a gen-
erator, i.e. such a point G that the sequence G, [2]G, [3]G, . . . , [n]G, where
n = #E,(a,b), contains al! points from Ep(a,b),[n]G= 0 (compare this
to the similar property of generator g in Sec. 2.2). The number of points
on elliptic curve upon a proper choice of parameters p , a , and b, can be a
prime, #E,(a,b) = q . In this case any point (except 0 ) is a generator of
the whole set of points. Such a curve is beneficial in many respects and
can always be found for acceptable time. If by some reasons such a curve
cannot be found and #Ep(a,b ) = hq where q is again prime then a subset
of Ep(a,b ) exists which contains q points with a generator to be any point
Elliptic Curve Cryptosystems 91


G # 0 such that [q]G= 0. In the sequel, without lost of generality, we
shall assume that we work with such a subset of cardinality q (and when
selecting the curve parameters we shall strive to obtain q = #E,(a, b ) ) .
The main cryptographic operation on elliptic curve is point multiplica-
tion,i.e. computation

(6.13)


This operation may be performed quite efficiently with not more than
2logm point compositions. The methods of its implementation are com-
pletely the same as of modular exponentiation. For example, t o find the
point Q = [21]P compute [2]P, [4]P, [8]P,[16]P, each time doubling the
+ +
preceding point, and sum up P [4]P [16]P = Q (in total, 4 point dou-
blings and 2 point additions).
The inverse problem which is traditionally called elliptic curve discrete
logarithm problem if formulated as follows. Given points P and Q find
an integer m such that [m]P = Q. This problem is difficult. If the curve
parameters are carefully chosen (as described in the next section) then the
best algorithms known to date are analogues of baby-step giant-step algo-
rithm (Sec. 3.2) and require the number of curve operations proportional
to 4 where q is the cardinality of the set of points generated by Q. All
computations on the curve are carried out modulo p , i.e. with numbers
of length t PZ logp bit. For cryptographic applications, logq M logp so
4 M 2 t / 2 which means exponential growth of complexity with the length
of numbers increasing.


Choosing Curve Parameters
6.3

In this section, we consider the main recommendations as to the choice of
the elliptic curve parameters, namely, coefficients a, b and modulus p, in
order to obtain a curve suitable for cryptographic applications. In fact,
the criterion of the choice is the impossibility of maintaining some kinds
of attacks suggested for elliptic curve cryptosystems. The recommenda-
tions below follow the strategy of choosing a random curve. This strategy
is regarded as the most reliable with respect to security of the resulting
cryptosystem. The alternative approach, not considered here, is to sys-
tematically construct the curve with desired properties which occurs more
efficient from the computational point of view. There are special methods
Basics of Contemporary Cryptography for IT Practitioners
92


suggested for implementing this approach but the curves obtained are in
fact chosen from a relatively small set of curves and are suspected to have
some special features which may allow, in the course of time, to invent
efficient attacks against them.
Let us describe in steps the process of selecting a good random curve.
(1) Select randomly a prime number p . As will be shown in Sec. 6.6, the
number of points on the curve is of the same order as p . So the bitlength
+
of p , t = Llogp] 1, must be sufficiently great to prevent the use of general
methods for computing discrete logarithms on the curve whose complexity
is proportional to 2t/2 operations. The value o f t = 128 bits (4 machine
words on 32-bit computers) is not sufficient today because there are re-
ports of breaking corresponding curves for several months of intensive dis-
tributed computations. But the value o f t = 160 bits (5 machine words) is
nowadays inaccessible by cryptanalysts and may serve as a starting point.
Another reasoning is based on the demand that the elliptic curve cipher be
no less secure than the block cipher AES (which is now the US standard,
see Sec. 8.2.3). It is believed that the security of AES is provided by the
full key length which is 128, 196, or 256 bits. Since the security of elliptic
curve cipher is determined by the value of t / 2 the length of the modulus
must be 256, 392, or 512 bits, respectively.
(2) Select random integers a and b such that a,b # 0 (mod p ) and
4a3+27b2 # 0 (mod p ) . Notice, however, that parameter b does not appear
anywhere in the formulas for computing compositions. So it is sometimes
recommended, for the sake of computational efficiency, to randomly select
only b while taking a equal to a small integer. Thus the US standard FIPS
186-2 assumes the use of curves with a = -3 which, as we shall see in
Sec. 6.5, slightly simplifies computations.
(3) Determine the number of point on the curve n = #Ep(a,b) (this
is the most complicated step in the described process, its basic algorithm
being considered in Sec. 6.6). It is important that n have a large prime
divisor q, or better be itself prime, n = q. If n has only small factors
then many small subsets with their own generators exist in Ep(a,b),and
the Pohlig-Hellman algorithm [Pohlig and Hellman (1978); Menezes et al.
(1996)I can quickly find the general logarithm through the logarithms in
these small subsets. If the search for the curve with n = q takes up too
much time then one may admit n = hq where h is a small integer. Recall
that security of elliptic curve cryptosystem is determined not by modulus
p but by the number of points in the working subset q. If h is small then
q is of the same order as p . If the number of points on the curve does not
93
Ellaptic Curve Cryptosystems


satisfy the requirements, revert to Step 2.
(4) Verify whether the inequalities p k - 1 mod q # 0 hold for all k,
0 < k < 32. If not, revert to Step 2. This check prevents the MOV-attack
[Menezes (1993)] (called after the names of its inventors Menezes, Okamoto,
Vanstone) and, as well, excludes the so-called supersingular curves and the
curves with #Ep(a,b) = p - 1. The MOV-attack and the special types
of curves mentioned allow to reduce the elliptic curve discrete logarithm
problem to simpler problems.
( 5 ) Verify whether the inequality q # p holds. If not, revert to Step 2.
The matter is that for the curves with q = p which are called anomalous,
efficient methods of computing discrete logarithms are suggested.
(6) At this step a suitable curve for cryptographic applications has been
obtained. We have parameters p , a, b, the number of points n, and the
cardinality of the working subset q. It is usually required to find a point G,
the generator of the working subset. If q = n then any point (except 0) is
the generator. If q < n then select random points G' until G = [n/q]G'# 0
is obtained. To find a random point on the curve take a random number
++
x < p , compute e = (x3 ax b) modp and try to extract the square
root g = f i m o d p . If the square root exists, we obtain the point ( I C , ˜ ) ,
otherwise try another number IC. The algorithms for computing square roots

<<

. 17
( 36 .)



>>