Discussion

 After reading chapter 3, analyze the history of the Caesar Cypher and its impact on cryptography.  Feel free to also include the impact of items such as the Scytale and the Polybius square.  All of these were used long before computers. 

Cryptography and Network Security: Principles and Practice

Eighth Edition

Chapter 3

Classical Encryption Techniques

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Lecture slides prepared for “Cryptography and Network Security”, 8/e, by William Stallings, Chapter 3 – “Classical Encryption Techniques”.
Symmetric encryption, also referred to as conventional encryption or single-key
encryption, was the only type of encryption in use prior to the development of public-key
encryption in the 1970s. It remains by far the most widely used of the two types
of encryption. Part One examines a number of symmetric ciphers. In this chapter, we
begin with a look at a general model for the symmetric encryption process; this will
enable us to understand the context within which the algorithms are used. Next, we
examine a variety of algorithms in use before the computer era. Finally, we look briefly
at a different approach known as steganography. Chapters 4 and 6 introduce the two
most widely used symmetric cipher: DES and AES.
1

Learning Objectives
Present an overview of the main concepts of symmetric cryptography.
Explain the difference between cryptanalysis and brute-force attack.
Understand the operation of a monoalphabetic substitution cipher.
Understand the operation of a polyalphabetic cipher.
Present an overview of the Hill cipher.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Definitions (1 of 2)
Plaintext
An original message
Ciphertext
The coded message
Enciphering/encryption
The process of converting from plaintext to ciphertext
Deciphering/decryption
Restoring the plaintext from the ciphertext

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Before beginning, we define some terms. An original message is known as the
plaintext, while the coded message is called the ciphertext. The process of converting
from plaintext to ciphertext is known as enciphering or encryption; restoring the
plaintext from the ciphertext is deciphering or decryption. The many schemes used
for encryption constitute the area of study known as cryptography Such a scheme
is known as a cryptographic system or a cipher. Techniques used for deciphering a
message without any knowledge of the enciphering details fall into the area of cryptanalysis.
Cryptanalysis is what the layperson calls “breaking the code.” The areas of
cryptography and cryptanalysis together are called cryptology.
3

Definitions (2 of 2)
Cryptography
The area of study of the many schemes used for encryption
Cryptographic system/cipher
A scheme
Cryptanalysis
Techniques used for deciphering a message without any knowledge of the enciphering details
Cryptology
The areas of cryptography and cryptanalysis

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Before beginning, we define some terms. An original message is known as the
plaintext, while the coded message is called the ciphertext. The process of converting
from plaintext to ciphertext is known as enciphering or encryption; restoring the
plaintext from the ciphertext is deciphering or decryption. The many schemes used
for encryption constitute the area of study known as cryptography Such a scheme
is known as a cryptographic system or a cipher. Techniques used for deciphering a
message without any knowledge of the enciphering details fall into the area of cryptanalysis.
Cryptanalysis is what the layperson calls “breaking the code.” The areas of
cryptography and cryptanalysis together are called cryptology.
4

Figure 3.1 Simplified Model of Symmetric Encryption

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
A symmetric encryption scheme has five ingredients (Figure 3.1)
■ Plaintext: This is the original intelligible message or data that is fed into the
algorithm as input.
■ Encryption algorithm: The encryption algorithm performs various substitutions
and transformations on the plaintext.
■ Secret key: The secret key is also input to the encryption algorithm. The key is
a value independent of the plaintext and of the algorithm. The algorithm will
produce a different output depending on the specific key being used at the
time. The exact substitutions and transformations performed by the algorithm
depend on the key.
■ Ciphertext: This is the scrambled message produced as output. It depends on
the plaintext and the secret key. For a given message, two different keys will
produce two different ciphertexts. The ciphertext is an apparently random
stream of data and, as it stands, is unintelligible.
■ Decryption algorithm: This is essentially the encryption algorithm run in
reverse. It takes the ciphertext and the secret key and produces the original
plaintext.
5

Symmetric Cipher Model
There are two requirements for secure use of conventional encryption:
A strong encryption algorithm
Sender and receiver must have obtained copies of the secret key in a secure fashion and must keep the key secure

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
There are two requirements for secure use of conventional encryption:
1. We need a strong encryption algorithm. At a minimum, we would like the algorithm
to be such that an opponent who knows the algorithm and has access to
one or more ciphertexts would be unable to decipher the ciphertext or figure
out the key. This requirement is usually stated in a stronger form: The opponent
should be unable to decrypt ciphertext or discover the key even if he or
she is in possession of a number of ciphertexts together with the plaintext that
produced each ciphertext.
2. Sender and receiver must have obtained copies of the secret key in a secure
fashion and must keep the key secure. If someone can discover the key and
knows the algorithm, all communication using this key is readable.
We assume that it is impractical to decrypt a message on the basis of the
ciphertext plus knowledge of the encryption/decryption algorithm. In other words,
we do not need to keep the algorithm secret; we need to keep only the key secret.
This feature of symmetric encryption is what makes it feasible for widespread use.
The fact that the algorithm need not be kept secret means that manufacturers can
and have developed low-cost chip implementations of data encryption algorithms.
These chips are widely available and incorporated into a number of products. With
the use of symmetric encryption, the principal security problem is maintaining the
secrecy of the key.
6

