Cryptography Reference
In-Depth Information
and the parchment was sent on its way. The receiver wrapped the parchment
around another baton of the same shape and the original message reappeared.
In his correspondence, Julius Caesar allegedly used a simple letter sub-
stitution method. Each letter of Caesar's message was replaced by the letter
that followed it alphabetically by three places. The letter A was replaced by
D, the letter B by E, and so on. For example, the English word COLD after the
Caesar substitution appears as FROG. This method is still called the Caesar
cipher, regardless of the size of the shift used for the substitution.
These two simple examples already contain the two basic methods of en-
cryption which are still employed by cryptographers today, namely,
transpo-
sition
and
substitution
. In transposition (scytale) the letters of the
plaintext
, the
technical term for the message to be transmitted, are rearranged by a special
permutation. In substitution (Caesar's cipher) the letters of the plaintext are
replaced by other letters, numbers or arbitrary symbols. The two techniques
can be combined to produce more complex ciphers.
Simple substitution ciphers are easy to break. For example, the Caesar
cipher with 25 letters admits any shift between 1 and 25, so it has 25 possible
substitutions (or 26 if you allow the zero shift). One can easily try them all,
one by one. The most general form of one-to-one substitution, not restricted
to the shifts, can generate
26!
or
403
,
291
,
461
,
126
,
605
,
635
,
584
,
000
,
000
(1.1)
possible substitutions. And yet, ciphers based on one-to-one substitutions,
also known as monoalphabetic ciphers, can be easily broken by frequency
analysis. The method was proposed by the ninth-century polymath from
Baghdad, Al-Kindi (800-873
A
.
D
.), often called the philosopher of the Arabs.
Al-Kindi noticed that if a letter in a message is replaced with a different
letter or symbol then the new letter will take on all the characteristics of the
original one. A simple substitution cipher cannot disguise certain features of
the message, such as the relative frequencies of the different characters. Take
the English language: the letter E is the most common letter, accounting for
12.7% of all letters, followed by T (9.0%), then A (8.2%) and so on. This means
that if E is replaced by a symbol X, then X will account for roughly 13% of
symbols in the concealed message, thus one can work out that X actually
represents E. Then we look for the second most frequent character in the
concealed message and identify it with the letter T, and so on. If the concealed
message is sufficiently long then it is possible to reveal its content simply by
analyzing the frequency of the characters.
1.2 Le Chiffre Indechiffrable
In the fifteenth and sixteenth centuries, monoalphabetic ciphers were grad-
ually replaced by more sophisticated methods. At the time, Europe, Italy in
particular, was a place of turmoil, intrigue, and struggle for political and finan-
cial power, and the cloak-and-dagger atmosphere was ideal for cryptography
to flourish.
