Substitution cipher

The first ever published description of how to crack simple substitution ciphers was given by Al-Kindi in A Manuscript on Deciphering Cryptographic Messages written around 850 CE.

Using this system, the keyword "zebras" gives us the following alphabets: A message enciphers to And the keyword "grandmother" gives us the following alphabets: The same message enciphers to Usually the ciphertext is written out in blocks of fixed length, omitting punctuation and spaces; this is done to disguise word boundaries from the plaintext and to help avoid transmission errors.

For example: Such features make little difference to the security of a scheme, however – at the very least, any set of strange symbols can be transcribed back into an A-Z alphabet and dealt with as normal.

Provided the message is of reasonable length (see below), the cryptanalyst can deduce the probable meaning of the most common symbols by analyzing the frequency distribution of the ciphertext.

According to the unicity distance of English, 27.6 letters of ciphertext are required to crack a mixed alphabet simple substitution.

In practice, typically about 50 letters are needed, although some messages can be broken with fewer if unusual patterns are found.

Named after the public official who announced the titles of visiting dignitaries, this cipher uses a small code sheet containing letter, syllable and word substitution tables, sometimes homophonic, that typically converted symbols into numbers.

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.

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

More artistically, though not necessarily more securely, some homophonic ciphers employed wholly invented alphabets of fanciful symbols.

Francesco I Gonzaga, Duke of Mantua, used the earliest known example of a homophonic substitution cipher in 1401 for correspondence with one Simone de Crema.

[4][5] Mary, Queen of Scots, while imprisoned by Elizabeth I, during the years from 1578 to 1584 used homophonic ciphers with additional encryption using a nomenclator for frequent prefixes, suffixes, and proper names while communicating with her allies including Michel de Castelnau.

Johannes Trithemius, in his book Steganographia (Ancient Greek for "hidden writing") introduced the now more standard form of a tableau (see below; ca.

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").

To facilitate encryption, all the alphabets are usually written out in a large table, traditionally called a tableau.

First published in 1585, it was considered unbreakable until 1863, and indeed was commonly called le chiffre indéchiffrable (French for "indecipherable cipher").

(Such a simple tableau is called a tabula recta, and mathematically corresponds to adding the plaintext and key letters, modulo 26.)

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.

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.

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.

Between around World War I and the widespread availability of computers (for some governments this was approximately the 1950s or 1960s; for other organizations it was a decade or more later; for individuals it was no earlier than 1975), mechanical implementations of polyalphabetic substitution ciphers were widely used.

It was mathematically proven unbreakable by Claude Shannon, probably during World War II; his work was first published in the late 1940s.

The one-time pad is, in most cases, impractical as it requires that the key material be as long as the plaintext, actually random, used once and only once, and kept entirely secret from all except the sender and intended receiver.

Soviet one-time pad messages sent from the US for a brief time during World War II used non-random key material.

(See Venona project) In a mechanical implementation, rather like the Rockex equipment, the one-time pad was used for messages sent on the Moscow-Washington hot line established after the Cuban Missile Crisis.