(a) UNSJFUUQJ

(b) GUHAI

Chapter 2

Public Key Cryptosystems

2 1 Prehistory and Main Ideas

.

Let™s consider three problems whose solution will help us understand better

the ideas and methods of public-key cryptography. All these problems are

of great practical interest.

The first problem is storing passwords in a computer. We know that

every user in a network has a confidential password. In order to log in to

the network the user have to type in his/her login name (usually, publicly

known) and password. The issue is the following: if the password is stored

on a computer disk, then Eva can read it through (perhaps, temporarily

dismounting the disk). Therefore it is necessary to store passwords in such

a way that they could not be read (but could still be verified).

The second problem has occurred with the advent of radars and systems

of air defence. When a plane is crossing the border, the radar system

asks for a password. If the password is valid then the plane is admitted,

otherwise the flight is denied. The problem here is that the password has

to be transmitted over the public open channel (air) and can therefore be

overheard by the enemy. After that, when the enemy plane is asked for a

password, it simply replays the intercepted one and gets admittance.

The third problem is similar to the previous one. It arises in computer

networks with remote access, e.g. in interactions between a bank and a

client. In the beginning of a session the bank asks the client for the userid

and password, but Eve can overhear the transmission since the communi-

cations line is public.

Nowadays all these problems are solved by applying cryptographic meth-

ods. The solution is based on an important notion of one-way function.

7

Basics of Contemporary Cryptography f o r IT Practitioners

8

Definition 2.1 Let there be a function

