. 17 |

other numbers are decrypted to yield 25, 4, 1, 17, 0, which, via Table 2.1 becomes

zebra.

N Messages and Tranformations

In order to discuss even the most basic ciphers in depth, we need to use a

rigorous mathematical language in which to carry on this discussion. Earlier in

this section, we de¬乶ed certain basic notions such as the plaintext and cipher-

text. Both the plaintext and the ciphertext are written in terms of elements

from a ¬乶ite set A, called an alphabet of de¬乶ition. The alphabet of de¬乶ition

may consist of numbers, letters from an alphabet such as the English, Greek,

or Russian alphabets, or symbols such as !, @, *, or any other symbols that

we choose to use when sending messages. The alphabet of de¬乶ition for the

plaintext and ciphertext may di¬er, but the usual convention is to use the same

for both. For instance, a commonly used one is A = {0, 1}, called the binary

alphabet of de¬乶ition, in terms of which any given alphabet may be given binary

equivalents. An example is the English alphabet, in which each letter may be

assigned a unique binary string of length ¬乿e since there are 25 = 32 binary

strings of length ¬乿e. Another example is A = {0, 1, 2}, called the ternary

alphabet, in which each letter of the English alphabet may be replaced by a

unique ternary string of length three since there exist 33 = 27 ternary strings of

length three (see page 326). Once we have agreed upon an alphabet of de¬乶ition,

we choose a message space, M, which is de¬乶ed to be a ¬乶ite set consisting of

strings of symbols from the alphabet of de¬乶ition. Elements of M, which may

be anything from binary strings to English text, are called plaintext message

units. Any block of n 鈭 N letters may be used. A ¬乶ite set C, consisting of

strings of symbols from an alphabet of de¬乶ition for the ciphertext, is called the

ciphertext space, and elements from C are called ciphertext message units. Most

often it is convenient to let M be the message space consisting of all possible

plaintext message units and C be the set of all possible ciphertext message units.

It is within this context that we will choose to work below.

To make cryptanalysis more di¬僣ult, we need a set of parameters K, called

the keyspace, whose elements are called keys. For instance, we learned above

about the Caesar cipher. In terms of the above de¬乶itions, we may restate the

cipher as follows. Given the alphabet of de¬乶ition as the numbers 0 through 25,

corresponding to the letters A through Z, respectively, any m 鈭 M is enciphered

as c 鈭 C, where

c = m + 3 鈭 Z/26Z.

Thus, the (enciphering) key is k = 3 鈭 K, since we are using the parameter 3

as the shift from m 鈭 M to achieve c 鈭 C. Also, the (deciphering) key is also

the parameter 3 since we achieve m 鈭 M from c 鈭 C by

c 鈭’ 3 = m 鈭 Z/26Z.

© 2007 by Taylor & Francis Group, LLC

2.1. De¬乶itions and Illustrations 85

We formalize the above in the following.

De¬乶ition 2.1 Enciphering and Deciphering Transformations

An enciphering transformation (also called an enciphering function) is a

bijective function

Ee : M 鈫’ C,

where the key e 鈭 K uniquely determines Ee acting upon plaintext message units

m 鈭 M to get ciphertext message units

Ee (m) = c 鈭 C.

A deciphering transformation (or deciphering function) is a bijective function

Dd : C 鈫’ M,

which is uniquely determined by a given key d 鈭 K, acting upon ciphertext

message units c 鈭 C to get plaintext message units

Dd (c) = m.

The application of Ee to m, namely the operation Ee (m), is called enciphering,

encoding, or encrypting m 鈭 M, whereas the application of Dd to c is called

deciphering, decoding, or decrypting c 鈭 C.

In De¬乶ition 2.1 we have mathematically formalized the two notions of enci-

phering and deciphering, which we informally discussed earlier in this section, as

a motivator for this formal setup. For instance, returning to the Caesar cipher,

