Cryptography Reference
In-Depth Information
In the 1460s Leone Battista Alberti (1404-1472), better known as an archi-
tect, invented a device based on two concentric discs that simplified the use
of Caesar ciphers. The substitution, i.e., the relative shift of the two alphabets,
is determined by the relative rotation of the two disks (Figure 1.1).
Rumor has it that Alberti also considered changing the substitution within
one message by turning the inner disc in his device. It is believed that this is
how he discovered the so-called polyalphabetic ciphers, which are based on
superpositions of Caesar ciphers with different shifts. For example, the first
letter in the message can be shifted by 7, the second letter by 14, the third by
19, the fourth again by 7, the fifth by 14, the sixth by 19, and so on repeating the
shifts 7, 14, 19 throughout the whole message. The sequence of numbers — in
this example 7, 14, 19 — is usually referred to as a cryptographic key. Using
this particular key we transform the message SELL into its concealed version,
which reads ZSES.
As said, the message to be concealed is called the plaintext; the opera-
tion of disguising it is known as encryption. The encrypted plaintext is called
the ciphertext or cryptogram. Our example illustrates the departure from a
simple substitution; the repeated L in the plaintext SELL is enciphered differ-
ently in each case. Similarly, the two S's, in the ciphertext represent different
letters in the plaintext: the first S corresponds to the letter E and the second
to the letter L. This makes the straightforward frequency analysis of char-
acters in ciphertexts obsolete. Indeed, polyalphabetic ciphers invented by
the main contributors to the field at the time, such as Johannes Trithemius
(1462-1516), Blaise de Vigenre (1523-1596), and Giovanni Battista Della Porta
(1535-1615), were considered unbreakable for at least another 200 years.
Indeed,
Vigenre
himself
confidently
dubbed
his
invention
“le
chiffre
indechiffrable”—the unbreakable cipher.
1.3 Not So Unbreakable
The first description of a systematic method of breaking polyalphabetic ci-
phers was published in 1863 by the Prussian colonel Friedrich Wilhelm Kasiski
(1805-1881), but, according to some sources (for example, Simon Singh,
The Code Book
), Charles Babbage (1791-1871) had worked out the same method
in private sometime in the 1850s.
The basic idea of breaking polyalphabetic ciphers is based on the obser-
vation that if we use N different substitutions in a periodic fashion then every
Nth character in the cryptogram is enciphered with the same monoalphabetic
cipher. In this case we have to find N, the length of the key and apply fre-
quency analysis to subcryptograms composed of every Nth character of the
cryptogram.
But how do we find N? We look for repeated sequences in the ciphertext.
If a sequence of letters in the plaintext is repeated at a distance which is a mul-
tiple of N, then the corresponding ciphertext sequence is also repeated. For
example, for N
=
3, with the 7, 14, 19 shifts, we encipher TOBEORNOTTOBE
