Editing Substitution cipher (section)

=== Polygraphic ===
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, 'OS' is much more common than 'RÑ' in Spanish). 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 (<math>26^2</math>). 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 [[glyph]]s. 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 [[Second Boer War|Boer War]] through [[World War II]].

Several other practical polygraphics were introduced in 1901 by [[Felix Delastelle]], including the [[bifid cipher|bifid]] and [[four-square cipher]]s (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 [[numeral system|base 26]]: A = 0, B =1, and so on. (In a variation, 3 extra symbols are added to make the [[basis (linear algebra)|basis]] [[prime number|prime]].) A block of n letters is then considered as a [[vector space|vector]] of n [[dimension]]s, and multiplied by a n x n [[matrix (mathematics)|matrix]], [[modular arithmetic|modulo]] 26. The components of the matrix are the key, and should be [[random]] provided that the matrix is invertible in <math>\mathbb{Z}_{26}^n</math> (to ensure decryption is possible). A mechanical version of the Hill cipher of dimension 6 was patented in 1929.<ref>{{cite web|title=Message Protector patent US1845947|date=February 14, 1929|url=https://patents.google.com/patent/US1845947|access-date=November 9, 2013}}</ref>

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 [[confusion and diffusion|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 cipher]]s as a type of polygraphic substitution.