it may be de¬乶ed as that transformation Ee uniquely determined by the key e,

which is addition of 3 modulo 26. Thus,

Ee (m) = c 鈮 m + 3 (mod 26),

or simply

Ee (m) = c = m + 3 鈭 C = Z/26Z.

Also, m 鈭 M = Z/26Z is the numerical equivalent of the plaintext letter as

described above. Similarly, Dd (c) is that deciphering transformation uniquely

de¬乶ed by the key d, which is modular subtraction of 3 modulo 26. In other

words,

Dd (c) = m 鈮 c 鈭’ 3 (mod 26),

or simply

Dd (c) = m = c 鈭’ 3 鈭 Z/26Z,

and c 鈭 C = Z/26Z is the numerical equivalent of the ciphertext letter. Notice

that

Dd (Ee (m)) = m

鈭’1

for each m 鈭 M. In other words, Dd = Ee is the inverse function of Ee . This

is formalized as follows.

© 2007 by Taylor & Francis Group, LLC

86 2. Cryptographic Basics

De¬乶ition 2.2 Cryptosystems/Ciphers

A cryptosystem is composed of a set

{Ee : e 鈭 K}

consisting of enciphering transformations and the corresponding set

鈭’1

{Ee : e 鈭 K} = {Dd : d 鈭 K}

of deciphering transformations. In other words, for each e 鈭 K, there exists a

鈭’1

unique d 鈭 K such that Dd = Ee , so that Dd (Ee (m)) = m for all m 鈭 M.

The keys (e, d) are called a key pair where possibly e = d. A cryptosystem is

also called a cipher. We reserve the term Cipher Table for the pairs of plaintext

symbols and their ciphertext equivalents

{(m, Ee (m)) : m 鈭 M}.

De¬乶ition 2.2 mathematically formalizes the notions of the terms cryptosys-

tem/cipher, cipher table, and key, which were informally discussed earlier in

this section. The case where e = d or where one of them may be 鈥渆asily鈥 deter-

mined from the other in the key pair has a special name, which is the simplest

of the possibilities for cryptosystems, and so has the longest history.

De¬乶ition 2.3 Symmetric-Key Ciphers

A cryptosystem is called symmetric-key (also called single-key, one-key, and

conventional) if for each key pair (e, d), the key d is 鈥渃omputationally easy鈥 to

determine knowing only e and similarly to determine e knowing only d. 2.1

Usually e = d with practical symmetric-key ciphers, thereby justifying the

use of the term symmetric-key.

There are two kinds of symmetric-key cryptosystems about which we will

learn in Section 2.2.

2.1 We will use the term 鈥渃omputationally easy problem鈥 to mean one that can be solved

in expected (in the probability sense) polynomial time and can be attacked using available

resources. (The reason for adding the latter caveat is to preclude problems that are of poly-

nomial time complexity but for which the degree is 鈥渓arge.鈥) The antithesis of this would

be a computationally infeasible problem, which means that, given the enormous amount of

computer time that would be required to solve the problem, this task cannot be carried out in

realistic computational time. Thus, 鈥渃omputationally infeasible鈥 means that, although there

(theoretically) exists a unique answer to our problem, we cannot ¬乶d it even if we devoted

every scintilla of the time and resources available. This is distinct from a problem that is

unsolvable in any amount of time or resources. For example, an unsolvable problem would be

to cryptanalyze XY Z assuming that it was enciphered using a monoalphabetic substitution.

There is simply no unique veri¬乤ble answer without more information. However, it should be

stressed here that there is no proved example of a computationally infeasible problem.

© 2007 by Taylor & Francis Group, LLC

2.1. De¬乶itions and Illustrations 87

We close this section with the following distinction between ciphers based

on the number of cipher alphabets.

N Monoalphabetic and Polyalphabetic Ciphers

A homophone is a ciphertext symbol that always represents the same plain-

text symbol. For instance, with the Caesar cipher in Table 2.1 (page 83), the

