ńņš. 1 |

History and Basic

Cryptographic Concepts

For secrets are edged tools, and must be kept from children and from fools.

John Dryden (1631ā“1700) English poet, critic, and playwright

1.1 Terminology

In The Lives of the Twelve Caesars [226, p. 45], Suetonius writes of Julius

Caesar: ā... if there was occasion for secrecy, he wrote in cyphers; that is, he

used the alphabet in such a manner, that not a single word could be made out.

The way to decipher those epistles was to substitute the fourth for the ļ¬rst

letter, as d for a, and so for the other letters respectively.ā

What is being described in the above is a means of sending messages in dis-

guised form ā” an example of enciphering or encrypting, which is the process of

disguising messages. The original (undisguised) message is called the plaintext or

(less often) cleartext, and the disguised message is called the ciphertext, whereas

the ļ¬nal message, encapsulated and sent, is called a cryptogram. The reverse

process of turning ciphertext into plaintext is called decryption or deciphering,

or (less frequently used) exploitation. The science of cryptography is the study

of sending messages in secret, namely, in enciphered form, so that only the in-

tended recipient can decipher and read it. The study of mathematical techniques

for attempting to defeat cryptographic methods is called cryptanalysis. Those

engaged in cryptography are called cryptographers, whereas those engaged in

cryptanalysis are called cryptanalysts ā” the āenemyā or āopponentā. Although

cryptography is sometimes called an art in the contemporary literature, we re-

serve the term science for modern cryptography, which is concerned with the

mathematical techniques that are embraced by the study and the computa-

tional tools used to implement them. Certainly from a historical perspective

1

Ā© 2003 by CRC Press LLC

2 1. History and Basic Cryptographic Concepts

(as we will see shortly) cryptography began as an art in the course of human

development, but is now a very serious science in our information-based society.

The study of both cryptography and cryptanalysis is called cryptology and the

practitioners of cryptology are called cryptologists. The etymology of cryptology

is the Greek kryptos meaning hidden and logos meaning word. The term cryp-

tology was coined by James Howell in 1645. However, John Wilkins (1614ā“1672)

in his book, Mercury, or the Secret and Swift Messenger, introduced into the

English language the terms cryptologia or secrecy in speech, and cryptographia or

secrecy in writing. He also used cryptomeneses as a general term for any secret

communications. Wilkins, who was a cofounder of the Royal Society along with

John Wallis (1616ā“1703), later married Oliver Cromwellā™s sister, and became

Bishop of Chester. The appearance of the use of the word cryptology is prob-

ably due to the advent of Kahnā™s encyclopedic book [117], The Codebreakers,

published in 1967, after which the term became accepted and established as

that area of study embracing both cryptography and cryptanalysis.

Cryptography may be viewed as overt secret writing in the sense that the

writing is clearly seen to be disguised. This is diļ¬erent from steganography (from

the Greek steganos meaning impenetrable) which conceals the very existence of

the message, namely, covert secret writing. For instance, invisible ink would be

called a technical steganographic method, whereas using tiny dissimilarities be-

tween handwritten symbols is a linguistic use of steganography. One of the most

famous of the technical steganographic methods, employed by the Germans dur-

ing World War II, was the use of the microdot (invented by Emanuel Goldberg

in the 1920s) as a period in typewritten documents. Today, hiding messages in

graphic images would also qualify. Generally speaking, steganography involves

the hiding of secret messages in other messages or devices. The modern conven-

tion is to break cryptography into two parts: cryptography proper or overt secret

writing, and steganography or covert secret writing. The term steganography ļ¬rst

appeared in the work Steganographia, by Johannes Trithemius (1462ā“1516). We

will not be concerned in this text with steganography, but rather with cryptog-

raphy proper. (See [16] for more data on Steganography.)

The ļ¬rst recorded instance of a cryptographic technique was literally written

in stone almost four millennia ago by an Egyptian scribe who used hieroglyphic

symbol substitution in his writing on a rock wall in the tomb of a nobleman

of the time, Khnumhotep. The intention was not to disguise the inscription,

but rather to add some measure of majesty to his inscription of the noble-

manā™s deeds, which included the erection of several monuments for the reigning

Pharaoh Amenemhet II. Although the scribeā™s intent was not secrecy (the pri-

mary goal of modern cryptography), his method of symbol substitution was one

of the elements of cryptography that we recognize today. Today the use of sub-

stitutions without the element of secrecy is called protocryptography. Subsequent

scribes actually added the essential element of secrecy to their hieroglyphic sub-

stitutions. However, the end-goal here seems to have been to provide a riddle

or puzzle. As these inscriptions became more complex, this practice abated and

suļ¬ered the same fate as the inhabitants of the tombs. Hence, the seeds of

cryptology were planted in ancient Egypt but did not mature rapidly or contin-

Ā© 2003 by CRC Press LLC

1.1. Terminology 3

uously. Instead cryptography had several incarnations in various cultures, with

probably fewer methods extant than the number lost in antiquity.

We will now continue with the description of cryptographic terms and re-

fer the reader to [117] for an encyclopedic history of cryptography, or to this

authorā™s previous book [165] for a very brief overview.

At the outset, we had a glimpse of a cryptographic means invented by Julius

Caesar, which we can illustrate as follows. For now we may think of a cipher as

a means of transforming plaintext into ciphertext. This is often visualized as a

table consisting of plaintext symbols together with their ciphertext equivalents,

where the convention is that plaintext letters are written in lower case, and

ciphertext letters are written in upper case.

Table 1.1 The Caesar Cipher

Plain a b c d e f g h i j k l m

Cipher D E F G H I J K L M N O P

Plain n o p q r s t u v w x y z

Cipher Q R S T U V W X Y Z A B C

We see that each plaintext letter is substituted by the ciphertext letter three

places to the right in the alphabet with X, Y, and Z ālooping backā to A, B, and

C. A mathematically more satisfying way to display this is to give the letters

numerical values as follows.

a b c d e f g h i j k l m

0 1 2 3 4 5 6 7 8 9 10 11 12

Table 1.2

n o p q r s t u v w x y z

13 14 15 16 17 18 19 20 21 22 23 24 25

We can transform plaintext into numerical values and visualize the Caesar

Cipher in terms of modular arithmetic. If Ī± is the numerical equivalent of a

plaintext letter, then Ī² ā” Ī± + 3 (mod 26) is the ciphertext letter substituted for

it. (See Appendix C for a reminder of the arithmetic of congruences.) To deci-

pher, take each ciphertext numerical equivalent Ī², perform Ī± ā” Ī² ā’ 3 (mod 26),

and convert back to the letter equivalents via Table 1.2 to recover the plaintext.

For instance, suppose that the following was encrypted using the Caesar Cipher:

IOHH DW GDZQ.

Then the numerical equivalents of these ciphertext letters are:

8, 14, 7, 7, 3, 22, 6, 3, 25, 16.

By calculating Ī± ā” Ī² ā’3 (mod 26) on each one, we get the numerical equivalents

of the plaintext letters:

5, 11, 4, 4, 0, 19, 3, 0, 22, 13.

Then translating them back to letters via Table 1.2, we get the plaintext:

Ā© 2003 by CRC Press LLC

4 1. History and Basic Cryptographic Concepts

ļ¬‚ee at dawn.

The reader may now solve the related Exercises 1.1ā“1.8.

With the Caesar Cipher, a given plaintext letter is enciphered as the same

ciphertext letter each time the cipher is used. This is an example of a monoal-

phabetic substitution cipher, which we will formally deļ¬ne in Section 1.2. This

predictability makes this type of cipher very vulnerable to attack. We will dis-

cuss various attacks in Section 1.3. For now, we may think of a substitution

as a permutation of the plaintext letters, and a monoalphabetic cipher as one

in which only one cipher alphabet is used, where the term ācipher alphabetā

means a list of equivalents used to transform plaintext into secret form, as in

Table 1.1. (See Exercises 1.9ā“1.14.)

The above illustration is a motivator for some deļ¬nitions of cryptographic

terminology. However, before we can do this, we need to provide a basis of

rigorous mathematical language from which we can launch a discussion of cryp-

tography in depth. Both the plaintext and the ciphertext for any given cipher

are written in terms of elements from a ļ¬nite set A, called an alphabet of def-

inition, which may consist of letters from an alphabet such as English, Greek,

Hebrew, or Russian, and may include symbols such as:

