Prehistory of Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 4

1.1.3 Transpositions, Substitutions, and Secret Keys

In the antiquity, Spartan warriors used to encrypt messages by using scytales. These
were cylinders around which they wrapped a leather belt. Encryption was performed
by writing the message on a leather belt along the axis of the cylinder and unwrapping
the belt. Decryption was performed by wrapping the belt around a cylinder of the same
diameter and reading along the axis.

Obviously, this encryption consists of changing the order of the characters in the
message, according to a secret permutation called transposition .

Later in Rome, Caesar used another cryptographic system which consisted of
replacing every character by the character which comes three positions later in
the alphabet. Following the Latin alphabet of Caesar 5 , the substitution was as fol-
lows.

abcdefghiklmnopqrstvx
DEFGHIKLMNOPQRSTVXABC

For instance, the plaintext caesar was encrypted into FDHXDV . 6 The Caesar Cipher
generalizes into the simple substitution cipher : we encrypt by replacing every character
by another one obtained by a secret permutation of the alphabet. We decrypt by replacing
every character by another one obtained by the inverse permutation of the alphabet.
The permutation is called a substitution .

The UNIX community is already familiar with the ROT13 substitution which shifts
the alphabet by 13 positions as follows.

abcdefghijklmnopqrstuvwxyz
NOPQRSTUVWXYZABCDEFGHIJKLM

This makes it an involution: rotating twice by 13 positions consists of rotating by 26
positions. Since 26 is the exact size of the alphabet, this rotation is a complete rotation
which leads to no transform at all.

It is quite easy to break a simple substitution cipher by using frequencies of char-
acter in human language. We can, for instance, use the frequencies of characters in
English texts as given in Fig. 1.1. We can also use frequent digrams or trigrams. Here

5

Most textbooks on cryptography describe the Caesar cipher with a 26-character alphabet, which is a little
anachronic. There were only 21 characters at this time. Characters Y and Z were foreign characters, used
in order to transcript Greek words. Characters I and J were the same one, I . Characters U and V were
also the same ( V ). Character W did not exist.

6

Writing ciphertext with capital letters and plaintext with small letters is a common convention.