Figure 3.2 Model of Symmetric Cryptosystem

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Let us take a closer look at the essential elements of a symmetric encryption scheme, using Figure 3.2.
7

Cryptographic Systems
Characterized along three independent dimensions:
The type of operations used for transforming plaintext to ciphertext
Substitution
Transposition
The number of keys used
Symmetric, single-key, secret-key, conventional encryption
Asymmetric, two-key, or public-key encryption
The way in which the plaintext is processed
Block cipher
Stream cipher

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Cryptographic systems are characterized along three independent dimensions:
1. The type of operations used for transforming plaintext to ciphertext. All
encryption algorithms are based on two general principles: substitution, in
which each element in the plaintext (bit, letter, group of bits or letters) is
mapped into another element, and transposition, in which elements in the
plaintext are rearranged. The fundamental requirement is that no information
be lost (i.e., that all operations are reversible). Most systems, referred to as
product systems , involve multiple stages of substitutions and transpositions.
2. The number of keys used. If both sender and receiver use the same key, the
system is referred to as symmetric, single-key, secret-key, or conventional
encryption. If the sender and receiver use different keys, the system is referred
to as asymmetric, two-key, or public-key encryption.
3. The way in which the plaintext is processed. A block cipher processes the
input one block of elements at a time, producing an output block for each
input block. A stream cipher processes the input elements continuously,
producing output one element at a time, as it goes along.
8

Cryptanalysis and Brute-Force Attack
Cryptanalysis
Attack relies on the nature of the algorithm plus some knowledge of the general characteristics of the plaintext
Attack exploits the characteristics of the algorithm to attempt to deduce a specific plaintext or to deduce the key being used
Brute-force attack
Attacker tries every possible key on a piece of ciphertext until an intelligible translation into plaintext is obtained
On average, half of all possible keys must be tried to achieve success

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Typically, the objective of attacking an encryption system is to recover the key in
use rather than simply to recover the plaintext of a single ciphertext. There are two
general approaches to attacking a conventional encryption scheme:
• Cryptanalysis: Cryptanalytic attacks rely on the nature of the algorithm plus
perhaps some knowledge of the general characteristics of the plaintext or
even some sample plaintext–ciphertext pairs. This type of attack exploits the
characteristics of the algorithm to attempt to deduce a specific plaintext or to
deduce the key being used.
• Brute-force attack: The attacker tries every possible key on a piece of ciphertext
until an intelligible translation into plaintext is obtained. On average, half
of all possible keys must be tried to achieve success.
If either type of attack succeeds in deducing the key, the effect is catastrophic:
All future and past messages encrypted with that key are compromised.
9

Table 3.1 Types of Attacks on Encrypted Messages
Type of Attack Known to Cryptanalyst
Ciphertext Only Encryption algorithm
Ciphertext
Known Plaintext Encryption algorithm
Ciphertext
One or more plaintext–ciphertext pairs formed with the secret key
Chosen Plaintext Encryption algorithm
Ciphertext
Plaintext message chosen by cryptanalyst, together with its corresponding ciphertext generated with the secret key
Chosen Ciphertext Encryption algorithm
Ciphertext
Ciphertext chosen by cryptanalyst, together with its corresponding decrypted plaintext generated with the secret key
Chosen Text Encryption algorithm
Ciphertext
Plaintext message chosen by cryptanalyst, together with its corresponding ciphertext generated with the secret key
Ciphertext chosen by cryptanalyst, together with its corresponding decrypted plaintext generated with the secret key

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Table 3.1 summarizes the various types of cryptanalytic attacks based on the
amount of information known to the cryptanalyst. The most difficult problem is
presented when all that is available is the ciphertext only . In some cases, not even
the encryption algorithm is known, but in general, we can assume that the opponent
does know the algorithm used for encryption. One possible attack under these
circumstances is the brute-force approach of trying all possible keys. If the key space
is very large, this becomes impractical. Thus, the opponent must rely on an analysis
of the ciphertext itself, generally applying various statistical tests to it. To use this
approach, the opponent must have some general idea of the type of plaintext that
is concealed, such as English or French text, an EXE file, a Java source listing, an
accounting file, and so on.
The ciphertext-only attack is the easiest to defend against because the
opponent has the least amount of information to work with. In many cases, however,
the analyst has more information. The analyst may be able to capture one or more
plaintext messages as well as their encryptions. Or the analyst may know that certain
plaintext patterns will appear in a message. For example, a file that is encoded in the
Postscript format always begins with the same pattern, or there may be a standardized
header or banner to an electronic funds transfer message, and so on. All these are
examples of known plaintext . With this knowledge, the analyst may be able to deduce
the key on the basis of the way in which the known plaintext is transformed.
Closely related to the known-plaintext attack is what might be referred to as a
probable-word attack. If the opponent is working with the encryption of some general
prose message, he or she may have little knowledge of what is in the message.
However, if the opponent is after some very specific information, then parts of the
message may be known. For example, if an entire accounting file is being transmitted,
the opponent may know the placement of certain key words in the header of the
file. As another example, the source code for a program developed by Corporation
X might include a copyright statement in some standardized position.
If the analyst is able somehow to get the source system to insert into the system
a message chosen by the analyst, then a chosen-plaintext attack is possible. In general,
if the analyst is able to choose the messages to encrypt, the analyst may deliberately
pick patterns that can be expected to reveal the structure of the key.
Table 3.1 lists two other types of attack: chosen ciphertext and chosen text.
These are less commonly employed as cryptanalytic techniques but are nevertheless
possible avenues of attack.
10