Y = f (XI (2.1)

defined on a finite set X (z E X), for which the inverse function exists

(2.2)

z =f-l(y).

The function is said to be one-way if Eq. (2.1) is “easy” to compute for all

x but for “essentially all” y the reverse computation (2.2) is “infeasible”

(say, requires 106-1010 years on a supercomputer).

This definition is certainly informal. A rigorous definition of one-way

function may be found in the literature (e.g. [Goldwasserand Bellare (2001);

Menezes et al. (1996)l) but for our purposes the one given above will suffice.

As an example of one-way function, let us consider the following:

y = a” modp (2.3)

where p is a large prime number (i.e. an integer that is divisible only by

1 and itself) and a , z positive integers (some restrictions will apply in the

sequel). The inverse function is denoted as

z = log, y mod p (2.4)

and is called the discrete logarithm.

To make computation of (2.4) really infeasible on all modern computers

one have to use numbers of length more than 512 bits. In practice, other

one-way functions are also used, e.g. so-called hash functions (considered

in Chap. 8) that operate with shorter numbers of length 80-160 bits.

First we show that computation of (2.3), i.e. modular exponentiation,

can be carried out fast. Begin with the example of computation of a16modp.

We can write

2

u16modp= ( ( ( u ˜ ) ˜ ) ™ ) o d p ,

m

i.e. the value of this function is obtained for 4 modular multiplications

instead of 15 in the “naive” variant a.a +. ..a. This is the general algorithm

.

based upon.

To describe the algorithm we introduce the quantity t = [logz xj , i.e. the

integer part of log, x (in what follows all logarithms are binary, so we shall

not indicate the base 2 henceforth). Compute the series of numbers

..., a 2t (modp)

a2, u 4 , a8,

a,

Public Key Cryptosystems 9

In Eq. (2.5) each number is obtained by squaring the preceding number

modulo p . Write the exponent x in binary system:

x = (xtxt-1 . . . X I X 0 ) 2 *

Then the value y = a“ m o d p can be computed as

nt

mod p

y= (2.6)

i=O

(all operations are modulo p ) .

Let us compute 374 mod 100. We have t = Llog741 = 6.

Example 2.1

Compute the series of numbers (2.5):

3 32 34 38 316 364

332

(2.7)

3 9 81 61 21 81.

41

Write the exponent in binary system:

74 = (1001010)˜

and compute by (2.6):

364 38 32

81 * 1 . 1 * 6 1 * 1 9 . 1 = 6 9 .

.

As few as 8 multiplications were required (6 for computation of (2.7) and

2 for (2.8)).

In general case, we have the following

Proposition 2.1 (complexity of exponentiation) T h e number of multipli-

cations t o compute ( 2 3 ) using the described method does not exceed 2 log x .

To compute the series (2.5) t multiplications (squarings) are re-

Proof.

quired, to compute y by (2.6) we need at most t multiplications (see Exam-

ple 2.1). So the total number of multiplications does not exceed 2t. Since

t = [log x) 5 log 5 the correctness of the proposition is obvious. 0

Remark It will be shown later that in exponentiation modulo p , it makes sense

to use only exponents x < p . So we can say that the number of multiplications

to compute (2.3) does not exceed 2logp.

It is important to note that as effective algorithms for computing the

inverse function (2.4) are unknown, one of the methods called “baby-step

giant-step™™ algorithm will be described in detail in Sec. 3.2. This method

requires on the order of 2 f i operations. Let us show that under large p the

Basics of Contemporary Cryptography for IT Practitioners

10

function (2.3) is actually one-way if the “baby-step giant-step” algorithm

is used. The results are given in Table 2.1.

Table 2.1 The number of multiplications for computing direct and inverse

functions.

Computation of (2.4)

The number of Computation of (2.3)

(2 logp multiplications) (2fi multiplications)

decimal digits in p

2 ™ 40 = 80

12 2.106

2.200 = 400

60 2.1030

2.300 == 600 2.1045

90

We can see that if the length of modulus is about 50-100 decimal digits

then the direct function can be computed shortly but the inverse one is

practically non-computable. Consider, for example, a supercomputer that

multiplies two 90-digit numbers for sec (for contemporary computers

it is not achievable). To compute (2.3) such a computer will require

=6* sec

Tdir, = 600 *

but to compute (2.4)

qnv. = 1031 sec,

=

i.e. more than years. We see that computation of inverse functions is

practically impossible if the length of numbers is about 90 decimal digits

and the use of parallel and distributed systems does not essentially affect

the situation. In the example considered, we assumed that the inverse func-

tion was computed for 2Jir operations. At present time “faster” methods

for computing discrete logarithms are known but the pattern is the same:

the number of required operations is far greater than 2logp. So, we can

conclude that the function (2.3) is indeed one-way with the only one reser-

vation: nobody has strictly proved that the inverse function (2.4) cannot

in principle be computed as fast as the direct function.

Now we shall use the one-way function (2.3) for solving all three prob-

lems stated in the beginning of the section, though taking into account that

any other one-way function may be used instead.

Begin with storing passwords in a computer. The solution of the prob-

lem is based on the idea that passwords are not stored at all! To log in

to the computer the user types in his/her login name and password. Let,

for instance, the login name be “fruit” and the password “apricot”. The

Public Key Cryptosystems 11

computer treats the word “apricot” as the binary record of the number x

and computes (2.3), where a and p are two non-secret numbers, perhaps,

publicly known. After that the computer creates and stores the pair (login

name, y), where y is obtained from (2.3) under x = password. Upon the

user™s login, after entering the pair (“fruit”, “apricot”),the computer finds

by (2.3) a new value ynew under x =“apricot” and compares it with the y

already stored in the memory. If ynew is the same as the y corresponding

to the specified login name the user is admitted to the system. Otherwise,

the access is denied.

Eve might try to find x if she somehow learned y. However we have seen

years. In

that even with 90-digit numbers it would require more than

that way, the presented scheme of storing passwords is reliable and used in

many operating systems.

Let us discuss a solution of the second problem (a plane and air defence).

One can use the following method. Each “legitimate” plane is assigned a

secret name (i.e. password) which is known only to the air defence system

and to the pilot (or, more precisely, to the on-board computer). Let, for

instance, one of the planes be assigned the secret name FALCON and the

plane is approaching the border on February 1, 2005 at 12:45. Then the

on-board computer constructs the word

12 45

FALCON 05 02 01

(name year hours minutes).

day

month

In other words, the on-board computer, as well as the radar system,

append the timestamp to the name. Now they treat the word obtained as

the number x and compute y = a” modp, where a and p are non-secret.

After that the plane communicate the number y to the radar system. The

latter compares its own y to the received value. If both values are equal

the plane is admitted as legitimate.

The enemy cannot break this system. Indeed, on the one hand, she

does not know the secret name FALCON and cannot recover it from y,

years. On the other hand, she

since finding x given y requires, say,

cannot replay the same y in the future as the response to the radar system

since the time of crossing border will never be the same and the subsequent

values of y will differ from the one stored by the enemy.

This way of solution of the “air defence” problem requires precise syn-

chronisation of the clocks on the plane and in the radar system. The issue

can be easily settled. For instance, the navigation control service period-

Basics of Contemporary Cryptography for IT Practitioners

12

ically transmits timestamps and all radars and planes use these to syn-

chronise their clocks. But there are more delicate issues. A timestamp is

appended to the word x in order to make all computed values of y differ-

ent and to preclude replaying by the enemy. However the enemy may try

to replay y immediately within the current minute. How to prevent this

opportunity? This is the first question. The other difficulty arises in a

situation when the plane sends the number y in the end of 45-th minute,

and the radar receives it in the beginning of 46-th. We give the reader an

opportunity independently to offer a variant of the solution t o these issues.

The other way of solution of the “air defence” problem is possible if we

use an extra communications channel for transmitting data from the radar

system to the plane. As before, each “legitimate” plane is assigned a secret

name such as FALCON which is also known to the radar. Having located

a target, the radar sends a randomly generated number u (“challenge”).

The plane computes y = a” mod p , where x is the secret word (FALCON)

and communicates y (“response”) to the radar. The radar performs the

same computations and compares the received and computed values of y.

In this scheme, synchronising clocks is not needed but, as earlier, the enemy

cannot replay y since the radar sends a different challenge ( u ) each time.

It is interesting, that this problem, apparently, was historically the first to

be solved with the aid of one-way functions.

The third problem is solved absolutely similarly and both methods of

transmitting passwords are applicable and used in practical network proto-

cols.

The First Public Key System - DiffieHellman K e y

2.2