<<

. 16
( 36 .)



>>


B:
A (82,49).

At the fourth step B decrypts (82,49):

mod p = 49 . 82106-45 mod 107 = 7 .
m = e . rP--l--cB
˜

B verifies that he obtains his secret number k2 = 7.
Now A and B can make a common key by a method agreed in advance,
e.g.

k = k l @ k2 mod 10 = 3 @ 7 = (011)2 @ (111)2 = ( 1 0 0 ) ˜ 4 ,
=


Problems and Exercises

5.1 For realization of the “Mental poker” protocol the following common
parameters are chosen: p = 23, & = 5, /3 = 7, = 14. Besides, there
are the following variants for Alice and Bob:
(a) = 13, = 5, Alice shuffles cards by the rule ( 1 , 2 , 3 ) +
CA CB
(3,2, l),Bob selects the first number and uses the permutation
(1,Z) --+ ( 2 , l ) . Alice selects the second number.
CA = 7, cg = 15, Alice shuffles cards by the rule (1,2,3) +
(b)
(1,3,2), Bob selects the second number and uses the permuta-
tion (1,2) -+ (1,2). Alice selects the first number.
(c) CA = 19, CB = 3, Alice shuffles cards by the rule (1,2,3) -+
(2,1,3), Bob selects the second number and uses the permuta-
tion (1,2) -+ ( 2 , l ) . Alice selects the second number.
(d) C A = 9, C B = 7, Alice shuffles cards by the rule (1,2,3) --+
(3,2, l ) ,Bob selects the third number and uses the permutation
(1,2) --+ (1,2). Alice selects the second number.
(e) C A = 15, CB = 5 , Alice shuffles cards by the rule (1,2,3) +
(1,2,3), Bob selects the first number and uses the permutation
(1,2) --+ ( 2 , l ) . Alice selects the first number.
Basics of Contemporary Cryptography f o r IT Practitioners
82


Determine which cards will be Alice™s and Bob™s hand. What num-
bers transmitted will Eve observe?
5.2 In the digital cache system the secret parameters of the Bank are
P = 17, Q = 7, c = 77, and the corresponding public parameters
N = 119, d = 5. Make digital bank notes with the following serial
number:
(a) n = 11 under = 5,
T

n = 99 under = 6,
(b) T
n = 55 under
(c) = 10,
T

(d) n = 44 under = 15,
T

(e) n = 77 under = 30.
T




Themes for Labs

In all tasks below, we suggest the reader to select the necessary pa-
rameters and cryptographic tools at his/her discretion.
Make a computer implementation of the “Mental poker” protocol.
5.3
Make a computer implementation of the zero-knowledge protocol
5.4
based on the graph colouring problem.
Make a computer implementation of the zero-knowledge protocol
5.5
based on the Hamiltonian cycle problem.
Make a computer implementation of the digital cache protocol.
5.6
Make a computer implementation of the Needham-Schroeder mutual
5.7
identification protocol.
Chapter 6

Elliptic Curve Crypt osyst ems



Introduction
61
.