Encryption Scheme Security
Unconditionally secure
No matter how much time an opponent has, it is impossible for him or her to decrypt the ciphertext simply because the required information is not there
Computationally secure
The cost of breaking the cipher exceeds the value of the encrypted information
The time required to break the cipher exceeds the useful lifetime of the information

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Two more definitions are worthy of note. An encryption scheme is unconditionally
secure if the ciphertext generated by the scheme does not contain enough
information to determine uniquely the corresponding plaintext, no matter how
much ciphertext is available. That is, no matter how much time an opponent has, it
is impossible for him or her to decrypt the ciphertext simply because the required
information is not there. With the exception of a scheme known as the one-time pad
(described later in this chapter), there is no encryption algorithm that is unconditionally
secure. Therefore, all that the users of an encryption algorithm can strive
for is an algorithm that meets one or both of the following criteria:
• The cost of breaking the cipher exceeds the value of the encrypted information.
• The time required to break the cipher exceeds the useful lifetime of the
information.
An encryption scheme is said to be computationally secure if either of the
foregoing two criteria are met. Unfortunately, it is very difficult to estimate the
amount of effort required to cryptanalyze ciphertext successfully.
All forms of cryptanalysis for symmetric encryption schemes are designed
to exploit the fact that traces of structure or pattern in the plaintext may survive
encryption and be discernible in the ciphertext. This will become clear as we examine
various symmetric encryption schemes in this chapter. We will see in Part Three
that cryptanalysis for public-key schemes proceeds from a fundamentally different
premise, namely, that the mathematical properties of the pair of keys may make it
possible for one of the two keys to be deduced from the other.
11

Brute-Force Attack
Involves trying every possible key until an intelligible translation of the ciphertext into plaintext is obtained
On average, half of all possible keys must be tried to achieve success
To supplement the brute-force approach, some degree of knowledge about the expected plaintext is needed, and some means of automatically distinguishing plaintext from garble is also needed

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
A brute-force attack involves trying every possible key until an intelligible
translation of the ciphertext into plaintext is obtained. On average, half of all possible
keys must be tried to achieve success. That is, if there are X different keys, on
average an attacker would discover the actual key after X/2 tries. It is important to
note that there is more to a brute-force attack than simply running through all possible
keys. Unless known plaintext is provided, the analyst must be able to recognize
plaintext as plaintext. If the message is just plain text in English, then the result pops
out easily, although the task of recognizing English would have to be automated. If
the text message has been compressed before encryption, then recognition is more
difficult. And if the message is some more general type of data, such as a numerical
file, and this has been compressed, the problem becomes even more difficult to
automate. Thus, to supplement the brute-force approach, some degree of knowledge
about the expected plaintext is needed, and some means of automatically
distinguishing plaintext from garble is also needed.
12

Strong Encryption
The term strong encryption refers to encryption schemes that make it impractically difficult for unauthorized persons or systems to gain access to plaintext that has been encrypted
Properties that make an encryption algorithm strong are:
Appropriate choice of cryptographic algorithm
Use of sufficiently long key lengths
Appropriate choice of protocols
A well-engineered implementation
Absence of deliberately introduced hidden flaws

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
For users, security managers, and organization executives, there is a requirement for strong encryption to protect data. The term strong encryption is an imprecise one, but in general terms, it refers to encryption schemes that make it impractically difficult for unauthorized persons or systems to gain access to plaintext that has been encrypted. [NAS18] lists the following properties that make an encryption algorithm strong: appropriate choice of cryptographic algorithm, use of sufficiently long key lengths, appropriate choice of protocols, a well-engineered implementation, and the absence of deliberately introduced hidden flaws. The first two factors relate to cryptanalysis, discussed in this section, and the third factor relates to the discussion in Part Six. The last two factors are beyond the scope of this book.
13