letter D is always the ciphertext for the plaintext letter a, so D is a homophone

in the monoalphabetic cipher known as the Caesar cipher. Here 鈥渕onoalpha-

betic鈥 means that there is only one cipher alphabet, which means the set of

ciphertext equivalents used to transform the plaintext. The row of ciphertext

equivalents below the plaintext in Table 2.1, for instance, is the cipher alphabet

for the Caesar cipher.

A polyphone is a ciphertext sym-

bol that always represents the same Biography 2.5 The title Father of

set of plaintext symbols, typically a Western Cryptography must go to Leon

set consisting of at most three plain- Battista Alberti (1404鈥“1472). Alberti

text symbols. With homophones was born on February 14, 1404, in

or polyphones, there is no option Genoa, Italy, and was the son of a

for change since the relationship be- wealthy banker, Lorenzo di Benedetto

tween plaintext and ciphertext is Alberti. Alberti was raised as Battista in

¬亁ed. However, a cipher is called Venice where the family moved shortly

polyalphabetic if it has more than after he was born. (He adopted the name

one cipher alphabet. In this type of Leon later in life.) At the age of ten,

cipher, the relationship between the he had already learned Latin and his

ciphertext substitution for plaintext father was teaching him mathematics.

symbols is variable. Thus, since His formal education was at the Uni-

each cipher alphabet (usually) em- versity of Bologna, where he ultimately

ploys the same symbols, a given earned a degree in law. However, he

symbol may represent several plain- quickly turned his interests to artistic

texts. and ultimately scienti¬乧 thought. Alberti

An example of a polyalphabetic not only taught himself music, became

cipher, the ¬乺st in history, is that in- an expert at playing the organ, and

vented by Leon Battista Alberti (see wrote sonnets, but also wrote on art,

Biography 2.5). criminology, sculpture, architecture, and

Alberti conceived of a disk with mathematics. In 1432, he went to Rome

plaintext letters and numbers on the where he became a secretary in the Papal

outer ring and ciphertext symbols Chancery, and he remained in the arms

on an inner movable circle. Alberti of church for the rest of his life. In

divided his ring and corresponding 1434, he went to Florence as part of the

circle into twenty-four equal seg- papal court of Eugenius IV. It was in

ments, called cells, each containing the papal secretariat that he became a

a symbol. A representation of Al- cryptographer.

berti鈥™s disk is pictured in Figure 2.1

on page 88. We have altered his

original presentation since he had ciphertext in lower case and plaintext in

upper case, the reverse of what we have as a convention.

© 2007 by Taylor & Francis Group, LLC

88 2. Cryptographic Basics

Figure 2.1: Alberti disk.

In Figure 2.1 the plaintext letter z is enciphered as V, so in this setting (one

of the twenty-six possible cipher alphabets) the plaintext zebra, for instance,

would be enciphered as VZLYD. However, there is nothing new at this juncture

that is any di¬erent from, say, the Caesar cipher with the cipher alphabet having

the letter c below the Z. Alberti had an idea, however (which is why he wanted

the inner circle to be able to rotate). This idea would revolutionize the forward

movement of cryptological development. After a random number of plaintext

words had been enciphered, usually three or four, Alberti would move the inner

disk to a new setting. Hence, he would now be using a new cipher alphabet.

Suppose that he moved the inner circle so that z sits over K. Then zebra would

be enciphered as KADTR, a new ciphertext for the same plaintext as above

since we have a new cipher alphabet. In fact, with his cipher disk, Alberti

invented the ¬乺st polyalphabetic cipher in history. However, he did even more.

Alberti had twenty letters, as depicted in Figure 2.1. This excludes the

letters h, k, and y, deemed to be unnecessary, and since j, u, and w were not

part of his alphabet, this left twenty letters. The inner circle consists of the

twenty-four letters of the Latin alphabet, put in the cells at random, including

