. 15
( 36 .)


denomination are used which is, of course, inconvenient for the users. This
can be surmounted as follows. The Bank acquires several pairs (ci, di)
subject to (5.9) and declares that, say, dl corresponds to 21000, dz to
2500, and so on. When the User requests the Bank for a blind signature she
additionally specifies the desired denomination of note. The Bank debits
the User account with the specified amount and uses the corresponding
secret number ci to generate the signature. When afterwards the Bank
receives a signed note it uses one after another the numbers d l , d2, etc. for
signature verification. If the signature occurs valid for some di then the
note of ith denomination is accepted. In the variant where the parameter
n of the note contains a fixed heading with indication of denomination, the
Bank directly applies the relevant key di.
Basics of Contemporary Cryptography for IT Practitioners

M u t u a l Identification w i t h Key Establishment

In the present section, we consider a cryptographically secure protocol that
allows two users A and B to mutually identify each other (i.e. A makes sure
that she deals with B , and B makes sure that he deals with A ) and to create
a common secret key that may be used for further encryption of transmitted
messages. In real life A and B may be a user and a computer system, or
two computer systems, it does not matter for the protocol described below.
In the course of our study we consider more and more subtle types
of attacks and means of protection against them. Thus we have consid-
ered earlier (see Secs. 2.1 and 2.2) the approaches to solve the problem of
identification and key establishment. But we implicitly assumed then that
the adversary can only overhear the information transmitted over open
channels. However, in contemporary communications networks, e.g. in the
Internet, the user data is transmitted through a number of intermediate
nodes (such as routers, gates, mail servers, etc.) that are not controlled by
the user. As a result, an adversary settled down on one of such nodes is able
not only to overhear the information, i.e. play just a passive role, but also
to perform some active operations, e.g. alter, install, or delete messages.
Look into a typical attack on Diffie-Hellman system in a network with
active adversary. Alice chooses her secret number X A and sends Bob g X A .
Bob chooses his secret number X B and sends Alice g x B . But Eve intercepts
these numbers and sends Alice and Bob g X E instead, where X E is her
number. All these numbers look like completely random, so neither Alice
nor Bob suspect anything. Alice ends up with the key KA = g X E X A , and
Bob with KB = g X E X B . Both these keys can also be computed by Eve.
Now when Alice sends Bob a message enciphered with K A ,Eve deciphers it,
re-enciphers with K B and sends Bob. She does similarly in case of reverse
transmission. Alice and Bob believe that they communicate securely but
actually Eve reads all their messages.
Such an attack becomes impossible if Alice and Bob do not transmit
their public keys (in the Diffie-Hellman system these are YA = g X A and
YB = g x B ) but take them out of a table or directory obtained earlier from
a “reliable” source (as it was assumed in Sec. 2.2).
As a matter of fact, the majority of public key systems require some or-
ganisational structure providing for public key certification. Such a struc-
ture may look like the following. There is a “trusted” user Trent in the
network to which Alice and Bob belong. Trent has no own interests but
to ensure a reliable and secure functioning of the network (most likely it is
Cryptographic Protocols

not a human but a heavily-guarded computer operating upon a hardcored
program). Trent makes use of some reliable cryptosystem (e.g. RSA with
the modulus length of about 10000 bits) with corresponding private keys
and performs only two tasks:
(1) he adds to his database the information about the public key of a user
sent to him as a message encrypted with the use of Trent™s public key;
(2) he provides the information about the public key of a user supplied
with Trent™s signature.
Trent™s public keys are submitted to all users by some way precluding any
interference of Eve, e.g. they are published in a form of advertisement in a
newspaper. Now Alice having computed her public key creates a message
consisted of her name and key, encrypts it with the use of Trent™s public key
and sends to Trent (nobody but Trent can decrypt this message). When
Bob needs Alice™s public key he sends Trent a request, and Trent answers
him with the signed Alice™s public key (nobody can forge Trent™s signature).
Bob verifies the signature using Trent™s public key and accepts Alice™s key
as valid. By implementing this procedure, each user of the network obtains
trustworthy information about users™ public keys and Eve cannot interfere
in this process.
So, if Alice and Bob use the authentic public keys, the Diffie-Hellman
scheme tackles the problem of establishing secret key. However it provides
no explicit identification of the users. Indeed, if Eve tries to act as Alice
then she and Bob will end up with different secret keys but it will become
evident only in the future, e.g. when Bob will have been unable to decipher
a received message or have detected that “Alice” does not understand what
he sends her. Often it is required to provide an explicit identification, i.e. to
let the parties know exactly who is who at the end of the protocol.
The Diffie-Hellman scheme has yet another disadvantage: the secret key
established by Alice and Bob will always be the same until they change their
public keys. But changing keys is a relatively slow process (e.g. it may be
necessary to inform about the change of key all users in the network to let
them correct their public key directories). It is desirable to have a protocol
which would allow for instantaneous creation of different, randomly selected
secret keys.
The solution is to use some public-key cipher for transporting secret
keys. Denote the ciphertext for message z produced with the aid of A™s
public key by PA(x). example, PA(z) may be RSA or ElGamal en-
cryption. In case of RSA, PA(x) x d A mod N A where the pair of numbers
Basics of Contemporary Cryptography for IT Practitioners