ā,ā,ā,āŗ,n,,ā”,ā,ā,,āŖ,ā,v,ā,ā¦,ā‘,ā,o, ā, ā, ā«, Ā¤, ā, ā,ā¹,

or any other symbols that we choose to use when sending messages. Although

the alphabets of deļ¬nition for the plaintext and the ciphertext may diļ¬er, the

usual practice is to use the same for both. A commonly used one is A =

{0, 1}, the binary alphabet of deļ¬nition. There is also the alphabet of deļ¬nition

consisting of A = {0, 1, 2, . . . , 25} ā” the alphabet of deļ¬nition for the Caesar

Cipher.

Once we have an alphabet of deļ¬nition, we choose a message space M, which

is deļ¬ned to be a ļ¬nite set consisting of strings of symbols from the alphabet

of deļ¬nition, and elements of M are called plaintext message units. A ļ¬nite

set C, consisting of strings of symbols from the alphabet of deļ¬nition for the

ciphertext, is called the ciphertext message space and elements from C are called

ciphertext message units. For instance, for the Caesar Cipher, M = C = Z/26Z,

the ring of integers modulo 26. (See Appendix C for general number theoretic

facts.)

Next, we need to foil cryptanalysts, so we need a set of parameters K, called

the keyspace, the elements of which are called keys. For example, with the

Caesar Cipher, 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 c ā C. The deciphering key is also the parameter k = 3

since we achieve m ā M from c ā C by

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

Ā© 2003 by CRC Press LLC

1.1. Terminology 5

This motivates the following, which will also give rigour to the preceding dis-

cussion.

Deļ¬nition 1.3 (Enciphering and Deciphering Functions)

An enciphering transformation or enciphering function is a one-to-one func-

tion

Ee : M ā’ C,

where the enciphering key e ā K uniquely determines Ee acting upon the plain-

text message units m ā M to get ciphertext units Ee (m) = c ā C. A deciphering

transformation or deciphering function is a one-to-one function

Dd : C ā’ M,

which is uniquely determined by a given decryption key d ā K acting upon

ciphertext message units c ā C to get plaintext message units Dd (c) = m.

The operation of applying Ee to m is called enciphering, or encrypting,

whereas the operation of applying Dd to c is called deciphering, or decrypting.

Remark 1.4 This remark is devoted to a discussion of distinctions between

encoding/decoding and enciphering/deciphering. We may think of ācodesā as

transformations that replace the words and phrases in the plaintext with alpha-

betic or numeric code groups. (For instance, a code for Launch the attack!

might be L ā’ 343.) Historically, the ļ¬rst code vocabularies were called nomen-

clatures, which consisted of plaintext corresponding to (order-preserving) literal

or numerical codegroups. This required only one codebook, a one-part code. The

notion of a two-part nomenclature was introduced by A. Rossignal (1600ā“1682).

For the ļ¬rst part, he used what was called a tables ` chiļ¬er, consisting of plain-

a

text letters in alphabetical order, and ciphertext letters in random order. The

second part, called a tables ` dĀ“chiļ¬er, consisting of the plaintext letters jum-

ae

bled, while the ciphertext letters were in alphabetical order, what we now call a

two-part code (see Footnote 1.5 on page 14). Later these nomenclatures were

expanded into what were called repertories, then ultimately codes. We use the

term cryptographic codes in the above context in order to avoid confusion with

error-correcting codes that detect or correct errors to ensure messages transmit-

ted over a noisy channel are recovered intact, which involves no secrecy.

The distinction between encoding and enciphering, for example, is that en-

ciphering transformations applied to plaintext units result in ciphertext units,

done independent of the meaning of the plaintext. On the other hand, cryp-

tographic encoding means that words, for instance, are replaced by codegroups.

The key is the codebook, which lists the plaintext units and their corresponding

codegroups. Cryptographic codes are not used for modern communications since

they are, by their very nature, open to what is called a known-plaintext attack

ā” see Section 1.3. This means that the key ā” the codebook ā” would have to be

replaced often. In the modern world, the time and money this would cost renders

this means of securing transmissions unacceptable for most applications.

Ā© 2003 by CRC Press LLC

6 1. History and Basic Cryptographic Concepts

Deļ¬nition 1.3 has given us another building block in our quest for the nec-

essary mathematical precision to carry out our exploration of cryptographic

concepts in depth, and has given rigour to the somewhat informal discussion

that has gone before. We now can illustrate the Caesar Cipher in light of our

new notions.

The key e, which is addition of 3 modulo 26, uniquely determines the en-

ciphering transformation Ee (m) ā” c ā” m + 3 (mod 26), namely, Ee (m) = c =

m + 3 ā C = Z/26Z. Also, the key d, subtraction of 3 modulo 26, uniquely

determines the deciphering transformation Dd (c) ā” m ā” c ā’ 3 (mod 26), which

is the same as saying Dd (c) = m = c ā’ 3 ā Z/26Z. We also make the very im-

portant observation that Dd (Ee (m)) = m, and Ee (Dd (c)) = c. In other words,

ā’1

Dd is the the inverse function of Ee , which we denote by Dd = Ee . This is the

crucial relationship between enciphering and deciphering functions that allows

us to deļ¬ne the term cipher in more precise mathematical terms.

Deļ¬nition 1.5 (Cryptosystems)

A cryptosystem or cipher is comprised of a set {Ee : e ā K} of enciphering

ā’1

functions and a set {Dd = Ee : d ā K} of deciphering functions, which corre-

sponds to the former set in such a way that for each e ā K, there exists a unique

ā’1

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

Individually e and d are called keys, and (e, d) is called a key pair. The set of

pairs {(m, Ee (m)) : m ā M} is called a cipher table.

The following illustrates a generic cryptosystem.

Diagram 1.6 An Illustrated Cryptosystem

ā ā

Encryption Decryption

Key Key

ā ā ā ā

ļ£¦ ļ£¦

ļ£¦e ļ£¦

d

Encryption Decryption

P laintext

m ā M ā’ Ee (m) = c ā’ Dd (c) = m

ENCIPHER DECIPHER

Remark 1.7 The reader is cautioned that there is not a general consensus in

the literature about the use of the term cipher. Some sources use the term as

we have in Deļ¬nition 1.5, whereas others use it to mean what we have called

a cipher table. Moreover, at least in practice, the term ācipherā and ācipher

tableā are used synonymously. We will use the terms ācipherā and ācryptosys-

temā interchangeably to mean the notion given in Deļ¬nition 1.5, whereas we

Ā© 2003 by CRC Press LLC

1.1. Terminology 7

reserve the term ācipher tableā as deļ¬ned therein. Thus, the cipher table for

the Caesar Cipher is Table 1.1, for instance, whereas the Caesar Cipher is the

system of enciphering and deciphering transformations discussed above. More-

over, Deļ¬nition 1.5 provides a formal mathematical formulation of the terms

cipher and key used informally in the previous discussion.

Now a natural question (and one that is central to the main theme of this

book) is to ask about the distinctions (or lack thereof) between the enciphering

and deciphering keys. The following is the ancestor of the type of cryptosystem

that will dominate the discussions in the balance of the chapters.

Deļ¬nition 1.8 (Symmetric-Key Cryptosystems)

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

ventional) if for each key pair (e, d), the key d is ācomputationally easyā to

determine knowing only e, and similarly e is easy to determine knowing only d.

In practical symmetric-key cryptosystems, we usually have that e = d, thus

justifying the term āsymmetric-keyā.

Remark 1.9 We will use the term ācomputationally easy problemā to mean

one that can be solved in expected polynomial time and can be attacked using

available resources (the reader unfamiliar with these terms may ļ¬nd them in

Appendix B on complexity issues). The reason for adding the caveat on attacks

is to preclude problems that are of polynomial time complexity but for which the

degree is ālargeā. 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 real-

istic computational time. Therefore, ācomputationally infeasibleā means that,

although there (at least theoretically) exists a unique answer to the problem, we

could not ļ¬nd it even if we devoted every scintilla of the time and resources

available. Note that this is distinct from a problem that is unsolvable with any

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

cryptanalyze ABC, assuming that it was encrypted using a monoalphabetic sub-

stitution. There is simply no unique veriļ¬able answer without more information.

However, the bottom line is that there is no proven example of a computationally

infeasible problem (see Footnote B.9 on page 211).

Symmetric-key ciphers come in two ļ¬‚avours. The ļ¬rst is described as follows.

Deļ¬nition 1.10 (Block Ciphers)

A block cipher is a cryptosystem which separates the plaintext message into