Substitution Technique
Is one in which the letters of plaintext are replaced by other letters or by numbers or symbols
If the plaintext is viewed as a sequence of bits, then substitution involves replacing plaintext bit patterns with ciphertext bit patterns

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
The two basic building blocks of all encryption techniques are substitution
and transposition. We examine these in the next two sections. Finally, we discuss a
system that combines both substitution and transposition.
A substitution technique is one in which the letters of plaintext are replaced by
other letters or by numbers or symbols. If the plaintext is viewed as a sequence of bits,
then substitution involves replacing plaintext bit patterns with ciphertext bit patterns.
14

Caesar Cipher
Simplest and earliest known use of a substitution cipher
Used by Julius Caesar
Involves replacing each letter of the alphabet with the letter standing three places further down the alphabet
Alphabet is wrapped around so that the letter following Z is A
plain: meet me after the toga party
cipher: PHHW PH DIWHU WKH WRJD SDUWB

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
The earliest known, and the simplest, use of a substitution cipher was by Julius
Caesar. The Caesar cipher involves replacing each letter of the alphabet with the
letter standing three places further down the alphabet.
15

Caesar Cipher Algorithm
Can define transformation as:
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
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
Mathematically give each letter a number
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
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Algorithm can be expressed as:
c = E(3, p) = (p + 3) mod (26)
A shift may be of any amount, so that the general Caesar algorithm is:
C = E(k , p ) = (p + k ) mod 26
Where k takes on a value in the range 1 to 25; the decryption algorithm is simply:
p = D(k , C ) = (C − k ) mod 26

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Note that the alphabet is wrapped around, so that the letter following Z is A.
An algorithm can be expressed as follows. For each plaintext letter p , substitute
the ciphertext letter C
16

Figure 3.3 Brute-Force Cryptanalysis of Caesar Cipher

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
If it is known that a given ciphertext is a Caesar cipher, then a brute-force
cryptanalysis is easily performed: simply try all the 25 possible keys. Figure 3.3
shows the results of applying this strategy to the example ciphertext. In this case, the
plaintext leaps out as occupying the third line.
Three important characteristics of this problem enabled us to use a brute-force
cryptanalysis:
1. The encryption and decryption algorithms are known.
2. There are only 25 keys to try.
3. The language of the plaintext is known and easily recognizable.
17

Sample of Compressed Text
Figure 3.4 Sample of Compressed Text

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
In most networking situations, we can assume that the algorithms are known.
What generally makes brute-force cryptanalysis impractical is the use of an algorithm
that employs a large number of keys. For example, the triple DES algorithm,
examined in Chapter 7, makes use of a 168-bit key, giving a key space of 2168 or
greater than 3.7 * 1050 possible keys.
The third characteristic is also significant. If the language of the plaintext
is unknown, then plaintext output may not be recognizable. Furthermore, the
input may be abbreviated or compressed in some fashion, again making recognition
difficult. For example, Figure 3.4 shows a portion of a text file compressed
using an algorithm called ZIP. If this file is then encrypted with a simple substitution
cipher (expanded to include more than just 26 alphabetic characters),
then the plaintext may not be recognized when it is uncovered in the brute-force
cryptanalysis.
18

Monoalphabetic Cipher
Permutation
Of a finite set of elements S is an ordered sequence of all the elements of S , with each element appearing exactly once
If the “cipher” line can be any permutation of the 26 alphabetic characters, then there are 26! or greater than 4 x 1026 possible keys
This is 10 orders of magnitude greater than the key space for DES
Approach is referred to as a monoalphabetic substitution cipher because a single cipher alphabet is used per message

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
With only 25 possible keys, the Caesar cipher is far from secure. A dramatic increase
in the key space can be achieved by allowing an arbitrary substitution. Before proceeding,
we define the term permutation . A permutation of a finite set of elements S
is an ordered sequence of all the elements of S, with each element appearing exactly
once.
For example, if S = {a, b, c}, there are six permutations of S :
abc, acb, bac, bca, cab, cba
In general, there are n ! permutations of a set of n elements, because the first
element can be chosen in one of n ways, the second in n – 1 ways, the third in n – 2
ways, and so on.
If, instead, the “cipher” line can be any permutation of the 26 alphabetic characters,
then there are 26! or greater than 4 * 1026 possible keys. This is 10 orders of magnitude
greater than the key space for DES and would seem to eliminate brute-force
techniques for cryptanalysis. Such an approach is referred to as a monoalphabetic
substitution cipher, because a single cipher alphabet (mapping from plain alphabet
to cipher alphabet) is used per message.
19