d˜ and N A is the public key of user A.) All who know A™s public key can
compute PA(z)for message x. At the same time, only A , who knows the
corresponding private key, can recover x out of y = PA(z). Similarly, we
shall denote by P B ( ˜ ) ciphertext produced with the aid of B™s public
key. Let, as before, the symbol 11 denote concatenation of numbers. We
shall describe the protocol through a series of improvements so that the
reader can understand better the details.
Recall that we are to solve the following problem: Alice and Bob wish to
mutually identify each other and establish a common secret key. Consider
first the following (flawed) 3-step protocol to discuss several issues.

Step 1 Alice devises a secret key kl, encrypts it with Bob™s public key and
sends to Bob:

A -B: (5.15)

Step 2 Bob decrypts kl, re-encrypts it with Alice™s public key and sends
to Alice:

A-B: (5.16)

Step 3 Alice decrypts kl and compares it to the key she has devised at
Step 1.
What do we have as a result of this protocol? First, Alice and Bob
have established a common secret key kl, unknown to Eve (she cannot
decrypt either P˜(k1) P˜(k1)).
or Second, Alice has got a cryptographically
secure identification of Bob since nobody but him could have decrypted kl.
Obviously, with the present protocol, Bob does not get any identification
of Alice (the message (5.15) could be sent by everybody). He could initiate
a symmetric protocol:


and obtain such identification. However, the issue here is in logical inde-
pendence of the two protocols which gives no guarantee that both protocols
are conducted by the same participants.
But there is yet a more subtle issue. Alice can use this protocol to
break the cryptosystem of Bob! This can be done as follows. Suppose
Alice has intercepted an encrypted message y intended to Bob, i.e. y =
P B ( ˜ )She pretends that she wishes to securely communicate with Bob
Cryptographic Protocoh

and initiates the protocol (5.15), (5.16). But instead of P˜(k1) sends
Bob the message y. Since Icl is an arbitrary integer, Bob does not suspect
anything. He performs his step in the protocol and decrypts IC for Alice !
The lesson that should be learned from this is the following: one should
not decrypt random numbers. It may impair one™s security. The method
of circumventing such “dangerous” randomness is to introduce redundancy
into messages, e.g. to enclose an element that is known and expected by
the recipient. Particularly, in (5.15) Alice could send her name. She could
construct a message by allocating 512 bits for random number kl and the
other 512 bits for her name, address, a fragment of public key, and simi-
lar easily verifiable information (denote these all by A), and send to Bob
Ps(klJJa). this case Bob would not have sent Alice the message 2 as
above because its corresponding 512 bits had certainly not contained
All the above-stated leads us to the following protocol due to Needham
and Schroeder[Needham and Schroeder (1978)], see also [Menezes et al.
(1996)], which completely solves the problem stated in the beginning of the

a and
Step 1 Alice devises a number kl, connects to it her public data
sends to Bob
B PB(˜,JJA).
A (5.19)

Step 2 Bob decrypts (5.19) and verifies that the message contains Alice™s
a.Next he devises a number k2, connects to it kl and
public data
sends to Alice
A +B : (5.20)
Step 3 Alice decrypts (5.20) and verifies that the message contains kl.
This gives her secure identification of Bob since nobody else could have
extracted kl from (5.19). Alice sends to Bob
A- B : P˜(k2). (5.21)

Step 4 Bob decrypts (5.21) and verifies that it is k2. This gives him se-
cure identification of Alice since nobody else could have extracted kz
from (5.20).

Now Alice and Bob can construct from kl, k2 a common key, e.g. k =
kl @ kz where @ is bitwise summation modulo 2, or they can use kl and k2
separately for enciphering incoming and outcoming messages.
Basics of Contemporary Cryptography for IT Practitioners

Example 5.5 Let in some network the ElGamal cipher be used with
common public parameters p = 107, g = 2. Users A and B have public
keys dA = 58, dg = 28, to whom the private CA = 33, CB = 45 correspond.
Consider a realisation of Needham-Schroeder protocol for mutual identifi-
cation of users A and B and secret key establishment. Due to small value
of modulus p in our example we shall use one decimal digit as the user™s
identificator. Let A = 1, B = 2, and the intended secret key be also one
At the first step of the protocol A devises a secret key, say, kl = 3,
and constructs a message m = k1llA = 31. This message is encrypted by
ElGamal cipher with B™s public key:

k = 15, r = gk m o d p = 215 mod 107 = 26,
e = m . d g k modp = 31 .2815 mod 107 = 47.

The pair of numbers (26,47) is the ciphertext to be sent to B. In the

notation of the protocol, PB(k1lIA) = (26,47) and

A (26,47).

At the second step B decrypts (26,47) applying his private key:
m = e . rP--l--cB
™ mod p = 47. 26106-45 mod 107 = 31.

B verifies that the low-order digit equals the identification number of user
A and extracts k l = 3. Then he selects his secret number, say, k2 = 7,
constructs a message m = k l 11 kg = 37 and encrypts it using A™s public key:

k = 77, r = gk m o d p = 277 mod 107 = 63,
e = m .dA k mod p = 37. 5877 mod 107 = 18.

The pair of numbers (63,18) is what he shall send to A. That is

P ˜ ( k l I I k 2 ) (63,18) and

A B: (63,18).

At the third step A decrypts (63,18):

m = e . TP-l-CA mod p = 18. 63106-33 mod 107 = 37

A verifies that the high-order digit contains k l = 3 and extracts ICz = 7.
Cryptographic Protocols 81

Now A encrypts for B:

r = gk modp = 241 mod 107 = 8 2 ,
k = 41,
e = m . d B k mod p = 7 . 2841 mod 107 = 49,

and sends to B


. 15
( 36 .)