Substitution Cipher - Polygraphic Substitution

Polygraphic Substitution

In a polygraphic substitution cipher, plaintext letters are substituted in larger groups, instead of substituting letters individually. The first advantage is that the frequency distribution is much flatter than that of individual letters (though not actually flat in real languages; for example, 'TH' is much more common than 'XQ' in English). Second, the larger number of symbols requires correspondingly more ciphertext to productively analyze letter frequencies.

To substitute pairs of letters would take a substitution alphabet 676 symbols long . In the same De Furtivis Literarum Notis mentioned above, della Porta actually proposed such a system, with a 20 x 20 tableau (for the 20 letters of the Italian/Latin alphabet he was using) filled with 400 unique glyphs. However the system was impractical and probably never actually used.

The earliest practical digraphic cipher (pairwise substitution), was the so-called Playfair cipher, invented by Sir Charles Wheatstone in 1854. 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. Playfair was in military use from the Boer War through World War II.

Several other practical polygraphics were introduced in 1901 by Felix Delastelle, including the bifid and four-square ciphers (both digraphic) and the trifid cipher (probably the first practical trigraphic).

The Hill cipher, invented in 1929 by Lester S. Hill, is a polygraphic substitution which can combine much larger groups of letters simultaneously using linear algebra. 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 (to ensure decryption is possible). A Hill cipher of dimension 6 was once implemented mechanically.

The Hill cipher is vulnerable to a known-plaintext attack because it is completely linear, so it must be combined with some non-linear step to defeat this attack. The combination of wider and wider weak, linear diffusive steps like a Hill cipher, with non-linear substitution steps, ultimately leads to a substitution-permutation network (e.g. a Feistel cipher), so it is possible – from this extreme perspective – to consider modern block ciphers as a type of polygraphic substitution.