Figure 3.5 Relative Frequency of Letters in English Text

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
There is, however, another line of attack. If the cryptanalyst knows the nature
of the plaintext (e.g., noncompressed English text), then the analyst can exploit the
regularities of the language. To see how such a cryptanalysis might proceed, we give
a partial example here that is adapted from one in [SINK09]. The ciphertext to be
solved is
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
As a first step, the relative frequency of the letters can be determined and
compared to a standard frequency distribution for English, such as is shown in
Figure 3.5 (based on [LEWA00]). If the message were long enough, this technique
alone might be sufficient, but because this is a relatively short message, we cannot
expect an exact match. In any case, the relative frequencies of the letters in the
ciphertext (in percentages) are as follows:
P 13.33 H 5.83 F 3.33 B 1.67 C 0.00
Z 11.67 D 5.00 W 3.33 G 1.67 K 0.00
S 8.33 E 5.00 Q 2.50 Y 1.67 L 0.00
U 8.33 V 4.17 T 2.50 I 0.83 N 0.00
O 7.50 X 4.17 A 1.67 J 0.83 R 0.00
M 6.67
Comparing this breakdown with Figure 3.5, it seems likely that cipher letters P
and Z are the equivalents of plain letters e and t, but it is not certain which is which.
The letters S, U, O, M, and H are all of relatively high frequency and probably correspond
to plain letters from the set {a, h, i, n, o, r, s}. The letters with the lowest
frequencies (namely, A, B, G, Y, I, J) are likely included in the set {b, j, k, q, v, x, z}.
There are a number of ways to proceed at this point. We could make some tentative
assignments and start to fill in the plaintext to see if it looks like a reasonable
“skeleton” of a message. A more systematic approach is to look for other regularities.
For example, certain words may be known to be in the text. Or we could look for
repeating sequences of cipher letters and try to deduce their plaintext equivalents.
20

Monoalphabetic Ciphers
Easy to break because they reflect the frequency data of the original alphabet
Countermeasure is to provide multiple substitutes (homophones) for a single letter
Digram
Two-letter combination
Most common is th
Trigram
Three-letter combination
Most frequent is the

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
A powerful tool is to look at the frequency of two-letter combinations, known
as digrams . A table similar to Figure 3.5 could be drawn up showing the relative frequency
of digrams. The most common such digram is th. In our ciphertext, the most
common digram is ZW, which appears three times. So we make the correspondence
of Z with t and W with h. Then, by our earlier hypothesis, we can equate P with e.
Now notice that the sequence ZWP appears in the ciphertext, and we can translate
that sequence as “the.” This is the most frequent trigram (three-letter combination)
in English, which seems to indicate that we are on the right track.
Next, notice the sequence ZWSZ in the first line. We do not know that these
four letters form a complete word, but if they do, it is of the form th_t. If so, S
equates with a.
So far, then, we have
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
t a e e te a that e e a a
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
e t ta t ha e ee a e th t a
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
e e e tat e the t

Only four letters have been identified, but already we have quite a bit of the
message. Continued analysis of frequencies plus trial and error should easily yield a
solution from this point. The complete plaintext, with spaces added between words,
follows:
it was disclosed yesterday that several informal but
direct contacts have been made with political
representatives of the Viet cong in Moscow
Monoalphabetic ciphers are easy to break because they reflect the frequency
data of the original alphabet. A countermeasure is to provide multiple substitutes,
known as homophones, for a single letter. For example, the letter e could be assigned
a number of different cipher symbols, such as 16, 74, 35, and 21, with each
homophone assigned to a letter in rotation or randomly. If the number of symbols
assigned to each letter is proportional to the relative frequency of that letter, then
single-letter frequency information is completely obliterated. The great mathematician
Carl Friedrich Gauss believed that he had devised an unbreakable cipher using
homophones. However, even with homophones, each element of plaintext affects
only one element of ciphertext, and multiple-letter patterns (e.g., digram frequencies)
still survive in the ciphertext, making cryptanalysis relatively straightforward.
Two principal methods are used in substitution ciphers to lessen the extent to
which the structure of the plaintext survives in the ciphertext: One approach is to
encrypt multiple letters of plaintext, and the other is to use multiple cipher alphabets.
We briefly examine each.
21

Playfair Cipher
Best-known multiple-letter encryption cipher
Treats digrams in the plaintext as single units and translates these units into ciphertext digrams
Based on the use of a 5 × 5 matrix of letters constructed using a keyword
Invented by British scientist Sir Charles Wheatstone in 1854
Used as the standard field system by the British Army in World War I and the U.S. Army and other Allied forces during World War II

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
The best-known multiple-letter encryption cipher is the Playfair, which treats
digrams in the plaintext as single units and translates these units into ciphertext
Digrams.
The Playfair algorithm is based on the use of a 5 * 5 matrix of letters constructed
using a keyword.
22

