Substitution Cipher

ELI5

Imagine you have two identical sets of the alphabet. You lay them side-by-side and draw arrows from the first set to the second. As long as every letter points to exactly one unique letter, you have a cipher.

Let $\mathcal{A}$ be our alphabet (e.g., $A$ to $Z$ ). A monoalphabetic substitution cipher is defined by a permutation function $\pi$ :

\pi: \mathcal{A} \rightarrow \mathcal{A}

The Key: The specific map you chose. The key space size is $|\mathcal{A}|!$ .
Encryption ( $E$ ): For every letter in your message $m$ , you look it up on your map.
$E_{\pi}(m) = \pi(m_1)\pi(m_2)...\pi(m_n)$
Decryption ( $D$ ): You follow the arrows backward.
$D_{\pi}(c) = \pi^{-1}(c_1)\pi^{-1}(c_2)...\pi^{-1}(c_n)$

🧸 Toy Example:

If our alphabet is only $\{A, B, C\}$ and our key ( $\pi$ ) is $\{A \to B, B \to C, C \to A\}$ :

Plaintext: $ABA$
Ciphertext: $BCB$

Julius “Script Kiddie” Caesar

The most famous version of substitution cipher is the Caesar Cipher, used by Julius Caesar of Roman Empire. He used a fixed shift of three positions to communicate securely with his generals. In 50 BCE, the “attacker” (Gaulish tribes or political rivals) often couldn’t read at all. Even for the literate elite, the concept that text could be systematically scrambled was a foreign idea.

The Substitution Family Tree (Variations)

Not all substitutions are created equal. Here are the other “flavors”:

Atbash Cipher: The “reverse” cipher. $A \leftrightarrow Z, B \leftrightarrow Y$ . It’s basically the “Mirror Dimension” of substitutions. Historically used in Hebrew texts.
Affine Cipher: A bit more mathy. It uses a linear function: $E(x) = (ax + b) \mod 26$ . It’s like a Caesar Cipher but with a multiplication “spice” added.
Polybius Square: This turns letters into coordinates (e.g., $A = 1,1$ ). It’s a substitution that also acts as a “reduction” from letters to numbers.
Pigpen Cipher: A geometric substitution where letters are replaced by symbols based on a grid. Meme status: 10-year-old me feeling like a master hacker.

Why It’s Actually Trash

Substitution ciphers provide essentially no security against anyone with a brain and a bit of math (under modern scenarios). Al-Kindi¹, working out of the Abbasid Caliphate, basically ended the Caesar Cipher’s career by documenting frequency analysis. He realized that if you count the symbols, the language’s “fingerprint” stays the same as letters aren’t distributed equally. For example in English, ‘E’ is the main character ( $12.7\%$ ), and ‘Z’ is the background extra ( $0.07\%$ ). If the most common symbol in your ciphertext is “X,” “X” is probably “E.”

The Modern Cryptography

To go from “hiding notes in class” to “protecting global finance,” we had to stop being deterministic. $\rightarrow$ Polyalphabetic Cipher

This guy lived in the 9th - the family of Substitution Cipher was essentially destroyed if given enough ciphertext for frequency analysis since then. While much of the world was still figuring out basic governance, the Arab were already performing statistical attacks on encryption. ↩