Substitution cipher

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Substitution cipher" – news · newspapers · books · scholar · JSTOR (March 2009) (Learn how and when to remove this template message)

In

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 CE. The method he described is now known as frequency analysis.

Types

Simple

Substitution of single letters separately—simple substitution—can be demonstrated by writing out the alphabet in some order to represent the substitution. This is termed a substitution alphabet. The cipher alphabet may be shifted or reversed (creating the Caesar and Atbash ciphers, respectively) or 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 "zebras" gives us the following alphabets:

A message

flee at once. we are discovered!

enciphers to

SIAA ZQ LKBA. VA ZOA RFPBLUAOAR!

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.

Example: MAT would be used to represent 120.

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! ≈ 2^88.4, or about

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

Nomenclators were the standard fare of

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 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^[2][3] and was one of the first^{[citation needed]} 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.

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.^[6]

Polyalphabetic

The work of

In a polyalphabetic cipher, multiple cipher alphabets are used. To facilitate encryption, all the alphabets are usually written out in a large 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 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, 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. 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.^[8] 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 periodicity.
• The running key cipher, where the key is made very long by using a passage from a book or similar text.

Modern stream ciphers 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.

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, '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 (${\displaystyle 26^{2}}$). 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

(probably the first practical trigraphic).

The

random

provided that the matrix is invertible in ${\displaystyle \mathbb {Z} _{26}^{n}}$ (to ensure decryption is possible). A mechanical version of the Hill cipher of dimension 6 was patented in 1929.

The Hill cipher is vulnerable to a

as a type of polygraphic substitution.

Mechanical

This section needs additional citations for verification. Please help improve this article by adding citations to reliable sources in this section. Unsourced material may be challenged and removed. (February 2017) (Learn how and when to remove this template message)

Enigma cipher

machine as used by the German military in World War II

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. Several inventors had similar ideas about the same time, and rotor cipher machines were patented four times in 1919. The most important of the resulting machines was the Enigma, especially in the versions used by the German military from approximately 1930. The Allies also developed and used rotor machines (e.g., SIGABA and Typex).

All of these were similar in that the substituted letter was chosen

As far as is publicly known, no messages protected by the SIGABA and Typex machines were ever broken during or near the time when these systems were in service.

One-time pad

One type of substitution cipher, the

The one-time pad is, in most cases, impractical as it requires that the key material be as long as the plaintext, actually

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.

In modern cryptography

Substitution ciphers as discussed above, especially the older pencil-and-paper hand ciphers, are no longer in serious use. However, the cryptographic concept of substitution carries on even today. From an abstract perspective, modern bit-oriented

• Sherlock Holmes breaks a substitution cipher in "The Adventure of the Dancing Men". There, the cipher remained undeciphered for years if not decades; not due to its difficulty, but because no one suspected it to be a code, instead considering it childish scribblings.
• The
  Standard Galactic Alphabet, the writing system in the Commander Keen video games and in Minecraft
  .
• The
  French
  ).
• The
  Minbari's alphabet from the Babylon 5
  series is a substitution cipher from English.
• The language in
  Krystal is also a substitution cipher of the English alphabet
  .
• The television program Futurama contained a substitution cipher in which all 26 letters were replaced by symbols and called "Alien Language" Archived 2022-12-25 at the Wayback Machine. This was deciphered rather quickly by the die hard viewers by showing a "Slurm" ad with the word "Drink" in both plain English and the Alien language thus giving the key. Later, the producers created a second alien language that used a combination of replacement and mathematical Ciphers. Once the English letter of the alien language is deciphered, then the numerical value of that letter (0 for "A" through 25 for "Z" respectively) is then added (modulo 26) to the value of the previous letter showing the actual intended letter. These messages can be seen throughout every episode of the series and the subsequent movies.
• At the end of every season 1 episode of the cartoon series Gravity Falls, during the credit roll, there is one of three simple substitution ciphers: A -3 Caesar cipher (hinted by "3 letters back" at the end of the opening sequence), an Atbash cipher, or a letter-to-number simple substitution cipher. The season 1 finale encodes a message with all three. In the second season, Vigenère ciphers are used in place of the various monoalphabetic ciphers, each using a key hidden within its episode.
• In the
  Artemis Fowl series by Eoin Colfer
  there are three substitution ciphers; Gnommish, Centaurean and Eternean, which run along the bottom of the pages or are somewhere else within the books.
• In Bitterblue, the third novel by Kristin Cashore, substitution ciphers serve as an important form of coded communication.
• In the 2013 video game BioShock Infinite, there are substitution ciphers hidden throughout the game in which the player must find code books to help decipher them and gain access to a surplus of supplies.
• In the anime adaptation of The Devil Is a Part-Timer!, the language of Ente Isla, called Entean, uses a substitution cipher with the ciphertext alphabet AZYXEWVTISRLPNOMQKJHUGFDCB, leaving only A, E, I, O, U, L, N, and Q in their original positions.