. 3
( 36 .)


and an unknown key k, 0 < k < 26:
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.

Basics of Contemporary Cryptography f o r IT Practitioners

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

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
u16modp= ( ( ( u ˜ ) ˜ ) ™ ) o d p ,

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,
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

mod p
y= (2.6)

(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
3 9 81 61 21 81.
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-
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

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

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

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).

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

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-

The First Public Key System - DiffieHellman K e y


. 3
( 36 .)