Playfair Key Matrix
Fill in letters of keyword (minus duplicates) from left to right and from top to bottom, then fill in the remainder of the matrix with the remaining letters in alphabetic order
Using the keyword MONARCHY:
M O N A R
C H Y B D
E F G I/J K
L P Q S T
U V W X Z

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
In this case, the keyword is monarchy . The matrix is constructed by filling
in the letters of the keyword (minus duplicates) from left to right and from top to
bottom, and then filling in the remainder of the matrix with the remaining letters in
alphabetic order. The letters I and J count as one letter. Plaintext is encrypted two
letters at a time, according to the following rules:
1. Repeating plaintext letters that are in the same pair are separated with a filler
letter, such as x, so that balloon would be treated as ba lx lo on.
2. Two plaintext letters that fall in the same row of the matrix are each replaced
by the letter to the right, with the first element of the row circularly following
the last. For example, ar is encrypted as RM.
3. Two plaintext letters that fall in the same column are each replaced by the
letter beneath, with the top element of the column circularly following the last.
For example, mu is encrypted as CM.
4. Otherwise, each plaintext letter in a pair is replaced by the letter that lies in
its own row and the column occupied by the other plaintext letter. Thus, hs
becomes BP and ea becomes IM (or JM, as the encipherer wishes).
The Playfair cipher is a great advance over simple monoalphabetic ciphers.
For one thing, whereas there are only 26 letters, there are 26 * 26 = 676 digrams, so
that identification of individual digrams is more difficult. Furthermore, the relative
frequencies of individual letters exhibit a much greater range than that of digrams,
making frequency analysis much more difficult. For these reasons, the Playfair
cipher was for a long time considered unbreakable. It was used as the standard field
system by the British Army in World War I and still enjoyed considerable use by the
U.S. Army and other Allied forces during World War II.
Despite this level of confidence in its security, the Playfair cipher is relatively
easy to break, because it still leaves much of the structure of the plaintext language
intact. A few hundred letters of ciphertext are generally sufficient.
23

Figure 3.6 Relative Frequency of Occurrence of Letters

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
One way of revealing the effectiveness of the Playfair and other ciphers
is shown in Figure 3.6. The line labeled plaintext plots a typical frequency
distribution of the 26 alphabetic characters (no distinction between upper
and lower case) in ordinary text. This is also the frequency distribution of any
monoalphabetic substitution cipher, because the frequency values for individual
letters are the same, just with different letters substituted for the original letters.
The plot is developed in the following way: The number of occurrences of each
letter in the text is counted and divided by the number of occurrences of the
most frequently used letter. Using the results of Figure 3.5, we see that
e is the most frequently used letter. As a result, e has a relative frequency of 1, t of
9.056/12.702 0.72, and so on. The points on the horizontal axis correspond
to the letters in order of decreasing frequency.
Figure 3.6 also shows the frequency distribution that results when the text
is encrypted using the Playfair cipher. To normalize the plot, the number of
occurrences of each letter in the ciphertext was again divided by the number of
occurrences of e in the plaintext. The resulting plot therefore shows the extent
to which the frequency distribution of letters, which makes it trivial to solve
substitution ciphers, is masked by encryption. If the frequency distribution
information were totally concealed in the encryption process, the ciphertext plot
of frequencies would be flat, and cryptanalysis using ciphertext only would be
effectively impossible. As the figure shows, the Playfair cipher has a flatter distribution
than does plaintext, but nevertheless, it reveals plenty of structure for
a cryptanalyst to work with. The plot also shows the Vigenère cipher, discussed
subsequently. The Hill and Vigenère curves on the plot are based on results
reported in [SIMM93].
24

Hill Cipher
Developed by the mathematician Lester Hill in 1929
Strength is that it completely hides single-letter frequencies
The use of a larger matrix hides more frequency information
A 3 x 3 Hill cipher hides not only single-letter but also two-letter frequency information
Strong against a ciphertext-only attack but easily broken with a known plaintext attack

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Another interesting multiletter cipher is the Hill cipher, developed by the mathematician
Lester Hill in 1929.
Before describing the Hill cipher, let us briefly
review some terminology from linear algebra. In this discussion, we are concerned
with matrix arithmetic modulo 26. For the reader who needs a refresher on matrix
multiplication and inversion, see Appendix A.
We define the inverse M-1 of a square matrix M by the equation
M (M-1 ) = M-1M = I , where I is the identity matrix. I is a square matrix that is all
zeros except for ones along the main diagonal from upper left to lower right. The
inverse of a matrix does not always exist, but when it does, it satisfies the preceding
equation.
To explain how the inverse of a matrix is computed, we begin with the concept
of determinant. For any square matrix (m * m ), the determinant equals the sum of
all the products that can be formed by taking exactly one element from each row
and exactly one element from each column, with certain of the product terms preceded
by a minus sign.
This encryption algorithm takes m successive plaintext letters
and substitutes for them m ciphertext letters. The substitution is determined
by m linear equations in which each character is assigned a numerical value
(a = 0, b = 1, …. , z = 25).
As with Playfair, the strength of the Hill cipher is that it completely hides
single-letter frequencies. Indeed, with Hill, the use of a larger matrix hides more
frequency information. Thus, a 3 * 3 Hill cipher hides not only single-letter but
also two-letter frequency information.
Although the Hill cipher is strong against a ciphertext-only attack, it is
easily broken with a known plaintext attack.

25

