SUBSTITUTION AND CAESAR’S CIPHER

If your mission is to win a war, maintaining secrecy is mission-critical. Ancient
warrior Julius Caesar was extremely eager to disguise written messages, and
he came up with Caesar’s cipher, a simple system that is not particularly secure
once the method is known.

Here’s a slightly simplified version of how it works. Say Caesar wants to
send a written message, FIVE AM, to his generals, instructing them to attack
at that time. In the emperor’s system, each letter in the message FIVE AM is
advanced one place in the alphabet. F becomes G, I becomes J, V becomes W,
and so on. The generals receive GJWF BN, and, knowing that the procedure to
reclaim the message meaning is “subtract 1,” they convert G back to F, J to I,
and so on until the message makes sense.

To aid decoding, Caesar may have given his generals the helpful chart
shown in Figure 2-1.
To encrypt (disguise) a message, you convert each letter of the message to
the letter directly underneath it in the chart. A is converted to B and so on.
Mathematically, this method can be described as follows: message letter + 1
place = encrypted (disguised) letter. Z, the last letter, is converted to A.
A cipher is a method that encrypts or disguises text. The undisguised text is
called plaintext, and the disguised text is called ciphertext. The process of trans-
forming plaintext to ciphertext is called encryption. The reverse is called
decryption. Encipher and encrypt mean the same thing: to confuse or hide mean-
ing. Similarly, decipher and decrypt both mean to remove disguise and reclaim
meaning. See Figure 2-2 for some helpful pictures.


Figure 2-2 Encryption and decryption.


Note that even though it’s called “plaintext,” it could as well be “plain pic-
tures” or “plain audio” or “plain video.”
In Figure 2-1 we used the labels “Plain” and “Ciphered” because Caesar’s
cipher transforms a plain alphabet into a ciphered alphabet. Each letter of
ciphertext substitutes for a letter of plaintext. This is called a substitution cipher.1

Caesar’s cipher combines a method—called, in mathematics, an algorithm—
and a key. The method is “add,” and the key (how many times to do it) is 1.
Julius Caesar’s cipher was actually slightly more complex; he rotated the cipher
alphabet three places. If you understand “F + 1 = G,” it follows that “F + 2 = H”
and “F + 3 = I,” assuming that your cipher alphabet is in alphabetical order. The
F in FIVE becomes I, so FIVE AM translates to ILYH DP (see Figure 2-3).

1. Purists prefer to categorize this as a shift cipher or rotational cipher, a special kind of
substitution.


SUBSTITUTIONAND CAESAR’S CIPHER 9


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

Figure 2-3 Caesar’s cipher variation: rotating each letter three places.


Advancing three letters, instead of one, shows what happens when you add
levels of complexity to a key. An adversary trying to understand your disguised
message must work a little harder to reclaim plaintext from an enciphered mes-
sage that rotates the alphabetic code by three letters (Figure 2-3) than with a
ciphered message that rotates the alphabetic code by one letter (Figure 2-1).

Julius Caesar used the ciphered alphabet in Figure 2-3. His nephew,
Augustus Caesar, said to be less able than his uncle, used the ciphered alphabet
in Figure 2-1. Figures 2-1 and 2-3 show the results of using two Caesar’s cipher
keys—1 and 3, respectively—of 25 possible keys; that is, there are 25 different
ways to disguise letters of the alphabet using a Caesar cipher method.

The concentric alphabet circles in Figure 2-4 can be used to picture any
possible key. The outer ring is fixed and does not rotate. It’s the plaintext alpha-
bet that is used to write the message. The inner, or cipher, circle is the cipher
alphabet used to create the disguised text. Each movement of the inner cipher
circle creates a new cipher alphabet. The diamond shapes in key 1 point to the
letters FIVE AM.

In Figure 2-4, one of the four keys—1, 2, 24, or 25—is displayed inside each
circle. The inner wheel rotates the “key” number of positions: 1, 2, 24, or 25.
After 25, the cipher alphabet has turned full circle and the key returns to 0. In
other words, at “key” 0 the message and ciphertext are the same—oops, not a
disguise!

The key tells how far to move the inner circle alphabet from the initial
position where the A’s in both alphabet circles match—remember, that’s key 0.



The Origin of Cipher
The Arabic sifr is the root from which we get our words cipher and
zero. After the thirteenth century, Europeans began using Arabic nu-
merals rather than Roman numerals because decimals and zeroes made
European medieval mathematicians very happy. But the concept of zero
confused common people in the Middle Ages; so when they referred
to something that wasn’t quite clear, they compared it to something
they considered a mystery: the cipher. Eventually the word cipher
evolved to describe concealment of clear meaning.


Figure 2-4 Four Caesar cipher keys—1, 2, 24, and 25—encrypting FIVE AM.


