Editing Substitution cipher (section)

=== Polyalphabetic ===
{{Main|Polyalphabetic cipher}}

The work of [[Al-Qalqashandi]] (1355-1418), based on the earlier work of [[Ibn al-Durayhim]] (1312–1359), contained the first published discussion of the substitution and transposition of ciphers, as well as the first description of a polyalphabetic cipher, in which each plaintext letter is assigned more than one substitute.<ref>{{cite book |last1=Lennon |first1=Brian |title=Passwords: Philology, Security, Authentication |date=2018 |publisher=[[Harvard University Press]] |isbn=9780674985377 |page=26 |url=https://books.google.com/books?id=jbpTDwAAQBAJ&pg=PT26}}</ref> Polyalphabetic substitution ciphers were later described in 1467 by [[Leone Battista Alberti]] in the form of disks. [[Johannes Trithemius]], in his book ''Steganographia'' ([[Ancient Greek]] for "hidden writing") introduced the now more standard form of a ''tableau'' (see below; ca. 1500 but not published until much later). 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, all the alphabets are usually written out in a large [[table (information)|table]], traditionally called a ''tableau''. The tableau is usually 26×26, so that 26 full ciphertext alphabets are available. The method of filling the tableau, and of choosing which alphabet to use next, defines the particular polyalphabetic cipher. All such ciphers are easier to break than once believed, as substitution alphabets are repeated for sufficiently large plaintexts.

One of the most popular was that of [[Blaise de Vigenère]]. First published in 1585, it was considered unbreakable until 1863, and indeed was commonly called ''le chiffre indéchiffrable'' ([[French language|French]] for "indecipherable 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 mathematically corresponds to adding the plaintext and key letters, [[modular arithmetic|modulo]] 26.) A keyword is 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, or if the keyword is 'RISE', the first letter of plaintext is enciphered under alphabet 'R', the second under 'I', the third under 'S', the fourth under 'E', and so on. In practice, Vigenère keys were often phrases several words long.

In 1863, [[Friedrich Kasiski]] published a method (probably discovered secretly and independently before the [[Crimean War]] by [[Charles Babbage]]) which enabled the calculation of the length of the keyword in a Vigenère ciphered message. 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 difficult to break if mixed alphabets are used in the tableau, if the keyword is random, and if the total length of ciphertext is less than 27.67 times the length of the keyword.<ref>{{Cite journal|last=Toemeh|first=Ragheb|year=2014|title=Certain investigations in Cryptanalysis of classical ciphers Using genetic algorithm|journal=Shodhganga|hdl=10603/26543}}</ref> These requirements are rarely understood in practice, and so Vigenère enciphered message security is usually less than might have been.

Other notable polyalphabetics include:
* The Gronsfeld cipher. This is identical to the Vigenère 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'', whereby the same table is used for both encryption and decryption.
* The [[autokey cipher]], which mixes plaintext with a key to avoid [[periodic function|periodic]]ity.
* The [[running key cipher]], where the key is made very long by using a passage from a book or similar text.

Modern [[stream cipher]]s can also be seen, from a sufficiently abstract perspective, to be a form of polyalphabetic cipher in which all the effort has gone into making the [[keystream]] as long and unpredictable as possible.