strings of plaintext message units, called blocks, of ļ¬xed length k ā N, called the

blocklength and enciphers one block at a time.

Ā© 2003 by CRC Press LLC

8 1. History and Basic Cryptographic Concepts

The Caesar Cipher is a block cipher where the enciphering key e (addition

of 3 modulo 26) is ā’d where d is the deciphering key (subtraction of 3 modulo

26) and the blocklength is k = 1.

More generally, we have the following.

Deļ¬nition 1.11 (Shift Ciphers)

A shift cipher consists of the following. The enciphering function is given

by

Ee (m) ā” c ā” m + b (mod n)

for any b, n ā N where m ā M = Z/nZ and c ā C, which is the same as saying

Ee (m) = c = m + b ā Z/nZ = C.

The deciphering transformation is given by

Dd (c) ā” m ā” c ā’ b (mod n),

or simply

Dd (c) = m = c ā’ b ā Z/nZ.

Hence, the shift cipher is a symmetric-key cipher with d = ā’e since e is

the addition of b modulo n, and d = ā’e is the subtraction of b modulo n, the

additive inverse of e. This is an example of a block cipher of length k = 1.

The Caesar Cipher is the special case obtained by taking b = 3 and n = 26.

Also, for fans of the Stanley Kubrick ļ¬lm 2001: A Space Odyssey, take b = ā’1

and n = 26, from which HAL is deciphered as IBM. Note that shift ciphers are

vulnerable to letter frequency analysis (see Appendix B on page 205).

The above provides a warm-up for the discussion of classical ciphers in Sec-

tion 1.2, where we will discuss generalizations of the shift cipher. Before we can

look at the second type of symmetric-key cipher, we need the following notion.

Deļ¬nition 1.12 (Keystreams, Seeds, and Generators)

If K is the keyspace for a set of enciphering transformations, then a sequence

k1 k2 Ā· Ā· Ā· ā K is called a keystream. A keystream is either randomly chosen, or

is generated by an algorithm, called a keystream generator, which generates

the keystream from an initial small input keystream called a seed. Keystream

generators that eventually repeat their output are called periodic.

Remark 1.13 The term ārandomnessā is not easy to deļ¬ne precisely, and could

consume numerous pages to discuss (see Knuth [123, 149ā“189]). However, it

suļ¬ces to say that since computers are ļ¬nite state devices, then any random-

number generator on a computer must be periodic, which means it is predictable,

so not truly random. Hence, the most one can expect from computer, generating

sequences of bits (bitstrings) say, is pseudorandomness. Thus, by a pseudoran-

dom generator we will mean a deterministic algorithm that takes a short random

Ā© 2003 by CRC Press LLC

1.1. Terminology 9

seed and expands it into a bitstring for which it is computationally infeasible

(see Remark 1.9) to tell the diļ¬erence from a truly random bitstring. However,

keystreams so generated must be cryptographically secure, which means that

they must satisfy the additional property that, for a given output bit, the next

output bit must be computationally infeasible to predict, even given knowledge

of all previous bits, knowledge of the algorithm being used, and knowledge of

the hardware. Since these issues are not of concern to us herein, we will as-

sume that we have a cryptographically secure pseudorandom number generator

for our keystream, or a truly randomly chosen keystream, and proceed with our

discussion of cryptographic techniques.

Deļ¬nition 1.14 (Stream Ciphers)

Let K be a keyspace for a cryptosystem and let k1 k2 Ā· Ā· Ā· ā K be a keystream.

This cryptosystem is called a Stream Cipher if encryption upon plaintext strings

m1 m2 Ā· Ā· Ā· is achieved by repeated application of the enciphering transformation

on plaintext message units,

Ekj (mj ) = cj ,

and deciphering occurs as

Dkj (cj ) = mj

for j ā„ 1. If there exists an ā N such that kj+ = kj for all j ā N, then we

say that the Stream Cipher is periodic with period .

Perhaps the most famous example of a stream cipher is the following, wherein

ā• denotes addition modulo 2, also called XORing.

x The Vernam1.1 Cipher

The Vernam Cipher is a Stream Cipher with alphabet of deļ¬nition A = {0, 1}

that enciphers in the following fashion. Given a bitstring m1 m2 Ā· Ā· Ā· mn ā M,

and a keystream k1 k2 Ā· Ā· Ā· kn ā K, the enciphering transformation is given by

Ekj (mj ) = mj ā• kj = cj ā C,

and the deciphering transformation is given by

Dkj (cj ) = cj ā• kj = mj .

1.1 Gilbert S. Vernam was born in Brooklyn, New York, and was a graduate of Massachusetts

College. Within a year of graduating, he joined the American Telegraph and Telephone

Company (AT&T). After a year of working for AT&T, he married Alline Eno, and they had

one child together. On December 17, 1917, he wrote down the cipher for which he has earned

the title of the Father of Automated Cryptography. This was the ļ¬rst Polyalphabetic Cipher

automated using electrical impulses. Throughout his life, he was granted sixty-ļ¬ve patents,

including the fully automated telegraph switching system, and he even invented one of the

ļ¬rst versions of a binary digital enciphering of pictures. However, for all his accomplishments,

he died in relative obscurity on February 7, 1960 in Hackensack, New Jersey after years of

battling Parkinsonā™s disease.

Ā© 2003 by CRC Press LLC

10 1. History and Basic Cryptographic Concepts

The keystream (pad) is randomly chosen and never used again. For this reason,

the Vernam Cipher is also called the one-time pad.

We could have used a diļ¬erent alphabet of deļ¬nition such as Z/nZ, but

since we convert to binary on a computer, we may as well stick with the binary

alphabet. See Exercise 1.15, for instance, to see that we can essentially use

Z/26Z as with the Caesar Cipher, even though our alphabet of deļ¬nition is

binary. The big drawback to the Vernam Cipher is that the keylength (the

number of characters in the key) and plaintext length are the same. This creates

key management problems so the Vernam Cipher usually is employed only for

the most sensitive transmission of data such as missile launch ācodesā.

Example 1.15 Assume that the following bitstring is a randomly chosen key

for the one-time pad:1.2

k = (11001010001100111100010101110001011111110101010001).

Also, assume that the following was enciphered using k:

c = (10111001011110101111000101000001111100000101010010).

Then to ļ¬nd the the plaintext string, we perform addition modulo 2 on k + c:

(11001010001100111100010101110001011111110101010001) +

(10111001011110101111000101000001111100000101010010) =

(01110011010010010011010000110000100011110000000011) = m

A one-time pad can be shown to be theoretically unbreakable. In 1949 with

Shannonā™s development [205] of perfect secrecy the one-time pad was proved to

be unbreakable, something assumed to be true for a long time prior to the proof.

It is known that the revolutionary, Che Guevara, used a version of the Ver-

nam Cipher in base ten with additions and subtractions carried out by hand.

In 1967 the Bolivian army captured and executed him. On his body they found

some handwritten pages detailing how he created cryptograms for transmission

to Fidel Castro. Guevara used numerical equivalents of his plaintext, written

in Spanish, as decimal numbers of one or two digits according to a ļ¬xed cipher

table. The key was a random sequence of digits known only to Guevara and

Castro. The plaintext message was then added to the key (without carries) and

this produced the cryptogram, a process now called the Guevara Cipher.

Also, inspired by the Cuban missile crisis of the 1960s, a hot-line between

Washington and Moscow was established that used what they called the one-

time tape, which was a physical manifestation of the Vernam Cipher. In the

United States, this took the form of the ETCRRM II or Electronic Teleprinter

that the base b ā N representation of an integer is given by (atā’1 atā’2 . . . a1 a0 )b =

1.2 Recall

tā’1

where t ā N, atā’1 = 0, and 0 ā¤ aj ā¤ b ā’ 1 for 0 ā¤ j ā¤ t ā’ 1. We often suppress

j

j=0 aj b

the binary subscript for convenience as in our example above. See Exercises 1.17ā“1.22.

Ā© 2003 by CRC Press LLC

1.1. Terminology 11

Cryptographic Regenerative Repeater Mixer II. The one-time tape worked via the

existence of two magnetic tapes, one at the enciphering source, and one at the

deciphering end, both having the same keystream on them. To encipher, they

performed addition modulo 2 with the plaintext and the bits on the tape. To

decipher, the receiver performed addition modulo 2 with the ciphertext and the

bits on the (identical) tape at the other end. Thus, they had instant deciphering