&. The disk also included the numbers 1 through 4 in the outer ring of his

© 2007 by Taylor & Francis Group, LLC

2.1. De¬乶itions and Illustrations 89

original disk. In a book, he used these numbers in two-, three-, and four-digit

sets from 11 to 4444 yielding 336 = 42 + 43 + 44 codegroups. Beside each digit

he would write a phrase such as 鈥淪end in the troops鈥 for the number 21, say.

Then, with the setting in Figure 2.1, the code group 21 is enciphered as &P,

enciphered code. Alberti was the ¬乺st to discover it, and it is a testimony to his

being centuries ahead of his time that enciphered code, when it was rediscovered

at the end of the nineteenth century, was simpler than that of Alberti!

Exercises

In Exercises 2.1鈥“2.2, use the Caesar cipher described on page 83 to decrypt

the numeric ciphertext.

2.1. 22, 10, 7, 6, 11, 7, 11, 21, 5, 3, 21, 22.

(This is a quote by Julius Caesar himself when crossing the River Rubicon,

that delineated the frontier between Gaul and Italy proper. The quote

indicates the fact that he was virtually declaring war on Rome since his

military power was limited to Gaul. (See [88].))

2.2. 3, 16, 1, 21, 22, 11, 9, 15, 3, 25, 11, 14, 14, 6, 17, 22, 17,

4, 7, 3, 22, 3, 6, 17, 9, 15, 3.

(This is taken from Supers and Supermen (1920) by Philip Guedalla (1889鈥“

1944), a British writer.)

2.3. Polybius (see Biography 2.6 on page 90) invented a substitution cipher by

enciphering letters into pairs of numbers as follows.

The Polybius Square

1 2 3 4 5

1 a b c d e

2 f g h ij k

Table 2.3

3 l m n o p

4 q r s t u

5 v w x y z

Label a ¬乿e-by-¬乿e square with the numbers 1 through 5 for the rows and

columns, and string the English alphabet through the rows, considering

鈥渋j鈥 as a single letter, as given in Table 2.3.

Then, look at the intersection of any row and column (with row number

listed ¬乺st and column number listed second) as the representation of the

letter in question. For instance, k is 25 and q is 41. Hence, the letters

are plaintext and the numbers are ciphertext. This device is called the

Polybius checkerboard or Polybius square.

Use the Polybius square to decrypt the numeric ciphertext given by

4434 3111123442 2443 4434 35421154.

© 2007 by Taylor & Francis Group, LLC

90 2. Cryptographic Basics

(This is the motto of the Benedictine Order.)

Using the Polybius square de¬乶ed in Exercise 2.3, decipher the numeric ci-

phertexts given in Exercises 2.4鈥“2.8.

2.4. 331513154343244454 323444231542 3421 243351153344243433

(This is a quote from Love in a Wood, Act III, scene iii, (1671) by the

English dramatist Williiam Wycherley (ca. 1640鈥“1716).)

2.5. 2134421315 52244423344544 32243314 2111313143 1254 244443

345233 521524222344 (This is a quote from Odes Book 3 (23 B.C.) by

Horace (Quniton Horatius Flaccus) (65鈥“8 B.C.), a Roman poet.)

2.6. 33344423243322 4533141542 442315 434533 2443

11131324141533441131

(This is a quote from Emilia Galotti, Act iv, (1772) by Gotthold Ephraim

Lessing (1729鈥“1781), German critic and dramatist.)

Biography 2.6 Polybius, who lived approximately from 200 to 118 B.C., was

a Greek historian and statesman. Polybius鈥™ intended use of his square was to

send messages great distances by means of torches and hilltops. The sender

would hold a torch in each hand, then raise the torch in the right hand the

number of times to signal the row, and the torch in the left hand the number of

times to signal the column. There is no evidence that these were actually used in

this fashion or any other in ancient Greece. However, there are many variations

of his cipher that have been constructed. The reader may even concoct one by

. 17 |