The four different cipher combinations for the plaintext message FIVE AM are
shown below each cipher circle. Because all the inner cipher circles are in alpha-
betical order, the differing ciphertext is due only to the key, which tells how many
places to rotate the cipher alphabet in relation to the message alphabet.

Cryptanalysis of Caesar’s Cipher

Caesar’s cipher is a little bit confusing if you’ve never seen it, but the confusion
is easy to overcome. To cryptanalyze a message using this cipher, you simply put
the encrypted text on the top row and repeatedly increase each letter one alpha-
betic position (see Figure 2-5). For example, you replace I with J, then K, then
L, and so on. Most trials produce gibberish. When you are successful, the En-
glish plaintext jumps out upon inspection.
It’s important to understand that Caesar’s cipher has only 25 possible keys.
Next, you’ll see other methods with many more possible keys.
Throughout this book the “key” concept is the same. Like Caesar and his
generals, you and your confidant share a key. The object is to make your adver-
sary work a long time trying many, many keys. Hopefully, by the time an

Figure 2-5 Caesar’s cipher cryptanalysis: Meaningful text appears after 23 tries.


adversary finds the correct decrypting key, the encrypted message has little
value. At 5:01, the value of a FIVE AM attack message is greatly reduced. We’ll
see cryptographic methods that put your adversary to work for thousands of
years, just in case unforeseen technological advances permit your adversary to
do in hours what used to take years.

Empowering the Masses

After Gutenberg invented the printing press, more people learned to read. With
more people knowing the reading code, encryption systems such as Caesar’s
cipher were subjected to increasingly educated scrutiny. Secure hiding de-
manded increasingly elaborate encrypting.

Anyone who can read can quickly try all 25 keys. Also, if you figure out just
one letter of ciphertext that corresponds to plaintext, you’ve got the key. For
example, knowing that E is encrypted as K (see Figure 2-6) lets you determine
all the letters in the inside cipher circle by simply filling in the remaining alphabet

in alphabetical order. Well, what to do, what to do? Don’t teach them to read!
Although it may not be ethical or particularly democratic, this approach worked
for quite a long time. Major institutions supported it for centuries (and based on
the reading scores of many American children, perhaps some of them still do).
If you want to keep important secrets hidden from the reading masses, us-
ing 25 alphabetically ordered alphabets does not provide enough complexity. It’s
like using a combination lock that has only 26 numbers on the face—and a one-
number combination key (say, turn to 3) opens the lock.

Locks and Combinations

Imagine that a master locksmith has designed a combination lock and published

the entire inner workings—the nuts and bolts of every mechanism in the lock.

Alice buys a lock and changes the combination. The design is so secure that no

one, not even the locksmith, can figure out the new combination. Of course, this

means that if Alice forgets the combination, no one can open the lock without

trying every combination or breaking the lock.

Further imagine that this one lock design is used to make many locks. Sup-
One lock design

pose Bob also buys a lock and changes the combination. Just like the locksmith
used to make many

who designed the lock, Alice has no clue how to figure out the combination on
locks

Bob’s or anyone else’s lock. So Alice can’t open Bob’s lock, and Bob can’t open
Alice’s lock (see Figure 1-1).

12 Right, 18 Left… 34 Right, 28 Left…
Figure 1-1

Alice’s and Bob’s individual locks are only two of many instances of the
identical lock design.

LOCKS AND KEYS

we begin our explanation of cryptographic concepts with the help of two

people you’ll get to know well in this book: Alice and Bob, a fictitious pair

often used for illustration in cryptography books. Alice and Bob’s first task is to

illustrate the difference between

SECRET KEY CRYPTOGRAPHY

In 1977, two innovations in computer cryptography forever changed 3,500
years of message disguise engineering and brought cryptography closer to be-
ing a tool everyone would need and use. Part I, “Secret Key,” explains the con-
cepts used to develop one of these innovations—Data Encryption Standard
(DES)—and leads into the second innovation, public key cryptography, dis-
cussed in Part II.

Part I describes the current state of secret key computer cryptography. The
first five chapters explain two important concepts:
• Secret key cryptography offers secure ways to store secrets.
• The attacker’s most feasible attack against these secure methods is to
try each possible key.
To prove these two concepts, Chapters 1 through 5 quickly proceed from
ancient to modern cryptographic methods. If you’re familiar with these two
concepts, you may choose to skip to Chapter 6. That said, we believe the first
five chapters offer a quick and instructive overview that will help you understand
secret key cryptographic protective devices.
Chapter 6 shows how cryptography evolved into a mathematical science.
Chapter 7 describes protections and assurances available with secret key
cryptography.
Chapter 8 explains why secret key cryptography, by itself, is not sufficient
to protect communications on the Internet. The bulk of the book and appen-
dixes explain public key cryptography and demonstrate why the Internet
needs it.