and perfect secrecy as long as they used truly random keystreams, each was used

only once, and the tapes were destroyed after each use. Today, one-time pads

are in use for military and diplomatic purposes when unconditional security is

of the utmost importance.

We now have suļ¬cient framework with which to work, so we turn to the

next section for a description of some classical ciphers.

Exercises

In Exercises 1.1ā“1.8, determine the plaintext from the given ciphertext using

the Caesar Cipher 1.1.

L WKLQN WKHUHIRUH L DP

1.1.

IURP RQH OHDUQ WR NQRZ DOO

1.2.

EHKROG WKH VLJQ

1.3.

WKLV LV KDUG ZRUN

1.4.

QRQ VHTXLWXU

1.5.

WUXWK LV PLJKWB DQG ZLOO SUHYDLO

1.6.

WUXWK FRQTXHUV DOO WKLQJV

1.7.

WKH HQG FURZQV WKH ZRUN

1.8.

1.9. The following is a cipher for a monoalphabetic substitution.

Plain a b c d e f g h i j k l m

Cipher M L O P R Q T S N W U V Z

Plain n o p q r s t u v w x y z

Cipher Y X C B A F E D G K J I H

Using this cipher, decrypt the following:

KMA NF NZZNYRYE

In Exercises 1.10ā“1.14, use the cipher given in Exercise 1.9 to decipher

each of the ciphertext messages as follows.

Ā© 2003 by CRC Press LLC

12 1. History and Basic Cryptographic Concepts

YX FDOS MTRYOI

1.10.

YRGRA FMI MYIESNYT

1.11.

QNAR MYP NOR

1.12.

GMYNEI

1.13.

KR MAR PXYR

1.14.

1.15. Interpret the plaintext solution m to Example 1.15 as a bitstring that is the

concatenation of bitstrings of length 5, each corresponding to an English

letter equivalent given in decimal form by Table 1.2. Find the English text

equivalent of the bitstring. For instance, the ļ¬rst such bitstring, 01110, is

14 in decimal, which is O from Table 1.2. Proceed from there to the full

English plaintext.

1.16. Given the key

k = (11010111101111010101111011101011010)

for the one-time pad, and ciphertext

c = (01001011111011010000101101111001000),

determine the plaintext m and interpret it as the concatenation of bit-

strings of length 5, each corresponding to an English letter equivalent

given in decimal form by Table 1.2. Find the English text equivalent of

the bitstring.

(For instance, the sum modulo 2 of the ļ¬rst ļ¬ve bits of k and c is

11010 + 01001 = 10011,

which is binary for the decimal 19. In Table 1.2, 19 corresponds to the let-

ter T. Continue in this fashion for the modulo 2 additions of each remain-

ing ļ¬ve-bit integer in k and c to decipher the balance of the cryptogram.)

In Exercises 1.17ā“1.22, use the key k given in Exercise 1.16 and the ci-

phertext given in each of these following exercises to determine the English

equivalents of the plaintext by the method outlined in Exercise 1.16.

1.17. c = (10010100111110111011010011101101001).

1.18. c = (01000110101110000100110010100101000).

1.19. c = (11010100111110111110101011111001000).

1.20. c = (11001110101110010001101010111111110).

1.21. c = (11111100000111110001010001111001011).

1.22. c = (11010101011010111011110000111001000).

Ā© 2003 by CRC Press LLC

1.2. Classical Ciphers 13

1.2 Classical Ciphers

We shall see that cryptography is more than a subject permitting mathemati-

cal formulation, for indeed it would not be an exaggeration to state that abstract

cryptography is identical with abstract mathematics.

A.A. Albert1.3

Perhaps the best known classical cipher is the Caesar Cipher described in

Section 1.1. We demonstrated how this cipher is a special case of a shift cipher.

As it turns out, shift ciphers are special cases of the following concept.

x Aļ¬ne Ciphers

An Aļ¬ne Cipher is deļ¬ned as follows. Let M = C = Z/nZ, n ā N,

K = {(a, b) : a, b ā Z/nZ and gcd(a, n) = 1},

and for e, d ā K, and m, c ā Z/nZ, set

Ee (m) ā” am + b (mod n), and Dd (c) ā” aā’1 (c ā’ b) (mod n).

Example 1.16 Let n = 26 and M = C = Z/26Z. Deļ¬ne an Aļ¬ne Cipher as

follows.

Ee (m) = 5m + 7 = c ā M.

Since 5ā’1 ā” 21 (mod 26), then

Dd (c) = 21(c ā’ 7) = 21c + 9 ā M.

We want to encipher and send the following message:

launch the missles.

To do this, we get the numerical equivalents for the letters from Table 1.2 on

page 3:

11, 0, 20, 13, 2, 7, 19, 7, 4, 12, 8, 18, 18, 8, 11, 4, 18.

Then apply Ee to each value of m to get:

10, 7, 3, 20, 17, 16, 24, 16, 1, 15, 21, 19, 19, 21, 10, 1, 19.

1.3 Abraham Adrian Albert (1905ā“1972) was born in Chicago, Illinois on November 9, 1905,

and remained in Chicago most of his life. He studied under L. E. Dickson at the University of

Chicago receiving his Ph.D. in 1928 for his dissertation entitled Algebras and Their Radicals

and Division Algebras. His impressive work in classifying division algebras earned him a

National Research Council Fellowship, which allowed him to obtain a postdoctoral position

at Princeton. After that he spent a couple of years at Columbia University, then returned to

the University of Chicago in 1931. Albertā™s book Structure of Algebras, published in 1939,

remains a classic to this day. His work on algebras earned him the Cole Prize in that same

year. World War II induced Albert to take an interest in cryptography. In fact, the quote

given above is taken from his lecture on mathematical aspects of cryptography at the American

Mathematical Society meeting held in Manhattan, Kansas on November 22, 1941. His honours

and awards are too numerous to list here, but it is clear that he had a lasting inļ¬‚uence. He

died on June 6, 1972 in Chicago.

Ā© 2003 by CRC Press LLC

14 1. History and Basic Cryptographic Concepts

Then we use Table 1.2 to get the ciphertext English equivalents:

KHDURQ YQB PVTTVKBT,

which is sent as the cryptogram. The reader may now verify that Dd (c) yields

the original plaintext. (See Exercises 1.23ā“1.28.)

In turn, Aļ¬ne Ciphers are special cases of the following notion. Recall ļ¬rst

that a permutation Ļ on a ļ¬nite set S is a bijection on S; namely, Ļ is a one-to-one

and onto function on S.

Deļ¬nition 1.17 (Substitution Ciphers)

Let A be an alphabet of deļ¬nition consisting of n symbols, and let M be the

set of all blocks of length r over A. The keyspace K will consist of all ordered

r-tuples e = (Ļ1 , Ļ2 , . . . , Ļr ) of permutations Ļj on A. For each e ā K, and

m = (m1 m2 . . . mr ) ā M, let

Ee (m) = (Ļ1 (m1 ), Ļ2 (m2 ), . . . , Ļr (mr )) = (c1 , c2 , . . . , cr ) = c ā C,

ā’1 ā’1

and for d = (d1 , d2 , . . . , dr ) = (Ļ1 , Ļ2 , . . . , Ļr ) = eā’1 ,

ā’1

ā’1 ā’1 ā’1

Dd (c) = (d1 (c1 ), d2 (c2 ), . . . , dr (cr )) = (Ļ1 (c1 ), Ļ2 (c2 ), . . . , Ļr (cr )) = m.

This type of cryptosystem is called a substitution cipher. If all keys are the

same, namely, Ļ1 = Ļ2 = Ā· Ā· Ā· = Ļr , then this cryptosystem is called a simple

substitution cipher or monoalphabetic substitution cipher. If the keys diļ¬er,

then it is called a polyalphabetic substitution cipher.

Deļ¬nition 1.17 gives the promised formal interpretation of the notions that

we discussed in Section 1.1 wherein we gave examples of monoalphabetic block

ciphers such as the Caesar Cipher, and polyalphabetic stream ciphers such as

the Vernam Cipher ā” one-time pad.1.4 Another classical polyalphabetic block

cipher is given as follows.

x Vigen`re1.5 Cipher

e

Fix r, n ā N, and let M = C = (Z/nZ)s , the elements of which are ordered

s-tuples from Z/nZ, and K = Zr where s ā„ r. For

e = (e1 , e2 , . . . , er ) ā K, and m = (m1 , m2 , . . . , ms ) ā M,

1.4 The Vernam Cipher was, in fact, the ļ¬rst polyalphabetic substitution cipher that was

automated using electrical impulses, wherein each 5-bit key value determined one of thirty-

two ļ¬xed alphabetic substitutions.

1.5 Blaise de Vigen`re (1523ā“1596), while on a diplomatic mission to Rome in his mid-

