In cryptography, a substitution cipher is a method of encrypting that creates the ciphertext (its output) by replacing units of the plaintext (its input) in a defined manner, with the help of a key; the "units" may be single letters (the most common), pairs of letters, triplets of letters, mixtures of the above, and so forth. The receiver deciphers the text by performing the inverse substitution process to extract the original message.
Substitution ciphers can be compared with transposition ciphers. In a transposition cipher, the units of the plaintext are rearranged in a different and usually quite complex order, but the units themselves are left unchanged. By contrast, in a substitution cipher, the units of the plaintext are retained in the same sequence in the ciphertext, but the units themselves are altered.
There are a number of different types of substitution cipher. If the cipher operates on single letters, it is termed a simple substitution cipher; a cipher that operates on larger groups of letters is termed polygraphic. A monoalphabetic cipher uses fixed substitution over the entire message, whereas a polyalphabetic cipher uses a number of substitutions at different positions in the message, where a unit from the plaintext is mapped to one of several possibilities in the ciphertext and vice versa.
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 AD. The method he described is now known as frequency analysis. __TOC__ Types Simple
The simplest substitution ciphers are the Caesar cipher and Atbash cipher. Here single letters are substituted (referred to as simple substitution). It can be demonstrated by writing out the alphabet twice, once in regular order and again with the letters shifted by some number of steps or reversed to represent the ciphertext alphabet (or substitution alphabet).
The substitution alphabet could also be scrambled in a more complex fashion, in which case it is called a mixed alphabet or deranged alphabet. Traditionally, mixed alphabets may be created by first writing out a keyword, removing repeated letters in it, then writing all the remaining letters in the alphabet in the usual order.
Using this system, the keyword "" gives us the following alphabets: Plaintext alphabet Ciphertext alphabet A message flee at once. we are discovered!
enciphers to
SIAA ZQ LKBA. VA ZOA RFPBLUAOAR!
And the keyword "" gives us the following alphabets:
Plaintext alphabet Ciphertext alphabet The same message flee at once. we are discovered!
enciphers to
MCDD GS JIAD. WD GPD NHQAJVDPDN!
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. These blocks are called "groups", and sometimes a "group count" (i.e. the number of groups) is given as an additional check. Five-letter groups are often used, dating from when messages used to be transmitted by telegraph:
SIAAZ QLKBA VAZOA RFPBL UAOAR
If the length of the message happens not to be divisible by five, it may be padded at the end with "nulls". These can be any characters that decrypt to obvious nonsense, so that the receiver can easily spot them and discard them.
The ciphertext alphabet is sometimes different from the plaintext alphabet; for example, in the pigpen cipher, the ciphertext consists of a set of symbols derived from a grid. 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.
In lists and catalogues for salespeople, a very simple encryption is sometimes used to replace numeric digits by letters. Plaintext digits Ciphertext alphabets David Crawford / Mike Esterl, At Siemens, witnesses cite pattern of bribery, The Wall Street Journal, January 31, 2007: "Back at Munich headquarters, he [Michael Kutschenreuter, a former Siemens-Manager] told prosecutors, he learned of an encryption code he alleged was widely used at Siemens to itemize bribe payments. He said it was derived from the phrase "Make Profit," with the phrase's 10 letters corresponding to the numbers 1-2-3-4-5-6-7-8-9-0. Thus, with the letter A standing for 2 and P standing for 5, a reference to "file this in the APP file" meant a bribe was authorized at 2.55 percent of sales. - A spokesman for Siemens said it has no knowledge of a "Make Profit" encryption system." Examples: MAT would be used to represent 120, PAPR would be used for 5256, and OFTK would be used for 7803.
Security Although the traditional keyword method for creating a mixed substitution alphabet is simple, a serious disadvantage 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 generate the substitution alphabet completely randomly.
Although the number of possible substitution alphabets is very large (26! ≈ 288.4, or about 88 bits), this cipher is not very strong, and is easily broken. 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. This allows formation of partial words, which can be tentatively filled in, progressively expanding the (partial) solution (see frequency analysis for a demonstration of this). In some cases, underlying words can also be determined from the pattern of their letters; for example, the English words tater, ninth, and paper all have the pattern ABACD. Many people solve such ciphers for recreation, as with cryptogram puzzles in the newspaper.
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. In other cases, the plaintext can be contrived to have a nearly flat frequency distribution, and much longer plaintexts will then be required by the cryptanalyst.
Nomenclator
One once-common variant of the substitution cipher is the nomenclator. 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. Originally the code portion was restricted to 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 the ciphertext. The Rossignols' Great Cipher used by King Louis XIV of France was one.
Nomenclators were the standard fare of diplomatic correspondence, espionage, and advanced political conspiracy from the early fifteenth century to the late eighteenth century; most conspirators were and have remained less cryptographically sophisticated. 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.
Homophonic An early attempt to increase the difficulty of frequency analysis attacks on substitution ciphers was to disguise plaintext letter frequencies by homophony. In these ciphers, plaintext letters 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 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 a numeric substitution 'alphabet'. Another method consists of simple variations on the existing alphabet; uppercase, lowercase, upside down, etc. More artistically, though not necessarily more securely, some homophonic ciphers employed wholly invented alphabets of fanciful symbols.
The book cipher is a type of homophonic cipher, one example being the Beale ciphers. This is a story of buried treasure that was described in 1819–21 by use of a ciphered text that was keyed to the United States Declaration of Independence. Here each ciphertext character was represented by a number. The number was determined by taking the plaintext character and finding a word in the Declaration of Independence that started with that character and using the numerical position of that word in the Declaration of Independence as the encrypted form of that letter. Since many words in the Declaration of Independence start with the same letter, the encryption of that character could be any of the numbers associated with the words in the Declaration of Independence that start with that letter. Deciphering the encrypted text character X (which is a number) is as simple as looking up the Xth word of the Declaration of Independence and using the first letter of that word as the decrypted character.
Another homophonic cipher was described by Stahl in 1973Fred Alan Stahl. "A homophonic cipher for computational cryptography".Stahl, Fred A., On Computational Security, University of Illinois, 1974Stahl, Fred A. "A homophonic cipher for computational cryptography ", afips, pp. 565, 1973 Proceedings of the National Computer Conference, 1973 and was one of the first attempts to provide for computer security of data systems in computers through encryption. Stahl constructed the cipher in such a way that the number of homophones for a given character was in proportion to the frequency of the character, thus making frequency analysis much more difficult.
Francesco I Gonzaga, Duke of Mantua, used the earliest known example of a homophonic substitution cipher in 1401 for correspondence with one Simone da Crema.David Salomon. Coding for Data and Computer Communications. Springer, 2005.Fred A. Stahl. "A homophonic cipher for computational cryptography" Proceedings of the national computer conference and exposition (AFIPS '73), pp. 123–126, New York, USA, 1973.
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.
Polyalphabetic
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. 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").