What is a substitution cipher?
A substitution cipher is a method of encryption by which units of plaintext are replaced with ciphertext according to a fixed system. The "units" may be single letters, pairs of letters, triplets of letters, mixtures of the above, and so forth. The receiver deciphers the text by performing an inverse substitution. This type of cipher is one of the simplest and oldest methods of encoding messages, with its origins tracing back to ancient civilizations.
In a substitution cipher, the key is the rule that defines the substitution process. The simplest form of substitution cipher is the Caesar cipher, named after Julius Caesar, who reportedly used it in his private correspondence. In the Caesar cipher, each letter in the plaintext is shifted a certain number of places down or up the alphabet. For instance, with a shift of three positions, A would be replaced by D, B by E, C by F, and so forth. After the letter Z, the alphabet wraps around to the beginning, so X would be replaced by A, Y by B, and Z by C.
To illustrate, consider the plaintext message "HELLO". Using a Caesar cipher with a shift of three, the message would be encrypted as follows:
– H (shifted by 3) -> K
– E (shifted by 3) -> H
– L (shifted by 3) -> O
– L (shifted by 3) -> O
– O (shifted by 3) -> R
Thus, "HELLO" becomes "KHOOR".
The Caesar cipher is a specific instance of a more general class of substitution ciphers known as monoalphabetic substitution ciphers. In a monoalphabetic substitution cipher, each letter of the plaintext is mapped to a unique letter of the ciphertext alphabet. Unlike the Caesar cipher, which uses a uniform shift, a monoalphabetic substitution cipher can use any permutation of the alphabet. For example, the plaintext alphabet "ABCDEFGHIJKLMNOPQRSTUVWXYZ" might be mapped to the ciphertext alphabet "QWERTYUIOPASDFGHJKLZXCVBNM". Using this mapping, the plaintext "HELLO" would be encrypted as:
– H -> I
– E -> T
– L -> S
– L -> S
– O -> G
Thus, "HELLO" becomes "ITSSG".
The security of a substitution cipher relies on the secrecy of the key, which in this case is the substitution rule. If the key is known or can be discovered, the cipher can be easily broken. In practice, monoalphabetic substitution ciphers are vulnerable to frequency analysis, a technique that involves studying the frequency of letters or groups of letters in the ciphertext. Since certain letters and combinations of letters appear more frequently in natural language, an analyst can use this information to deduce the substitution rule.
For example, in English, the letter 'E' is the most common, followed by 'T', 'A', 'O', 'I', 'N', 'S', 'H', 'R', and so on. By comparing the frequency of letters in the ciphertext to the known frequency of letters in the language, an analyst can make educated guesses about the substitution rule. This method was famously used by the Arab mathematician and polymath Al-Kindi in the 9th century to break monoalphabetic substitution ciphers.
To mitigate the weaknesses of monoalphabetic substitution ciphers, polyalphabetic substitution ciphers were developed. In a polyalphabetic substitution cipher, multiple substitution rules are used, and the rule applied to each letter of the plaintext changes according to a predetermined scheme. One of the most well-known polyalphabetic ciphers is the Vigenère cipher, named after the French cryptographer Blaise de Vigenère.
The Vigenère cipher uses a keyword to determine the substitution rule for each letter of the plaintext. The keyword is repeated to match the length of the plaintext, and each letter of the keyword specifies a shift in the alphabet, similar to the Caesar cipher. For example, if the keyword is "KEY" and the plaintext is "HELLO", the keyword is repeated to form "KEYKE". The encryption process is as follows:
– H (shifted by K, which is 10 positions) -> R
– E (shifted by E, which is 4 positions) -> I
– L (shifted by Y, which is 24 positions) -> J
– L (shifted by K, which is 10 positions) -> V
– O (shifted by E, which is 4 positions) -> S
Thus, "HELLO" becomes "RIJVS".
The Vigenère cipher is more secure than the monoalphabetic substitution cipher because it obscures the frequency patterns of the plaintext. However, it is still vulnerable to cryptanalysis, particularly if the keyword is short or if the ciphertext is long enough to reveal repeating patterns. Techniques such as the Kasiski examination and the Friedman test can be used to break the Vigenère cipher by identifying the length of the keyword and then applying frequency analysis to each segment of the ciphertext.
Another notable polyalphabetic substitution cipher is the Enigma machine, used by the Germans during World War II. The Enigma machine employed a complex system of rotating disks, or rotors, to generate a polyalphabetic substitution cipher. Each rotor provided a different substitution rule, and the rotors rotated after each letter was encrypted, changing the substitution rule dynamically. The Enigma machine also included a plugboard that further scrambled the letters, adding an additional layer of complexity.
The security of the Enigma machine relied on the secrecy of the rotor settings and the plugboard connections. However, the machine was ultimately broken by Allied cryptanalysts, most notably by the Polish mathematician Marian Rejewski and the British mathematician Alan Turing. The breaking of the Enigma cipher is considered one of the most significant achievements in the history of cryptography and had a profound impact on the outcome of World War II.
In addition to monoalphabetic and polyalphabetic substitution ciphers, there are also homophonic substitution ciphers. In a homophonic substitution cipher, each letter of the plaintext can be replaced by one of several possible symbols in the ciphertext. This approach aims to flatten the frequency distribution of the ciphertext, making frequency analysis more difficult. For example, the letter 'E' in the plaintext might be replaced by any of the symbols '1', '2', or '3' in the ciphertext, while the letter 'T' might be replaced by '4' or '5'. By using multiple symbols for common letters, the homophonic substitution cipher reduces the predictability of the ciphertext.
Despite their historical significance, substitution ciphers are not considered secure by modern cryptographic standards. Advances in cryptanalysis and computational power have rendered these ciphers vulnerable to various attacks. Modern encryption algorithms, such as the Advanced Encryption Standard (AES) and the Rivest-Shamir-Adleman (RSA) algorithm, use more sophisticated mathematical techniques to provide a higher level of security. However, understanding substitution ciphers is essential for appreciating the evolution of cryptographic methods and the foundational principles of encryption.
In the context of modular arithmetic, substitution ciphers can be viewed as functions that map elements of a finite set (such as the alphabet) to other elements of the same set. For example, the Caesar cipher can be described using modular arithmetic as follows: Let 
be the numerical position of a letter in the alphabet (with A = 0, B = 1, …, Z = 25), and let 
be the shift value. The encryption function 
is given by 
, and the decryption function 
is given by 
, where 
is the numerical position of the ciphertext letter. This mathematical formulation highlights the cyclical nature of the Caesar cipher and its reliance on modular arithmetic.
Substitution ciphers, including monoalphabetic, polyalphabetic, and homophonic variants, represent a fundamental class of encryption techniques with a rich historical legacy. While their simplicity and elegance have made them popular throughout history, their vulnerabilities to cryptanalysis have driven the development of more advanced cryptographic methods. Studying substitution ciphers provides valuable insights into the principles of encryption and the challenges of secure communication.
Other recent questions and answers regarding EITC/IS/CCF Classical Cryptography Fundamentals:
- Was public-key cryptography introduced for use in encryption?
- Is the set of all possible keys of a particular cryptographic protocol referred to as the keyspace in cryptography?
- In a shift cipher, are the letters at the end of the alphabet replaced with letters from the beginning of the alphabet according to modular arithmetic?
- What should a block cipher include according to Shannon?
- Was the DES protocol introduced to improve the security of AES cryptosystems?
- Does the security of block ciphers depend on combining confusion and diffusion operations many times?
- Do the encryption and decryption functions need to be kept secret for the cryptographic protocol to remain secure?
- Can cryptanalysis be used to communicate securely over an insecure communication channel?
- Do Internet, GSM, and wireless networks belong to the insecure communication channels?
- Is an exhaustive key search effective against substitution ciphers?
View more questions and answers in EITC/IS/CCF Classical Cryptography Fundamentals