Polyalphabetic Ciphers
Polyalphabetic substitution cipher
Improves on the simple monoalphabetic technique by using different monoalphabetic substitutions as one proceeds through the plaintext message
All these techniques have the following features in common:
A set of related monoalphabetic substitution rules is used
A key determines which particular rule is chosen for a given transformation

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Another way to improve on the simple monoalphabetic technique is to use different
monoalphabetic substitutions as one proceeds through the plaintext message.
The general name for this approach is polyalphabetic substitution cipher . All these
techniques have the following features in common:
1. A set of related monoalphabetic substitution rules is used.
2. A key determines which particular rule is chosen for a given transformation.
26

Vigenère Cipher
Best known and one of the simplest polyalphabetic substitution ciphers
In this scheme the set of related monoalphabetic substitution rules consists of the 26 Caesar ciphers with shifts of 0 through 25
Each cipher is denoted by a key letter which is the ciphertext letter that substitutes for the plaintext letter a

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
The best known, and one of the simplest, polyalphabetic ciphers
is the Vigenère cipher. In this scheme, the set of related monoalphabetic substitution
rules consists of the 26 Caesar ciphers with shifts of 0 through 25. Each cipher is
denoted by a key letter, which is the ciphertext letter that substitutes for the plaintext
letter a. Thus, a Caesar cipher with a shift of 3 is denoted by the key value 3.

27

Example of Vigenère Cipher
To encrypt a message, a key is needed that is as long as the message
Usually, the key is a repeating keyword
For example, if the keyword is deceptive, the message “we are discovered save yourself” is encrypted as:
key: deceptivedeceptivedeceptive
plaintext: wearediscoveredsaveyourself
ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
To encrypt a message, a key is needed that is as long as the message. Usually,
the key is a repeating keyword. For example, if the keyword is deceptive, the
message “we are discovered save yourself” is encrypted as
key: deceptivedeceptivedeceptive
plaintext: wearediscoveredsaveyourself
ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ
The strength of this cipher is that there are multiple ciphertext letters for
each plaintext letter, one for each unique letter of the keyword. Thus, the letter
frequency information is obscured. However, not all knowledge of the plaintext
structure is lost. For example, Figure 3.6 shows the frequency distribution for a
Vigenère cipher with a keyword of length 9. An improvement is achieved over the
Playfair cipher, but considerable frequency information remains.
28

Vigenère Autokey System
A keyword is concatenated with the plaintext itself to provide a running key
Example:
key: deceptivewearediscoveredsav
plaintext: wearediscoveredsaveyourself
ciphertext: ZICVTWQNGKZEIIGASXSTSLVVWLA
Even this scheme is vulnerable to cryptanalysis
Because the key and the plaintext share the same frequency distribution of letters, a statistical technique can be applied

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
The periodic nature of the keyword can be eliminated by using a nonrepeating
keyword that is as long as the message itself. Vigenère proposed what is referred to
as an autokey system , in which a keyword is concatenated with the plaintext itself to
provide a running key. For our example,
key: deceptivewearediscoveredsav
plaintext: wearediscoveredsaveyourself
ciphertext: ZICVTWQNGKZEIIGASXSTSLVVWLA
Even this scheme is vulnerable to cryptanalysis. Because the key and the
plaintext share the same frequency distribution of letters, a statistical technique
can be applied. For example, e enciphered by e , by Figure 3.5, can be expected to
occur with a frequency of (0.127)2 = 0.016, whereas t enciphered by t would occur
only about half as often. These regularities can be exploited to achieve successful
cryptanalysis.
29

Vernam Cipher
Figure 3.7 Vernam Cipher

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
The ultimate defense against such a cryptanalysis is to choose a
keyword that is as long as the plaintext and has no statistical relationship to it. Such
a system was introduced by an AT&T engineer named Gilbert Vernam in 1918.
His system works on binary data (bits) rather than letters.
The essence of this technique is the means of construction of the key. Vernam
proposed the use of a running loop of tape that eventually repeated the key, so
that in fact the system worked with a very long but repeating keyword. Although
such a scheme, with a long key, presents formidable cryptanalytic difficulties, it
can be broken with sufficient ciphertext, the use of known or probable plaintext
sequences, or both.

30

One-Time Pad
Improvement to Vernam cipher proposed by an Army Signal Corp officer, Joseph Mauborgne
Use a random key that is as long as the message so that the key need not be repeated
Key is used to encrypt and decrypt a single message and then is discarded
Each new message requires a new key of the same length as the new message
Scheme is unbreakable
Produces random output that bears no statistical relationship to the plaintext
Because the ciphertext contains no information whatsoever about the plaintext, there is simply no way to break the code

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
An Army Signal Corp officer, Joseph Mauborgne, proposed an improvement to the
Vernam cipher that yields the ultimate in security. Mauborgne suggested using a
random key that is as long as the message, so that the key need not be repeated. In
addition, the key is to be used to encrypt and decrypt a single message, and then is
discarded. Each new message requires a new key of the same length as the new message.
Such a scheme, known as a one-time pad , is unbreakable. It produces random
output that bears no statistical relationship to the plaintext. Because the ciphertext
contains no information whatsoever about the plaintext, there is simply no way to
break the code.
In fact, given any plaintext of equal length to the ciphertext, there is a key that
produces that plaintext. Therefore, if you did an exhaustive search of all possible
keys, you would end up with many legible plaintexts, with no way of knowing which
was the intended plaintext. Therefore, the code is unbreakable.
The security of the one-time pad is entirely due to the randomness of
the key. If the stream of characters that constitute the key is truly random, then the
stream of characters that constitute the ciphertext will be truly random. Thus, there
are no patterns or regularities that a cryptanalyst can use to attack the ciphertext.
31

