. 1
( 2)



>>

Chapter 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
( 2)



>>