Let us begin the study of cryptography with the classical problem of trans-

mitting secret messages from a sender A to a receiver B. Both the sender

and the receiver may be persons, organisations, various technical systems.

Sometimes one speaks of A and B as of subscribers of some network, users

of some computer system, or, more formally, abstract “parties” or “entities”

participating in information exchange. But it often occurs more convenient

to identify the participants of exchange with some humans and use the

names Alice and Bob instead of A and B.

It is assumed that messages are transmitted via an open communications

channel which can potentially be accessed by a third party different from

the sender and receiver. Such a situation arises in radio transmission (say,

from a mobile phone) and is possible even in such “trusted” systems as wire

telephone, telegraph, as well as in ordinary mail. The Internet, as a means

of communication gaining the leading positions all over the world, offers

a special interest of being extremely vulnerable for unauthorised access

of third parties. In this environment, not only copying of data is easily

implemented but also deletion and substitution.

It is generally assumed in cryptography that the person who sends

and/or receives messages has an adversary or enemy E , which can be a

competitor in business, a member of a criminal group, a foreign intelli-

gence agent, or even an excessively jealous spouse, and that the adversary

can read and analyse the messages transmitted. The adversary is often

thought of as a person called Eve who has powerful computing facilities

and is able to use cryptanalytic methods. Of course, Alice and Bob want

their messages to be completely unclear to Eve, and, to achieve this, they

use appropriate ciphers.

Before transmitting a message from A to B over an open communica-

1

Basics of Contemporary Cryptography for IT Practitioners

2

tions channel, A encrypts (or enciphers) the message. In his turn, B , after

having received the encrypted message (ciphertext), decrypts (or deciphers)

it to recover the initial text (plaintext). It is important for the problem

considered in this chapter that Alice and Bob can agree in advance about

the cipher to be used (or rather about certain parameters thereof) not via

a n open channel but via a special “secure” channel which is inaccessible for

Eva. Such a “secure channel” can be maintained with the aid of trusted

messengers or couriers, or Alice and Bob can agree on the cipher during

their private meeting, etc. It is necessary t o take into account that, usually,

maintaining the secure channel and transmitting messages over this chan-

nel is much more expensive compared with an open unsecured channel, and

(or) the secure channel cannot be used at any time. For instance, courier

post is far more expensive than the regular one, it transmits messages much

slower than, say, electronic mail, and may be used not at any hour and not

in any situation.

To be more concrete, consider an example of cipher. Since the problem

of encryption has occurred long ago in centuries some ciphers are named

after renowned historical persons. These ciphers are often used to introduce

simple initial concepts and we shall follow that tradition. Let us start with

a well-known cipher by Gajus Julius Caesar. In this cipher, each letter of a

message is substituted by the other letter whose ordinal in the alphabet is

increased by 3. For instance, the letter A is replaced by D, the letter B by E,

and so on. The last 3 letters X, Y , Z are replaced by A, B, C, respectively.

Thus the word SEQUENCE transforms to VHTXHQFH under the Caesar

cipher.

Other Roman Caesars have modified the cipher by using the shifts

through 4, 5 and more letters in the alphabet. We can describe such ci-

phers in a general way if we enumerate (encode) the letters by their ordinal

numbers (from 0 to 25). Then the rule of encryption will be

c = (m+k)mod26, (1.1)

where m and c are the ordinals of letters of plaintext and ciphertext, re-

spectively, and k is an integer called the cipher key (in the Caesar cipher

considered above, k = 3). (Here and after a mod b denotes the remainder

from division of integer a by integer b, the remainder being taken from the

set { 0 , 1 , . . . , b - 1). For instance, 13 mod 5 = 3.)

To decrypt the ciphertext one should apply an “inverse” algorithm

m = (c - k) mod 26. (1.2)

3

Introduction

Let™s imagine that the sender and receiver have agreed to use the cipher

(1.1) but, to make the adversary™s job more difficult, decided to occasion-

ally change the cipher key. For that purpose, Alice somehow generates the

number k , sends it to Bob over a secure channel, after which they com-

municate messages encrypted with that k . The key may be changed prior

to each communication session or after transmitting a specified number of

letters (say, encipher every ten letters using a different key) and so forth. In

this situation, the key is said to be generated by a key source. A schematic

view of the cryptosystem considered is shown in Fig. 1.1.

encrypter decrypter

open channel

secure channel

Fig. 1.1 Classical secret communications system.

Proceed now to the discussion about the actions of adversary who tries

to recover the message and find the secret key, or, in other words, to break

the cipher. Every attempt to break a cipher is called an attack to the cipher

(or cryptosystem). It is generally assumed in cryptography that the adver-

sary always has the ciphertext in her disposal and can learn everything

about the encrypting algorithm used and the nature of data transmitted,

but only does not know the secret key. These are the Kerckhoffs assump-

tions named after the scientist who was the first to formulate the main

requirements to ciphers [Kerckhoffs (1883)]. Sometimes these assumptions

may seem “overcautious” but such “overcautiousness” is by no means su-

perfluous if, say, you send an order to transfer one million dollars from one

account to another.

In our example, Eve knows that the plaintext was encrypted according

to (l.l), message was in English, and the ciphertext is VHTXHQFH.

the

But the key is unknown to her.

The most obvious method to recover plaintext from ciphertext is to

search through all possible keys (this is a so-called brute-force attack

Basics of Contemporary Cryptography for IT Practitioners

4

or exhaustive key search). Thus Eva tries successively all possible keys

