Substitution cipher

A substitution cipher is a cipher that replaces each plaintext symbol for another ciphertext symbol. The receiver decodes using the inverse substitution. A substitution alphabet is the extended list of ciphertext symbols. Examples are Caesar ciphers (such as ROT13) and the atbash cipher.

Simple

The simple substitution cipher is one in which each plaintext character is simply replaced by a corresponding one from a cipher alphabet. The cipher alphabet may be shifted or reversed (creating the Caesar cipher and atbash ciphers, respectively) or scrambled, in which case it is called a "mixed alphabet" or "deranged alphabet". Traditionally, mixed alphabets are created by first writing out a keyword, then all the remaining letters. For example, with a keyword of 'ZEBRAS' we get:

Plaintext:

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

Ciphertext:

Z

E

B

R

A

S

C

D

F

G

H

I

J

K

L

M

N

O

P

Q

T

U

V

W

X

Y

A message of 'Flee at once. We are discovered' enciphers to:

SIAAZ QLKBA VAZOA RFPBL UAOAR

(Traditionally, the ciphertext is written out in blocks of fixed length, to help avoid errors). A disadvantage of this method of derangement is that the last letters of the alphabet (which are mostly low frequency) tend to stay at the end. A stronger way of constructing a mixed alphabet is to perform a columnar transposition on the ordinary alphabet using the keyword, but this is not often done.

Although the number of possible keys is very large ( $26!\approx 2^{88.4}$ , or about 88 bits), this cipher is not very strong; provided the message is of reasonable length, by analysing the frequency distribution of the ciphertext, the cryptanalyst can deduce the probable meaning of the most common symbols. This allows formation of partial words, which can be tentatively filled in, progressively expanding the solution. Many people solve such ciphers for recreation. According to the unicity distance concept, 27.6 letters of ciphertext are required to crack a mixed alphabet simple substitution. In practice, typically about 50 letters are needed, although some can be done with fewer if particular unusual patterns are found, while in others the plaintext is cunningly contrived to have a nearly flat frequency distribution, and much longer plaintexts are required.

Homophonic

The first attempt to deal with the frequency analysis problem with a simple substitution was the homophonic. In this cipher, plaintext letters can map to more than one ciphertext symbol. Usually, the highest frequency plaintext symbols are given more equivalents than lower frequency letters. In this way, the frequency distribution is flattened, making analysis much more difficult.

Since more than 26 characters will be required in the ciphertext alphabet, various solutions are employed to invent larger alphabets. Perhaps the simplest is to use numbers. Another method consists of simple variations on the existing alphabet; uppercase, lowercase, upside down, etc. More artistically, some homophonic ciphers employed wholly invented alphabets of fanciful symbols.

An interesting variant is the nomenclator. Named after the public official who announced the titles of visting dignitaries, this cipher combined a limited code with very large homophonic substitution tables.]] Originally the code just covered the names of important people, hence the name of the cipher; in later years it covered many common words and place names as well. The symbols for whole words (codewords in modern parlance) and letters (cipher in modern parlance) were not distinguished in any particular way.

Nomenclators were the standard fare of diplomatic correspondence and political conspiracy from the early fifteenth century to the late eighteenth century. Although government intelligence cryptanalysts were systematically breaking nomenclators by the mid-sixteenth century, and superior systems had been available since 1467, the usual response to cryptanalysis was simply to make the tables larger. By the late eighteenth century when the system was beginning to die out, some nomenclators had 50,000 symbols!

Nevertheless, not all nomenclators were broken; today, cryptanalysis of archived ciphertexts remains a fruitful area of historical research.

The book cipher is a type of homophonic.

Polyalphabetic

Polyalphabetic substitution was first described in 1467 by Leon Battista Alberti in the form of code disks. In 1518 by the monk Johannes Trithemius, in his book Steganographia (Ancient Greek for "hidden writing") introduced the now more standard form of a tableau (see below). A more sophisticated version using mixed alphabets was described in 1563 by Giovanni Battista della Porta in his book, De Furtivis Literarum Notis (Latin for "On concealed characters in writing").

In a polyalphabetic cipher, multiple cipher alphabets are used. To facilitate encryption, normally all the alphabets are written out in a large table, traditionally called a tableau. Usually the tableau is 26 x 26, so that 26 full ciphertext alphabets are available. The method of filling the tableau, and of chosing which alphabet to use next, define the particular polyalphabetic. One of the most popular and sophisticated was that of Blaise de Vigenère, first published in 1585, it was considered unbreakable until 1883, and indeed was commonly called le chiffre indéchiffrable (French for "undecipherable cipher").