e

twenties, ļ¬rst came into contact with cryptology at the Papal Cevria. This inspired him

to read the books by the pioneers Alberti, Belaso, Cardano, Porta, and Trithemius. One of

the books that Vigen`re wrote, TraictĀ“ des Chiļ¬res published in 1586, contains the ļ¬rst dis-

e e

cussion of plaintext and ciphertext autokey systems. However, it was not until the seventeenth

century that two-part ācodesā were used (see Remark 1.4 on page 5). The ļ¬rst to actually put

them into practice were Kings Louis XIII and Louis XIV of France. Vigen`re died of throat

e

cancer in 1596.

Ā© 2003 by CRC Press LLC

1.2. Classical Ciphers 15

let Ee (m) = (m1 + e1 , m2 + e2 , . . . , mr + er , mr+1 + e1 , . . . , ms + esā’kr ), for some

integer k, and let Dd (c) = (c1 ā’ e1 , c2 ā’ e2 , . . . , cr ā’ er , cr+1 ā’ e1 , . . . , cs ā’ esā’kr ),

for c = (c1 , c2 , . . . , cs ) ā C, where + is addition, and ā’ is subtraction, modulo

n. This cryptosystem is called the Vigen`re Cipher with period s. If r = s,

e

then this cipher is often called a Running-key Cipher. For the case r = s see

Example 1.24.

The Vigen`re Cipher is symmetric-key, given that knowing e is tantamount

e

to knowing d. It is a Block Cipher with blocklength r, and it is polyalphabetic

if we ensure that not all the keys ej for j = 1, 2, . . . , r are the same.

There is an easy means of visualizing the Vigen`re Cipher when we use

e

n = 26 and the English alphabet via Table 1.2, as follows.

`

THE VIGENERE TABLEAU

a b c d e f g h i j k l m n o p q r s t u v w x y z

a A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

b B C D E F G H I J K L M N O P Q R S T U V W X Y Z A

c C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

d D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

e E F G H I J K L M N O P Q R S T U V W X Y Z A B C D

f F G H I J K L M N O P Q R S T U V W X Y Z A B C D E

g G H I J K L M N O P Q R S T U V W X Y Z A B C D E F

h H I J K L M N O P Q R S T U V W X Y Z A B C D E F G

i I J K L M N O P Q R S T U V W X Y Z A B C D E F G H

j J K L M N O P Q R S T U V W X Y Z A B C D E F G H I

k K L M N O P Q R S T U V W X Y Z A B C D E F G H I J

l L M N O P Q R S T U V W X Y Z A B C D E F G H I J K

m M N O P Q R S T U V W X Y Z A B C D E F G H I J K L

n N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

o O P Q R S T U V W X Y Z A B C D E F G H I J K L M N

p P Q R S T U V W X Y Z A B C D E F G H I J K L M N O

q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P

r R S T U V W X Y Z A B C D E F G H I J K L M N O P Q

s S T U V W X Y Z A B C D E F G H I J K L M N O P Q R

t T U V W X Y Z A B C D E F G H I J K L M N O P Q R S

u U V W X Y Z A B C D E F G H I J K L M N O P Q R S T

v V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

w W X Y Z A B C D E F G H I J K L M N O P Q R S T U V

x X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X

z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

To use the above table, we do three things to encipher: (1) Put the plaintext

letters in a row; (2) Above each plaintext letter put the keyword letters, repeated

as often as necessary to cover all the plaintext; (3) Replace each letter of the

plaintext with the letter at the intersection of the row and column of the table

Ā© 2003 by CRC Press LLC

16 1. History and Basic Cryptographic Concepts

containing the keyword letter and plaintext letter, respectively. For example,

suppose that our keyword is watchers, and our plaintext is immortals never

die. Then we write the keyword as many times as necessary above the plaintext,

so the third row is the ciphertext determined by the intersections in the table.

w a t c h e r s w a t c h e r s w

i m m o r t a l s n e v e r d i e

E M F Q Y X R D O N X X L V U A A

For instance, the letter w is in a row that intersects the column containing

the letter i at the ciphertext letter E, and so on.

To decipher using the Vigen`re Tableau, we do three things: (1) Put the

e

ciphertext letters in a row; (2) Put the keyword letters above the ciphertext

letters, repeating them as required to cover all ciphertext; (3) For each column

in which a keyword letter sits, locate the row in which the ciphertext letter

below it sits. Then the letter in the ļ¬rst column of that row is the corresponding

plaintext. For instance, letā™s decipher our previous example. The third row is

the plaintext.

w a t c h e r s w a t c h e r s w

E M F Q Y X R D O N X X L V U A A

i m m o r t a l s n e v e r d i e

For instance, since the letter w sits over the ciphertext letter E, and the row

in which E sits in wā™s column has the letter i in its ļ¬rst column, this is the ļ¬rst

letter of plaintext, and so on. (See Exercises 1.29ā“1.34.)

The following is an example of how the Vigen`re Cipher may be viewed as

e

a periodic stream cipher.

Example 1.18 The Vigen`re Cipher with key e of length r may be considered to

e

be a periodic stream cipher with period r. The key e = (e1 , e2 , . . . , er ) provides

the ļ¬rst r elements of the keystream kj = ej for 1 ā¤ j ā¤ r, after which the

keystream repeats itself.

Example 1.18 illustrates that there are circumstances when a block cipher

may be considered to be a stream cipher. For instance, even the shift cipher

may be considered to be a Vigen`re Cipher with period length one. This should

e

not lead to confusion since all interpretations are consistent with the deļ¬nitions.

That there may be a blurring at the simplest levels between the two types that is

of no concern. Example 1.18 is actually an illustration of the following concept.

Deļ¬nition 1.19 (Synchronous Stream Ciphers)

A Stream Cipher is said to be synchronous if the keystream is generated

without use of either the plaintext or the ciphertext, called keystream generation

where that generation is independent of the plaintext and ciphertext.

Ā© 2003 by CRC Press LLC

1.2. Classical Ciphers 17

Basically, in a synchronous stream cipher both the sender and the receiver

must be synchronized in the sense that they must be at exactly the same position

in their shared key. Any loss or insertion of bits means that they must re-

synchronize. Deļ¬nition 1.19 is one of the two categories into which stream

ciphers are classiļ¬ed. The other is given as follows.

Deļ¬nition 1.20 (Self-Synchronizing Ciphers)

A Stream Cipher is called self-synchronizing (or asynchronous) if the

keystream is generated as a function of the key and a ļ¬xed number of previ-

ous ciphertext units. If the Stream Cipher utilizes plaintext in the keystream

generation, then it is called nonsynchronous.

Vigen`re had another idea that provides us with an example of a nonsyn-

e

chronous stream cipher as follows.

Example 1.21 This is a description of a variant of the Vigen`re Cipher. Let

e

n = |A| where A is the alphabet of deļ¬nition. We call k1 k2 Ā· Ā· Ā· kr for 1 ā¤ r ā¤ n a

priming key. Then given a plaintext message unit m = (m1 , m2 , . . . , ms ) where

s ā„ r, we generate a keystream as follows: k = k1 k2 Ā· Ā· Ā· kr m1 m2 Ā· Ā· Ā· msā’r . Then

we encipher via:

Ek (m) = (m1 + k1 , . . . , mr + kr , mr+1 + m1 , mr+2 + m2 , Ā· Ā· Ā· , ms + msā’r ) = c,

where + is addition modulo n, so mj + kj , mr+j + mj ā Z/nZ. We decipher via:

Dk (c) = (c1 ā’ k1 , . . . , cr ā’ kr , cr+1 ā’ m1 , . . . , cs ā’ msā’r ) = m. This cryptosystem

is nonsynchronous since the plaintext serves as the key, from the (r+1)st position

onwards, with the simplest case being r = 1.

Example 1.21 is an instance of the following concept.

Deļ¬nition 1.22 (Autokey Ciphers)

An Autokey Cipher is a cryptosystem wherein the plaintext itself (in whole

or in part) serves as the key (usually after the use of an initial priming key).

