650465522521y=

115165441243 ˜
= 1, P = (x7™
y7). Verify the hypothesis XR  x p = 0:
Let™s try T
h, = 552631612401  533030166456˜10000000
= 61115566241 # 0 mod $5.
Try T = 2. Compute P = [2](z7,y7). Here it is convenient to use point
addition since we add the point (x7, to the previous point P. We obtain
y7)
k = 3 . 100000002 + 2  434232361462

2051341455˜™
2.1064524266˜
4342323614622 213203662514
 2 * 10000000 =
xp =
20513414552y2 220445441503 ™
Verify the hypothesis X R  x p = 0:
h, = 552631612401.220445441503  213203662514.533030166456
= 0 mod $5.
Elliptic Curve Cryptosystems 109
Hence, X R = xp. Now we need to compare TJR and yp. We have
434232361462  1064524266y
yp = (10000000  213203662514)
220445441503 2051341455˜
 510334350655

221015611231y *
Verify whether YR  y p = 0:
h,  510334350655.115165441243
= 515441613166˜˜221015611231˜
= 0 mod $5.
Hence, t 5 = 2.
Finally, determine t 2 . We must find the greatest common divisor for
++
z3 ax b and x p  x. Apply the Euclidean algorithm for polynomials.
Notice that under the large p used in cryptography, we cannot store in
memory and operate with the polynomial x p  z. But at the first step of
+
Euclidean algorithm the remainder is computed (zp  z) mod (x3+ a x b ) ,
therefore it suffices to set as input not the polynomial z p  z but the
remainder. So we compute z p mod (x3+az+b) using a fast exponentiation
algorithm and subtract x. After that preparation we run the Euclidean
algorithm. In out example,
x7 = 304 mod 1026 ,
x7  x = 364,
gcd( 1026,364) = 1.
Hence, t 2 = 1.
Now apply the Chinese Remainder Theorem [Knuth (1981); Menezes
et al. (1996)l. We have
t=lmod2,
t = 0 mod 3 ,
t = 2 mod 5 ,
N = 2 3 3 . 5 = 30.
The solution t˜ = t mod N is found by the formula
3
aiNiMi mod N
t™ =
i= 1
Basics of Contemporary Cryptography for IT Practitioners
110
where
al = 1 , N1 = 30/2 = 15, MI = 151 mod2 = 1 ,
a2 = 0 , N2 = 30/3 = 10, M2 = lo' mod 3 = 1 ,
a3 = 2 , N3 = 3015 = 6 , M3 = 61 mod 5 = 1 .
Substituting the numbers we obtain
1 . 1 5 . 1 + O . 1 0 . 1 + 2 . 6 . 1 = 27.
t' =
To make the solution satisfy the inequality (6.27) subtract the modulus:
t=t'N=3.
By Eq. (6.23) find
#&(2,6) = 7 + 1  (3) = 11.
We see that determination of the number of points on the curve is
not a simple problem. Solving it requires highperformance computers.
In practice, improved versions of Schoof's algorithm are used that involve
subtle higheralgebraic constructions. The main feature of these methods
is the reduction of the degree of division polynomials from O ( m 2 ) down
to O(m). As a result, the complexity is reduced to O(log6p) and may be
further decreased down to O(10g4+'p) owing to the use of asymptotically
faster methods of multiplication and division.
Using Standard Curves
6.7
In view of the fact that generating random curves according to the guide
lines of Sec. 6.3, especially performing the step of point counting, appears
quite difficult, it is enough in practice to use the curves suggested by vari
ous standards and other sources. For instance, the US standard FIPS 1862
[FIPS 1862 (2000)] suggests specific elliptic curves for several lengths of
moduli. Generally speaking, there are no restrictions that one wellchosen
elliptic curve be used by all the users over the world. However such a curve,
being widely used, will attract considerable forces of cryptanalysts and ad
versaries. One cannot rule out the possibility that, in the course of time,
some attacks on that specific curve will be invented by utilising its hid
den properties not taken into account earlier. But this is only a possibility
which is considered by many specialists a highly improbable.
s
111
Elliptic Curve Cryptosystems
Let us give an example of a real curve suggested by FIPS 1862 (Curve
P256). By a backslash \ we denote the continuation of a number at a
next line. It is assumed that the curve is defined by the equation Y2 =
+
X 3 aX i b mod p , the number of points on the curve #Ep(a,b ) = n,
the point G = ( x ˜ , y ˜ )a generator of the working subset of points of
is
cardinality q where q is prime.
+ 2192 + 296  1
= 2256  2224
= 115792 089210356 248762697 446949407 573530086\
143415290 314195533 631308867 097853951
a = 3
b = O x 5ac635d8 aa3a93e7 b3ebbd55 769886bc 651d06b0\
cc53bOf6 3bce3c3e 27d2604b
n = 115792 089210356 248762697 446949407 573529996\
955224135 760342422 259061068 512044369
(prime number)
q=n
XG = Ox 6bl7dlf2 e12c4247 f8bce6e5 63a440f2 77037d81\
2deb33a0 f4a13945 d898c296
YG = O x 4fe342e2 fela7f9b 8ee7eb4a 7cOfQe16 2bce3357\
6b315ece cbb64068 37bf51f5
We can see that parameters p and a are scarcely be conceived as random,
and all “randomness” of the curve is determined by the random choice of
parameter b.
The first question that arises when we are given a curve such as the one
above: are there no errors in the record of parameters? Three basic tests
can be performed to ascertain this.
(1) Verify that p is prime.
(2) Verify that the point G = ( x ˜ , ylies on the curve (satisfies the
˜)
curve equation).
(3) Verify that n is indeed the number of points on the curve. Note that
this check makes sense also if we ourselves compute n, e.g. by the use of
Schoof™s algorithm. In general case, n = hq where h is a small integer and q
prime. First of all, by trial division and testing primality, one should make
certain that n complies with the specified form. Then randomly select a
point P on the curve (one may take P = [k]Gwhere k is a random integer).
The number n is guaranteed to be the number of points if simultaneously
[n]P= 0 and [h]P# 0. This condition being unsatisfied, two variants are
possible: If [n]P# 0 then n is not a number of points; but if [h]P= 0
Basics of Contemporary Cryptography for IT Practitioners
112
(which is extremely unlikely) then one needs t o take another point P.
In addition t o the proposed tests one may verify all other requirements
described in Sec. 6.3.
The second question that arises when we are given a “cooked” curve, is
whether it actually was generated randomly? This question is also impor
tant for many other cryptographic schemes. May be, the curve suggested
possesses some rare property allowing to break the resulting cryptosystem,
and the one who has manufactured the curve will be able later on to access
the secret information encrypted with the aid of this curve. To prove that
the curve was indeed randomly generated, we must prove that its parame
ters were chosen randomly but not at will. For instance, for the curve rec
ommended above, we must prove that parameter b was selected at random.
But how can one prove that some number is random? Actually, what we
need is to prove that it was not systematically constructed. This problem is
solved as follows. Let h ( z ) be a cryptographically secure hash function. To
generate a number b we select a number s, compute b = h(s) and suggest
both b and s. If the hash function satisfies all security requirements (see
Sec. 8.5) then b cannot have any prescribed properties and we can rely on
it, as it were truly random. The number s is the ˜˜certificate” which proves
the “purity” of number b (everyone can verify that b = h ( s ) ) . The elliptic
curve described above has such a certificate, based on hash function SHA1
[FIPS 1801 (1995)], and the standard specifies the procedure of its usage.
Therefore me may be sure that the curve is actually random.
Problems and Exercises
6.1 The elliptic curve is defined by the parameters p = 11, a = 4, b = 7.
Determine whether the following points are on the curve: (l,l), (1,2),
(2,1), (2,2), ( 5 8 .
6.2 For the elliptic curve with parameters p = 7, a = 2, b = 6 compute
+
the following point compositions: [2](2,2), [2](4,6), (1,3) (1,4),
+ +
(272) (3,2), (375) (5,1).
Elliptic Curve Cryptosystems 113
Themes for Labs
In labs, it is recommended to use the elliptic curve with the following
parameters:
a = 3 = 31988, b == 1000.
p = 31991,
The number of points on this curve
n = 32089 (prime number).
As a generator, one may take the point
G = (0,5585)
It is convenient to represent the point at infinity 0 as a point with
coordinates (0,O).
6.3 Write the set of programs (program functions) for computation of el
liptic curve point addition, doubling, and multiplication. We propose
several equalities for program testing:
+ (91,5500) = (7252,18353),
(51,7858)
(7777,10935) + (16000,20400) = (12395,26268),
(12405,28624) + (2963,16300) = (14905,2313),
(8020,1740) + (8020,30251) = 0 ,
[2](0,5585)= (8,19435),
[2](23161,17992) = (26775,10831),
[2](110,13171) = (26948,16087),
[10000](31122,9)= (31180,29596),
[12345](13140,5033) = (9362,27046),
[11111](11007,23704) = (850,6718).
6.4 Make a program implementation of ElGamal cipher on elliptic curve.
When debugging and testing the program one may use the following
Basics of Contemporary Cryptography for IT Practitioners
114
example of cipher:
D
c = 5103, = (12507,2027) ;
k = 523 ;
r = 10000,