In the Vigenère cipher, the first row of the tableau is filled out with a copy of the plaintext alphabet, and successive rows are simply shifted one place to the left. (Such a simple tableau is called a tabula recta, and mathemtically corresponds to adding the plaintext and ciphertext letters, modulo 26.) A keyword is then then used to choose which ciphertext alphabet to use. Each letter of the keyword is used in turn, and then they are repeated again from the beginning. So if the keyword is 'CAT', the first letter of plaintext is enciphered under alphabet 'C', the second under 'A', the third under 'T', the fourth under 'C' again, and so on. In practice, Vigenère keys were often phrases several words long.

In 1883, Friedrich Kasiski published a method (probably earlier known by Charles Babbage) which enabled the calculation of the length of the keyword in a Vigenère. Once this was done, ciphertext letters that had been enciphered under the same alphabet could be picked out and attacked separately as a number of semi-independent simple substitutions - complicated by the fact that within one alphabet letters were separated and did not form complete words, but simplified by the fact that usually a tabula recta had been employed.

As such, even today a Vigenère type cipher should theoretically be strong if mixed alphabets are used in the tableau, the keyword is random, and the total length of ciphertext is less than 27.6 times the length of the keyword.

Other notable polyalphabetics include:

The Gronsfeld cipher. This is identical to the Vigen&egrave except that only 10 alphabets are used, and so the "keyword" is numerical.
The Beaufort cipher. This is practically the same as the Vigenère, except the tabula recta is replaced by a backwards one, mathematically equivalent to ciphertext = key - plaintext. This operation is self-inverse, so that exactly the same table is used in exactly the same way, for both encryption and decryption.
The autokey cipher, which mixes plaintext in to the keying to avoid periodicity in the key.
The running key cipher, where the key is made very long by using a passage from a book or similar text.

Modern stream ciphers are also a form of polyalphabetic, but one in which the security has gone entirely into making the keystream as long and unpredictable as possible.

Polygraphic

In a polygraphic system, instead of substituting letters individually, they are substituted in larger groups - typically pairs, which makes a digraphic cipher. The advantage of this is firstly that the frequency distribution of digraphs is much flatter than that of individual letters (though not actually flat; for example 'TH' is much more common than 'XQ'!); and secondly that the larger number of symbols requires correspondingly more ciphertext to analyse the frequencies.

Because $26^{2}=676$ , to do this with a substitution alphabet would take an alphabet 676 symbols long, which would be rather cumbersome. In the same De Furtivis Literarum Notis mentioned above under Polyalphabetics, della Porta actually proposed such a system, with a 26 x 26 tableau filled with 676 unique glyphs. However the system was very impractical and never used. Hence algebraic or geometric methods are used to construct the substitution from simple operations.

The earliest practical digraphic substitution was the so-called Playfair cipher, actually invented by Sir Charles Wheatstone in 1854. It was in military use from the Boer War to World War II. In this cipher, a 5 x 5 grid is filled with the letters of a mixed alphabet (two letters, usually I and J, are combined). A digraphic substitution is then simulated by taking pairs of letters as two corners of a rectangle, and using the other two corners as the ciphertext (see the Playfair cipher main article for a diagram). Special rules handle double letters and pairs falling in the same row or column.

The Hill cipher is a polygraphic substitution which can combine much larger groups of letters simultaneously, using linear algebra. It was invented in 1929 by Lester S. Hill. Each letter is treated as a digit in base 26: A = 0, B =1, and so on. (In a variation, 3 extra symbols are added to make the basis prime.)A block of n letters is then considered as a vector of n dimensions, and multiplied by a n x n matrix, modulo 26. The components of the matrix are the key, and should be random provided that the matrix is invertible in $GF(26^{n})$ (to ensure decryption is possible). Astonishingly, a Hill cipher of dimension 2 was once implemented mechanically!

Unfortunately, the Hill cipher is very vulnerable to a known plaintext attack because it is completely linear, so it must be combined with some non-linear step for security. The combination of wider and wider weak, linear diffusive steps like a Hill cipher, with non-linear substitution steps, ultimately leads us to a substitution-permutation network (e.g. Feistel cipher), so a block cipher can be considered the ultimate polygraphic substitution.

Modern

Modern Feistel ciphers such as DES and Rijndael are similar in principle to substitution ciphers. They treat each 64-bit or 128-bit block of the plaintext as a symbol and perform several rounds of substitutions and transpositions on the bits in the block to approximate a general block-to-block substitution. The various block cipher modes of operation are analogous to the various polyalphabetics, while "randomized encryption" is similar to a homophonic substitution.