Difficulties
The one-time pad offers complete security but, in practice, has two fundamental difficulties:
There is the practical problem of making large quantities of random keys
Any heavily used system might require millions of random characters on a regular basis
Mammoth key distribution problem
For every message to be sent, a key of equal length is needed by both sender and receiver
Because of these difficulties, the one-time pad is of limited utility
Useful primarily for low-bandwidth channels requiring very high security
The one-time pad is the only cryptosystem that exhibits perfect secrecy (see Appendix F)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
In theory, we need look no further for a cipher. The one-time pad offers complete
security but, in practice, has two fundamental difficulties:
1. There is the practical problem of making large quantities of random keys.
Any heavily used system might require millions of random characters
on a regular basis. Supplying truly random characters in this volume is a
significant task.
2. Even more daunting is the problem of key distribution and protection. For
every message to be sent, a key of equal length is needed by both sender and
receiver. Thus, a mammoth key distribution problem exists.
Because of these difficulties, the one-time pad is of limited utility and is useful
primarily for low-bandwidth channels requiring very high security.
The one-time pad is the only cryptosystem that exhibits what is referred to as
perfect secrecy . This concept is explored in Appendix B.

32

Rail Fence Cipher
Simplest transposition cipher
Plaintext is written down as a sequence of diagonals and then read off as a sequence of rows
To encipher the message “meet me after the toga party” with a rail fence of depth 2, we would write:
m e m a t r h t g p r y
e t e f e t e o a a t
Encrypted message is:
MEMATRHTGPRYETEFETEOAAT

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
All the techniques examined so far involve the substitution of a ciphertext symbol
for a plaintext symbol. A very different kind of mapping is achieved by performing
some sort of permutation on the plaintext letters. This technique is referred to as a
transposition cipher.
The simplest such cipher is the rail fence technique, in which the plaintext is
written down as a sequence of diagonals and then read off as a sequence of rows.
For example, to encipher the message “meet me after the toga party” with a rail
fence of depth 2, we write the following:
m e m a t r h t g p r y
e t e f e t e o a a t
The encrypted message is
MEMATRHTGPRYETEFETEOAAT
33

Row Transposition Cipher
Is a more complex transposition
Write the message in a rectangle, row by row, and read the message off, column by column, but permute the order of the columns
The order of the columns then becomes the key to the algorithm
Key: 4 3 1 2 5 6 7
Plaintext: a t t a c k p
o s t p o n e
d u n t i l t
w o a mx y z
Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
A more complex scheme is
to write the message in a rectangle, row by row, and read the message off, column
by column, but permute the order of the columns. The order of the columns then
becomes the key to the algorithm. For example,
Key: 4 3 1 2 5 6 7
Plaintext: a t t a c k p
o s t p o n e
d u n t i l t
w o a m x y z
Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ
Thus, in this example, the key is 4312567. To encrypt, start with the column
that is labeled 1, in this case column 3. Write down all the letters in that column.
Proceed to column 4, which is labeled 2, then column 2, then column 1, then
columns 5, 6, and 7.
A pure transposition cipher is easily recognized because it has the same letter
frequencies as the original plaintext. For the type of columnar transposition just
shown, cryptanalysis is fairly straightforward and involves laying out the ciphertext
in a matrix and playing around with column positions. Digram and trigram
frequency tables can be useful.
The transposition cipher can be made significantly more secure by performing
more than one stage of transposition. The result is a more complex permutation
that is not easily reconstructed.
34

Summary
Present an overview of the main concepts of symmetric cryptography
Explain the difference between cryptanalysis and brute-force attack
Understand the operation of a monoalphabetic substitution cipher
Understand the operation of a polyalphabetic cipher
Present an overview of the Hill cipher

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Chapter 3 summary.
35

Copyright
This work is protected by United States copyright laws and is provided solely for the use of instructors in teaching their courses and assessing student learning. Dissemination or sale of any part of this work (including on the World Wide Web) will destroy the integrity of the work and is not permitted. The work and materials from it should never be made available to students except by instructors using the accompanying text in their classes. All recipients of this work are expected to abide by these restrictions and to honor the intended pedagogical purposes and the needs of other instructors who rely on these materials.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

36

.MsftOfcThm_Text1_Fill {
fill:#000000;
}
.MsftOfcThm_MainDark1_Stroke {
stroke:#000000;
}