For instance, the cipher given Example 1.21 is called the Autokey Vigen`re

e

Cipher, wherein the plaintext is introduced into the key generation after the

priming key has been exhausted.

There is also a means of interpreting the Vernam Cipher as a Vign`re Cipher.

e

Example 1.23 The deļ¬nition of the Vign`re Cipher is a Running-key Cipher.

e

In other words, the keystream is as long as the plaintext. The Vign`re Cipher

e

becomes a Vernam Cipher if we assume that the keystream is truly random and

never repeats.

Ā© 2003 by CRC Press LLC

18 1. History and Basic Cryptographic Concepts

A variant of the Vigen`re Cipher is the following.

e

x Beaufort1.6 Cipher

Fix r, n ā N. Both the encryption and decryption functions are given by

x ā’ (e1 ā’x1 , e2 ā’x2 , . . . , er ā’xr ), for e = (e1 , . . . , er ) ā K and x = (x1 , . . . , xr ) ā

(Z/nZ)r = M = C. In other words, the encryption and decryption functions are

the same; namely, they are their own inverses.

The self-decrypting Beaufort Cipher was used in a rotor-based cipher ma-

chine called the Hagelin1.7 M-209.

Example 1.24 In the Beaufort Cipher, let r = 4, n = 26, and choose the key

HARD. We wish to decipher the following cryptogram.

HXFVQAGCDAXYTJYLFAGS.

First convert the key and the cryptogram to its numerical equivalents via Table

1.2: e = (7, 0, 17, 3), and ciphertext

(7, 23, 5, 21, 16, 0, 6, 2, 3, 0, 23, 24, 19, 9, 24, 11, 5, 0, 6, 18).

Then apply the key to each r = 4-block modulo 26 = n:

e(7, 23, 5, 21) = (7 ā’ 7, 0 ā’ 23, 17 ā’ 5, 3 ā’ 21) = (0, 3, 12, 8) = (ADM I),

1.6 This cryptosystem was invented by Francis Beaufort (1774ā“1857). He was born in County

Meath, Ireland. He began his nautical career at age thirteen as a cabin boy in the British

Navy. By age twenty-two, he attained the rank of lieutenant, and by 1805, he was given his

ļ¬rst command on the H.M.S. Woolwich. His assignment was to do a hydrographic survey

of the Rio de la Plata region of South America. It was during this time that he began to

develop what later became known as the Beaufort Wind Force Scale, which is an instrument

that meteorologists use to indicate wind velocities on a scale from 0 to 12, where, for instance,

0 is calm, 6 is a strong breeze, and 12 is a hurricane. In 1838, his scale was put into use by

the British ļ¬‚eet. By 1846, Beaufort was promoted to Rear Admiral, and by 1855 Sir Francis

Beaufort retired from the Admiralty. He died two years later but left an admirable legacy.

The cipher that bears his name originated with him, but was not published until a few months

after his death by his brother.

1.7 Boris Caesar Wilhelm Hagelin, who was born on July 2, 1892, invented this device in the

early 1940s. In 1922, Emanuel Nobel, nephew of the famed Alfred Nobel, put Hagelin to work

in the ļ¬rm Aktiebolaget Cryptograph or Cryptograph Incorporated, a company owned by Avid

Gerhard Damn, who invented cipher machines of his own. Hagelin simpliļ¬ed and improved

one of Damnā™s machines. After Damnā™s death in 1927, Hagelin ran the ļ¬rm. Later he devel-

oped the M-209, which became so successful that in the early 1940s more than 140000 were

manufactured. The royalties from this alone made Hagelin the ļ¬rst to become a millionaire

from cryptography. Due to Swedish law that allowed the government to conļ¬scate inventions

required for national defence, Hagelin moved the company to Zug, Switzerland in 1948, where

it was incorporated as CRYPTO AG in 1959. The ļ¬rm is still in operation although it got

embroiled in a controversy over sales of a cipher product to Iran in the early 1990s. It went so

far that a senior salesman for CRYPTO AG, Hans Bueler, was arrested in Tehran on March

18, 1992, where he spent nine and a half months in prison being questioned about leaking

cryptographic data to the Western powers. He knew nothing as it turns out, and CRYPTO

AG ultimately paid a million dollars for Buelerā™s release in January, 1993. The company ļ¬red

him shortly thereafter. The controversy continued into whether or not CRYPTO AGā™s prod-

ucts were compromised by Western intelligence services. The company denies all allegations,

but rumours abound.

Ā© 2003 by CRC Press LLC

1.2. Classical Ciphers 19

e(16, 0, 6, 2) = (7 ā’ 16, 0 ā’ 0, 17 ā’ 6, 3 ā’ 2) = (17, 0, 11, 1) = (RALB),

e(3, 0, 23, 24) = (7 ā’ 3, 0 ā’ 0, 17 ā’ 23, 3 ā’ 24) = (4, 0, 20, 5) = (EAU F ),

e(19, 9, 24, 11) = (7 ā’ 19, 0 ā’ 9, 17 ā’ 24, 3 ā’ 11) = (14, 17, 19, 18) = (ORT S),

e(5, 0, 6, 18) = (7 ā’ 5, 0 ā’ 0, 17 ā’ 6, 3 ā’ 18) = (2, 0, 11, 11) = (CALL).

and

The end result is: ADMIRAL BEAUFORTā™S CALL (with

the apostrophe understood tacitly). (See Exercises 1.35ā“1.36.)

Deļ¬nition 1.17 tells us that a simple substitution cipher encrypts single

plaintext symbols as single ciphertext symbols, such as the Caesar Cipher de-

scribed in Section 1.1. When groups of one or more symbols are replaced by

other groups of ciphertext symbols, then this cryptosystem is called a polygram

substitution cipher. For instance, we have the following classical polygram sub-

stitution cipher, which is a digraph cipher ā” where two adjacent symbols, called

a digram, are enciphered/deciphered at a time.

x The Playfair1.8 Cipher1.9

In this cipher the letters I and J are considered as a single entity.

A Z W IJ D

E U T G Y

Table 1.25 O N K Q M

H F X L S

V R P B C

Pairs of letters are enciphered according to the following rules.

(a) If two letters are in the same row, then their ciphertext equivalents are

immediately to their right. For instance, VC in plaintext is RV in cipher-

text. (This means that if one is at the right or bottom edge of the table,

then one āwraps aroundā as indicated in the example.)

(b) If two letters are in the same column, then their cipher equivalents are the

letters immediately below them. For example, ZF in plaintext is UR in

ciphertext, and JB in plaintext is GI in ciphertext.

1.8 This cipher was conceived by Sir Charles Wheatstone, and it was the ļ¬rst literal digraphic

cipher in cryptographic history. Although his friend, Lord Lyon Playfair, never claimed that

the cipher was his idea, he was zealous in his support for the invention. Playfair had even

discussed it with Prince Albert, suggesting its use in the Crimean War. It turns out to

have been used in the Boer War and possibly elsewhere. In any case, Britainā™s War Oļ¬ce

ostensibly kept the cipher a secret due to its being used as the British Armyā™s ļ¬eld cipher.

Thus, it ultimately came to be known as the Playfair Cipher.

1.9 John F. Kennedyā™s PT-109 was sunk by a Japanese cruiser in the Soloman Islands during

World War II. Kennedy swam to shore on the Japanese controlled Plum Island where he was

able to send a message using the Playfair Cipher to arrange rescue for the survivors of his

crew. In May of 2002, it was announced that Dr. Robert Ballard found the wreckage of

PT-109, nearly sixty years after it went down.

Ā© 2003 by CRC Press LLC

20 1. History and Basic Cryptographic Concepts

(c) If two letters are on the corners of a diagonal of a rectangle, then their

cipher equivalents are on the other corners, and the cipher equivalent

of each plaintext letter is on the same row as the plaintext letter. For

instance, UL in plaintext becomes GF in ciphertext and SZ in plaintext

is FD in ciphertext.

(d) If the same letter occurs as a pair in plaintext, then we agree by convention

to put a Z between them and encipher. Also, if a single letter remains at

the end of the plaintext, then a Z is added to it to complete the digraph.

Example 1.26 Suppose that we wish to decipher: BP DV GW VY FD OE

HQ YF SG RT CF TU WC DH LD KU HV IV WG FD, assuming

that it was encrypted using the Playfair Cipher. One merely reverses the rules

to decipher. For instance, the ļ¬rst pair BP of ciphertext letters occurs on the

same row. So we choose the letters to their left, PR. The second set DV occurs

on a diagonal with AC as the opposite ends (respectively) of the other diagonal.

Then GW occurs in diagonal with TI, which is chosen as plaintext, and so on to

get: practices zealously pursued pass into habits, where the last letter Z

is ignored as the ļ¬ller of the digraph. Such ļ¬llers are called nulls. (See Exercises

1.37ā“1.40.)

Another classical polygram substitution cipher is the following, which re-

quires some elementary matrix theory. In what follows, the symbol MrĆ—r (Z/nZ)

denotes the ring of r Ć— r matrices with entries from Z/nZ (see Appendix C).

xThe Hill1.10 Cipher

Fix r, n ā N, let K = {e ā MrĆ—r (Z/nZ) : e is invertible}, and set M = C =

(Z/nZ)r . Then for m ā M, e ā K, c ā C, Ee (m) = em and Dd (c) = eā’1 c.

(Note that e is invertible if and only if gcd(det(e), n) = 1.)

Example 1.27 Assume that SVJYYCDOIMWPCVDXCH has been en-

crypted with with n = 26, and r = 3 using the Hill Cipher with key

ļ£« ļ£¶

123

e = ļ£ 0 5 1 ļ£ø.

201

1.10 Lester S. Hill invented this cipher. He achieved his Ph.D. in mathematics from Yale in

1926, and taught mathematics at Hunter College in New York from 1927 until his retirement

in 1960. Hill was the ļ¬rst to successfully employ general algebraic concepts for cryptography.

A. A. Albert (see Footnote 1.3 on page 13) liked Hillā™s ideas so much that he tailored them

to work on some simple cryptosystems. Hillā™s rigorous mathematical approach may be said

to be one of the factors which has helped foster todayā™s solid grounding of cryptography in

mathematics. He died in Lawrence Hospital in Bronxville, New York after suļ¬ering through

a lengthy illness.

Ā© 2003 by CRC Press LLC

1.2. Classical Ciphers 21

In order to ļ¬nd the plaintext, we ļ¬rst calculate

ļ£« ļ£¶

1 10 13

eā’1 = ļ£ 16 25 5 ļ£ø .

24 6 1

Then we decipher each triple of ciphertext numerical equivalents as follows.

ļ£« ļ£¶ļ£« ļ£¶ ļ£« ļ£¶ļ£« ļ£¶ ļ£« ļ£¶ļ£« ļ£¶

18 7 24 4 3 13

eā’1 ļ£ 21 ļ£ø = ļ£ 0 ļ£ø , eā’1 ļ£ 24 ļ£ø = ļ£ 6 ļ£ø , eā’1 ļ£ 14 ļ£ø = ļ£ 22 ļ£ø

9 21 2 20 8 8

ļ£« ļ£¶ļ£« ļ£¶ ļ£« ļ£¶ļ£« ļ£¶ ļ£« ļ£¶ļ£« ļ£¶

12 11 2 17 23 4

eā’1 ļ£ 22 ļ£ø = ļ£ 11 ļ£ø , eā’1 ļ£ 21 ļ£ø = ļ£ 0 ļ£ø , eā’1 ļ£ 2 ļ£ø = ļ£ 11 ļ£ø .

15 19 3 21 7 25

Now, using Table 1.2, we get the letter equivalents of each plaintext triple

and decipher the plaintext as have gun will travel, where there is an extra

Z on the end, enciphered to ensure a ļ¬nal triple in plaintext, so we discarded

it. (See Exercises 1.41ā“1.44.)

Block ciphers come in two categories. The ļ¬rst of these is described in

Deļ¬nition 1.17 and the second is given as follows.

Deļ¬nition 1.28 (Transposition/Permutation Ciphers)

A simple transposition cipher, also known as a simple permutation cipher, is

a symmetric-key block cryptosystem having blocklength r ā N, with keyspace K

being the set of permutations on {1, 2, . . . , r}. The enciphering transformation

is given, for each m = (m1 , m2 , . . . , mr ) ā M, and given e ā K, by

Ee (m) = (me(1) , me(2) , . . . , me(r) ),

and for each c = (c1 , c2 , . . . , cr ) ā C,

Dd (c) = Deā’1 (c) = (cd(1) , cd(2) , . . . , cd(r) ).

The cryptosystems in Deļ¬nition 1.28 have keyspace of cardinality |K| = r!.

Permutation encryption involves grouping plaintext into blocks of r symbols and

applying to each block the permutation e on the numbers 1, 2, . . . , r. In other

words, the places where the plaintext symbols sit are permuted. We will use the

notation (Ļ1 , Ļ2 , . . . , Ļr ) to mean that j ā’ Ļj for j = 1, 2, . . . , r. For instance,

take e = (1, 2, 3, 4, 10, 7, 8, 9, 5, 6, 11, 12, 13) and apply it to They ļ¬‚ung hags, and

we get They hung ļ¬‚ags. To see this, let mj be the jth letter in They ļ¬‚ung hags

for j = 1, 2, . . . , 13. Then, for instance, me(5) = m10 = h; me(6) = m7 = u;

me(7) = m8 = n; and so on. This is a permutation of the places where the

plaintext letters sit. Therefore, plaintext letters get moved according to the

given place permutation. To decipher, one merely reverses the permutation.

In contrast, Deļ¬nition 1.17 provides for a permutation of the actual plaintext

symbols themselves.

Ā© 2003 by CRC Press LLC

22 1. History and Basic Cryptographic Concepts

Example 1.29 Let r = 6, M = C = Z/26Z, with the English letter equivalents

given by Table 1.2. Then if e = (2, 3, 6, 1, 4, 5) is applied to

agency,

we get

GEYANC

since m1 = A, m2 = G, m3 = E, m4 = N, m5 = C, and m6 = Y , so

e(m) = (me(1) , me(2) , me(3) , me(4) , me(5) , me(6) ) = (m2 , m3 , m6 , m1 , m4 , m5 ).

Since the inverse transformation is

d = eā’1 = (4, 1, 2, 5, 6, 3),

then another way to visualize encryption is to write 4, 1, 2, 5, 6, 3 in the ļ¬rst row,

and the plaintext letter equivalents in the second row, then read the letters oļ¬

in numerical order. For instance,

41 2 5 6 3

.

AG E N C Y

Thus, the ļ¬rst in numerical order is G, the second is E and so on. (See Exercises

1.45ā“1.58.) To decrypt, write the message under the encryption key, and read

oļ¬ the text in numerical order.

An easy means for ļ¬nding the inverse of a given key e such as in Example

1.29 is given as follows. The key in that example can be written as

12345 6

e= ,

23614 5

since 1 ā’ 2, 2 ā’ 3; and so on. To ļ¬nd the inverse, just read oļ¬ in numeric

order (determined by the second row), the terms in the ļ¬rst row. For instance,

the term in the ļ¬rst row sitting above the 1 is 4, showing that 4 is the ļ¬rst term

in eā’1 . The term in the ļ¬rst row sitting above the 2 is 1, showing that 1 is the

second term in eā’1 , and so on.

To date, the best known symmetric-key block cipher is the Data Encryption

Standard (DES) which was the ļ¬rst commercially available algorithm and was

put into use in the 1970s (see [165] for a complete description and background).

However, by the end of the century DES had reached the end of its usefulness,

largely because of a keylength (56-bit) that was too small for modern security. It

was replaced in August 2001 by the Advanced Encryption Standard ā” Rijndael,

which is also described in detail in [165].

We have described several classical ciphers, and historical background, as a

precursor to the study of public-key encryption in this text.

Ā© 2003 by CRC Press LLC

1.2. Classical Ciphers 23

Exercises

In Exercises 1.23ā“1.28, use the Aļ¬ne Cipher given in Example 1.16 to de-

crypt each of the ciphertexts given as follows.

TBHORQYQBRHIBT

1.23.

EHYOZKYQBMZOWBO

1.24.

MZPMYQBRHPET

1.25.

TBRDOBYQBMHTB

1.26.

TDOOZDUWYQBRVYX

1.27.

EOZYBRYYQBRVIVKVHUT

1.28.

In Exercises 1.29ā“1.34, assume that the keyword, given in the example on

page 16, for the Vigen`re Cipher was used to encrypt each of the cipher-

