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