k = 1 , 2 , . . . , applying them to decrypting algorithm and estimating the ob-

tained results. Let us also try to use this method. The results of decrypting

according to (1.2) under various keys and the ciphertext VHTXHQFH are

shown in Table 1.1. In the majority of trials it was sufficient to decrypt

only a few letters to reject the corresponding key due to the absence of the

word in English that begins with these letters.

Table 1.1 Decrypting the word VHTXHQFH by exhaustive key search.

k m

k m k m k m

GS

8

UGS NZ 15 22 ZL

1

TF MYKOY YK

9 16 FRD 23

2

17 EQC 24 XJ

3 SEQUENCE 10 LX

KWI DP WIU

18 25

11

4 RD

19 COAE 26 VHTXHQFH

12

5 QC JV

PB IU

13 20 BN

6

OAM AMY

7 14 HT 21

We can see from Table 1.1that the key k = 3 was used and hence the

message SEQUENCE was enciphered. Moreover, when checking for the

other values of key, it was not required to decrypt all 8 letters since the key

might often be rejected after decrypting 2 or 3 initial letters. This example

shows that the Caesar cipher is completely insecure: for breaking it, one

needs to analyse several initial letters of the message after which the key

is disclosed unambiguously and, consequently, the whole message may be

deciphered.

What are the reasons of weakness of the considered cipher and how

might its security be increased? Consider another example. Suppose that

Alice hid some important documents in a safe with 5-digit combination lock.

Now she would like to tell Bob the combination for opening the safe. She

decided to use an analogue of the Caesar cipher adapted to the alphabet of

decimal digits:

+

c = ( m k) mod 10. (1.3)

Suppose she sent Bob the ciphertext 26047. Eve tries to decrypt it, as

earlier, by searching through all possible keys. The results of her work are

shown in Table 1.2.

We can see that all the variants are equivalent and Eve cannot decide

on what combination is true. Based on the ciphertext only, she is unable to

Introduction 5

Table 1.2 Decrypting the word

26047 by exhaustive key search.

k m k m

1 15936 6 60481

2 04825 7 59370

8

3 93714 48269

4 82603 9 37158

0

5 71592 26047

find the secret key. Of course, before intercepting the encrypted message

she had lo5 possible lock combinations, and after that only 10. But it is

important to note that in this particular example we have only 10 possible

values of the key. Under such a key (one decimal digit) Alice and Bob could

not count on better security.

The message in our first example is the text in natural language (En-

glish). So it obeys numerous rules, various letters and their combinations

have different probabilities and, in particular, many combinations are for-

bidden (this property is referred to as redundancy of the text). And that

is why the key was easily found and the message recovered, i.e. the redun-

dancy had made it possible to break the cipher. But, in contrast, in our

second example all combinations of digits are admissible. The “language”

of combination lock does not possess any redundancy. Therefore even a

simple cipher applied to messages in that language becomes unbreakable.

In the classical work by C. Shannon [Shannon (1949)], a deep and elegant

theory of secret key ciphers is constructed and, specifically, a “correct”

measure of redundancy is suggested. We shall briefly touch upon these

topics in Chap. 7, and in Chap. 8 some modern secret key ciphers will be

described.

The attack to the cipher considered in the previous examples is said

to be a ciphertext-only attack. But sometimes a so-called known-plaintext

attack to the cipher may be maintained. This happens if Eve obtains

in her disposal some plaintexts corresponding to previously transmitted

ciphertexts. Eve tries to disclose the secret key by examining the pairs

plaintext-ciphertext. If she succeeded, she would be able to decrypt all

further messages from Alice to Bob.

One can imagine even a more “serious” attack, a so-called chosen-

plaintext attack. In this attack, an adversary not only can access some

plaintext-ciphertext pairs but is also able to create plaintexts on her own

Basics of Contemporary Cryptography for IT Practitioners

6

and encrypt them under the key she wants to disclose. For instance, dur-

ing World War 11, Americans, having bribed the guards, stole the cipher-

machine in Japan Embassy for two days at weekend and had an opportu-

nity to input various plaintext and obtain corresponding ciphertexts. They

could not open the machine to directly determine the installed key because

the damage would be detected and all the keys immediately changed (this

and many other stories can be found in [Kahn (1967)I).

It may seem that the known- and chosen-plaintext attacks are rather

artificial and hard to maintain. It is so to some extent. But the designers of

modern cryptosystems strive to make them invulnerable even to those kinds

of attacks and there are great achievements in this direction. It is customary

to think that it is more reliable to use a cipher secure against chosen-

plaintext attacks rather than organisationally ensure the impossibility of

such attacks. Extremely cautious people do both things.

So, we have acquainted with the main characters of cryptography -

Alice, Bob, and Eve, and with important notions of that science - a cipher,

a key, an attack, open and secure channels. Note that an intriguing fact is

connected with the last item: secure cryptosystems are possible to construct

without any secure channel! In such cryptosystems Alice and Bob compute

the secret key so that Eve cannot do that. This discovery was made in

the seminal works ([Diffie and Hellman (1976); Mercle (1979)l) and has

constituted a new epoch in modern cryptography. The main part of this

book will be devoted to this kind of cryptosystems, referred to as public-key

or asymmetric-key schemes.

Problems and Exercises

1.1 Find the keys of the Caesar cipher if the following plaintext-

ciphertext pairs are known:

(a) ORANGE - FIREXV

(b) APRICOT - XMOFZLQ

1.2 Decrypt the following messages encrypted with the Caesar cipher