In this chapter, we consider one of the new directions of public-key cryptog-
raphy, elliptic curve systems. Elliptic curves have been studied in mathe-
matics for a long time, but their use in cryptographic applications was first
suggested by Neal Koblitz [Koblitz (1987)] and Victor Miller [Miller (1986)l.
About 20 years of active investigations have confirmed the beneficial prop-
erties of these systems and led to the invention of efficient implementation
methods. Since the end of XX century the use of elliptic curves for pro-
duction of cryptographic primitives, such as digital signatures, has begun
to put into standards, We have now, for instance, the US standards ANSI
X9.62 and FIPS 186-2 (ZOOO), and Russian standard GOST R34.10-2001
(2001).
The main advantage of elliptic curve cryptosystems is that compared to
“conventional” systems studied in the previous chapters, they offer a signif-
icantly greater level of security within the same computational complexity,
or, vice versa, significantly lower complexity within the given level of se-
curity. It is explained by the fact that for computing inverse functions on
elliptic curves only exponential-time algorithms are known whereas subex-
ponential algorithms exist in case of conventional cryptosystems. As a
result, the level of security achieved, say, in RSA with 1024-bit modulus,
can be attained in elliptic curve systems with 160-bit modulus which allows
for a simpler hardware and software implementation.
The profound study of elliptic curves requires the knowledge of higher al-
gebra and especially algebraic geometry. We shall however try t o set out the
matter without resorting to any higher-algebraic concepts. Nevertheless it
will be sufficient for understanding construction principles and functioning


83
Basics of Contemporary Cryptography for IT Practitioners
84


of the corresponding cryptosystems. A more detailed treatment of the ellip-
tic curves and their use in cryptography can be found in [Blake et al. (1999);
Menezes (1993); Silverman (1986)]. Sections 6.5 and 6.6 are rather technical
and may be omitted at first reading.


Mathematical Foundations
6.2

A cubic curve E defined by the equation

E: Y2=X3+uX+b (6.1)
is called elliptic curve (in fact, Eq. (6.1) is derived by transformation of
variables from a more general equation which we are not interested in).
+ +
Since Y = f d X 3 aX b the graph of the curve is symmetric with
respect to the horizontal axis. To find the points of intersection between
the graph and horizontal axis one needs to solve the cubic equation

x3+ax+ b = 0 . (6.2)
This can be done using the well-known formulas by Cardano. The discrim-
inant of the equation

(i)3 + (i) 2
D =

If D < 0 then (6.2) has three different real roots a, p, y;if D = 0 then
(6.2) has three real roots, say, a , p, p, of which at least two are equal; at
last, if D > 0 then (6.2) has one real root (Y and two complex conjugate.
The shape of the curve in all three cases is shown in Figs. 6.1-6.3.




<0
Fig. 6.1 Elliptic curve, D
Elliptic Curve Cryptosysterns 85




Fig. 6.2 Elliptic curve, D = 0




>0
Fig. 6.3 Elliptic curve, D


The curve shown in Fig. 6.2 is called singular. In its singularity point
(/?,0), there are two tangents to the curve. We shall exclude singular curves.
Therefore, when defining a curve by specifying parameters a and b, we shall
require that the condition D # 0 hold, which is equivalent to

+ 27b2 # 0 .
4a3 (6.4)
So, let elliptic curve E be defined by Eq. (6.1) with the constraint (6.4).
Define the operation of point composition on the curve. Take any two
points P = ( q , y ˜ ) Q = (z2,y2) E E and plot a straight line through the
,
points (Fig. 6.4). This line will necessarily intersect the curve at a third
point which we denote by Rt. (The third point necessarily exists. The fact
is that the cubic equation obtained after substitution of the line equation
into (6.1) has two red roots corresponding to points P and Q, consequently,
the third root corresponding to point R™ is also real.) The resultant point
Basics of Contemporary Cryptography for IT Practitioners
86




+Q
Fig. 6.4 Point composition R = P




R = (23, y3) is obtained by changing the sign of y-coordinate of point R'.
We shall denote the described composition of points by R = P + Q.
Let point P E E have coordinates (2,y). Then the point with coordi-
nates (x,-y) will be denoted by - P. We shall assume that the vertical
line passing through P and -P intersects the curve at a point at infinity
0, i.e. P+ (- P)= 0. By convention, P + 0 = O + P = P. As we shall see
later, point at infinity 0 plays the role of zero in elliptic curve arithmetic.
Suppose now that points P and Q (Fig. 6.4) are approaching each other
and eventually merge into one point P = Q = ( q , y l ) . Then the compo-
+ +
sition R = (23, y3) = P Q = P P is obtained by plotting the tangent
line to the curve at point P and reflecting its second intersection with the
curve R' with respect to the horizontal axis (Fig. 6.5). We shall use the
+
following notation: R = P P = [2]P.
Let us derive formulas for determining the coordinates of the resulting
point R = (23, y3) on the basis of coordinates of initial points P = ( X I ,y1)
+
and Q = ( 2 2 , y ˜ ) . First consider the case when P # &Q, R = P Q
(Fig. 6.4). Denote by k the angular coefficient of the line passing through
Elliptic Curve Cryptosystems 87




+ P = [2]P
Fig. 6.5 Point doubling R = P



P and Q. It is obvious that

k=-*Yz - Y1
-21
22

Then the line equation will be Y - y1 = k ( X - XI), so



Y into the curve equation (6.1). We
Substitute the expression for variable
obtain

x3+ a x f b .
+k(X - =
(y1

From this by squaring and grouping similar terms we obtain the cubic
equation

X 3 - k2X2 . . . = 0
+
(here . . . stand for terms not interesting for us). It is known that the sum
of roots of cubic equation equals the coefficient under X 2 , taken with the
Basics of Contemporary Cryptography f o r IT Practitioners
88


minus sign (ViBte theorem for cubic equations), i.e.

21+52+23=k2,

hence
2

<<

. 16
( 36 .)



>>