e

texts. Use the deciphering technique with the Vigen`re Tableau in that

e

example to ļ¬nd each plaintext.

OHXEYIRLADTUAEKW

1.29.

OHXFLPZNARXFALVE

1.30.

DEWGZXIGUEWVVAEK

1.31.

PHXAYISMELMCJMKQ

1.32.

XOMJZXIMCGEGZIEV

1.33.

BODTDEIDKRWUYYCW

1.34.

In Exercises 1.35ā“1.36, use the Beaufort Cipher key in Example 1.24 to

decipher the following cryptograms.

CSEAOTNLDYAZONDH

1.35.

OWARZNRKDTJR

1.36.

In Exercises 1.37ā“1.40, decipher the following cryptograms assuming they

were encrypted using the Playfair Cipher.

VE AO ZO KE VO VN OU

1.37.

HN BU UG IJV NE GW UW

1.38.

UP EG NV YO YO VG ZU

1.39.

EX MH YA DE LD MF TV GU QC UV

1.40.

In Exercises 1.41ā“1.44, decipher the following cryptograms using the key

and setup for the Hill Cipher given in Example 1.27.

WNWXCQZYRGSWOOV

1.41.

Ā© 2003 by CRC Press LLC

24 1. History and Basic Cryptographic Concepts

TNQPDXVGYONTZXTXYKSBRRRNLYPIKIATP

1.42.

QIWTLPTAYZUH

1.43.

JQDTNQMJRATWEQUEKY

1.44.

In Exercises 1.45ā“1.57, decipher the following cryptograms using the key

e = (4, 3, 1, 6, 7, 5, 8, 2) in a permutation cipher. (See Deļ¬nition 1.28.)

STLOLRLE

1.45.

IFWHTGTEOREISRMR

1.46.

ELAILVDLSROAIFLE

1.47.

TCVRYOCILPOTEEDM

1.48.

SUTHITMR

1.49.

AWBEORFEEVNBEMRO

1.50.

ELSDINDP

1.51.

IMTGINTI

1.52.

GRDSEIOTAGREUSN

1.53.

MICNAILRCNSIOTNA

1.54.

DOGEEDDOERSAIVLP

1.55.

ATTITLAONARANLDI

1.56.

LLFDWEIIERTREGTH

1.57.

1.58. Apply the key e = (5, 9, 10, 7, 12, 8, 6, 13, 1, 3, 11, 2, 4) as a permutation

cipher to: BRITNEY SPEARS

1.59. A superincreasing sequence is a sequence of natural numbers b1 , b2 , . . . , bn

iā’1

such that bi > j=1 bj for all i = 2, 3, . . . , n. Prove that a set of natural

numbers {b1 , b2 , . . . , bn }, satisfying the property that bj+1 > 2bj for all

j = 1, 2, . . . , n ā’ 1, is a superincreasing sequence.

1.60. The subset sum problem is deļ¬ned as follows. Given m, n ā N and a set S =

{bj : bj ā N, for j = 1, 2, . . . , n}, called a knapsack set, determine whether

or not there exists a subset S0 of S such that the sum of the elements in S0

equals m.1.11 Find all subsets of the knapsack set S = {1, 2, 3, 5, 9, 10, 11}

that have 13 as their sum. Is S a superincreasing sequence?

1.11 Exercises1.59ā“1.60 are related to another classical cipher called the knapsack cipher.

We will not describe this type of cryptosystem herein since the last of the remaining subset

sum based knapsack ciphers was broken in 2001. For details and additional comments, see

Footnote 3.9 on page 67.

Ā© 2003 by CRC Press LLC

1.3. Classiļ¬cation of Attacks 25

1.3 Classiļ¬cation of Attacks

Attack is the best form of defence

Late eighteenth century proverb

Although our primary goal is to study cryptography, there is an essential

need to understand some basics about cryptanalysis, if for no other reason than

to understand what the strength of a cryptosystem (usually tantamount to its

weakest point) means from knowledge of the various ways of breaking it. To

break a cryptosystem means to decrypt the ciphertext without knowledge of the

key, and in practical terms this means reconstructing the key via observations

of the cryptosystem being employed.

By an attack, we mean the use of any methodology that begins with some

information about the plaintext or ciphertext, encrypted using a key, which

is yet unknown to the cryptanalyst whose end-goal is to break the system.

The kinds of observations and the manipulations of the cryptosystem made

by the cryptanalyst determine the type of attack. The following provides a

description of the basic attacks on cryptosystems, under the assumption that the

cryptanalyst has complete knowledge of the enciphering transformation being

employed, but has no knowledge of the key. (This is the traditional assumption

made for academic cryptanalysis, although this is not always the case in āreal-

lifeā cryptanalysis. Nevertheless, this is a reasonable assumption to make if one

wants to ensure maximum strength of a cryptosystem.)

q Classiļ¬cation of Cryptanalytic Attacks

There are two basic types of attacks, passive and active. A passive attack

involves the cryptanalystā™s monitoring (also called āeavesdroppingā) of the com-

munication channels, thereby threatening only the conļ¬dentiality of the data.

An active attack is one where the cryptanalyst attempts to add, delete, or oth-

erwise alter the message, so that not only conļ¬dentiality but also the integrity

and authentication of the data are threatened. We begin with a classiļ¬cation of

passive attacks, which are given in order of the degree of diļ¬culty, on the part

of the cryptanalyst, to mount a successful attack.

ā¶ Passive Attacks

x Ciphertext-Only

The cryptanalyst has access only to the ciphertext, obtained through in-

terception of some cryptograms, from which to deduce the plaintext, without

any knowledge whatsoever of the plaintext. For instance, with a relatively

small amount of ciphertext enciphered using the Caesar Cipher, the cryptana-

lyst needs only try the twenty-ļ¬ve diļ¬erent deciphering shifts to get the key.

x Known-Plaintext

The cryptanalyst has both ciphertext and corresponding plaintext from in-

tercepted cryptograms as data from which to deduce the plaintext in general, or

Ā© 2003 by CRC Press LLC

26 1. History and Basic Cryptographic Concepts

the key. In the case of a shift cipher, for instance, only one plaintext-ciphertext

pair needs to be known to determine the key, which is instantly known to be

how far the enciphered symbol is shifted from the plaintext symbol.

One of the most prominent known-plaintext attacks against block ciphers is

linear cryptanalysis (LC), using linear approximations to describe the behavior

of the block cipher. LC was developed by Matsui [147] in 1994, when he suc-

cessfully used it (under experimental conditions) against DES (see page 22) to

obtain a key with 243 known plaintexts (see [148]).

x Chosen-Plaintext

The cryptanalyst chooses plaintext, is then given corresponding ciphertext,

and analyzes the data to determine the encryption key. It turns out that RSA

is extremely vulnerable to this type of attack, as we shall discuss in Chapter 6.

One of the best-known chosen-plaintext attacks against block ciphers is dif-

ferential cryptanalysis (DC) developed by Biham and Shamir [26] in 1993. DC

involves the comparisons of pairs of plaintext with pairs of ciphertext, the task

being to concentrate on ciphertext pairs whose plaintext pairs have certain ādif-

ferencesā. Some of these diļ¬erences have a high probability of reappearing in

the ciphertext pairs. Those that do are called ācharacteristicsā, which DC uses

to assign probabilities to the possible keys, with an end-goal being the location

of the most probable key. When used against DES, the DC attack proved less

successful than the LC attack.

x Chosen-Ciphertext

The cryptanalyst chooses the ciphertext and is given the corresponding plain-

text. This attack is most eļ¬ective against public-key cryptosystems (see Chapter

6), but sometimes is eļ¬ective against symmetric-key types as well.

One method of mounting a chosen-ciphertext attack is to gain access to

the equipment used to encipher. This was done prior to World War II when

the Americans were able to reconstruct the Japanese cipher machine that was

used for diplomatic communication. This allowed the American cryptanalysts

to decipher Japanese cryptograms during the war, but since the Japanese were

unable to cryptanalyze American ciphers, they assumed that their cryptograms

were also unbreakable ā” a fatal assumption. Cryptanalysts helped to ensure

that Japanā™s lifeline was rapidly cut, and that German U-boats were defeated.

Another incident involved the downing of the plane carrying the commander-

in-chief of the Combined Fleet of the Japanese Navy, Admiral Isoruko Ya-

mamoto. The Americans had been able to decipher a highly secret cryptogram,

giving the itinerary of Yamamotoā™s plane on a tour of the Solomon Islands.

Of vital importance was the Battle of Midway, which was a stunning victory

by American cryptanalysts since they were able to give complete information on

the size and location of the Japanese forces advancing on Midway. This enabled

the Navy to concentrate a numerically inferior force in exactly the right place

ńņš. 1 |