Substitution

Substitution is one of the two great historical principles of encryption, the other being transposition. To substitute is to replace each plaintext element by another symbol according to a fixed or shifting rule. The plaintext ATTACK may become DWWDFN (substitution), but stays ATTACK after transposition (just rearranged: TKCATA). Both families have their strengths, weaknesses, and combine in every modern cipher.

Four sub-families

1. Monoalphabetic substitution

A single fixed table. Each letter always becomes the same other letter. Key space ranges from modest to huge depending on the variant:

• Caesar: integer shift (25 keys). The grandfather.
• Atbash: alphabet mirror (1 transformation, no key).
• ROT13: shift 13 (1 self-inverse transformation).
• Affine: c = a × p + b (312 keys).
• General monoalphabetic substitution: arbitrary permutation (26! ≈ 4 × 10²⁶ keys).

All fall to frequency analysis — substitution preserves the statistical signature of letters.

2. Polyalphabetic substitution

Several alternating tables. The same plaintext letter can be encrypted differently depending on its position:

• Vigenère (1586): 26 Caesar alphabets indexed by the letters of a repeated textual key.
• Beaufort: subtractive variant, self-inverse.
• Autokey: the key extends by concatenating the plaintext.
• Enigma (1923): 3-4 rotors stepping on every keypress.
• Porta: 13 alphabets, more regular structure than Vigenère.

Flatten the frequency signature. Crackable by Kasiski + index of coincidence as soon as there’s a period.

3. Polygraphic substitution

Substitute by groups of letters (digrams, trigrams…) rather than letter by letter. Preserves the signature at the n-gram level, hence harder to attack:

• Playfair (1854): digram substitution via a 5×5 grid derived from a keyword.
• Hill (1929): block substitution of N letters via matrix multiplication modulo 26. The first cipher where linear algebra really comes into play.
• Two-square, four-square: variants of Playfair on two or four grids.

More laborious to break by hand, but no match for a modern computer.

4. Homophonic substitution

A frequent plaintext letter (E for example) is replaced by several different ciphertext symbols, picked at random for each occurrence. Idea: flatten frequency by spreading E across five or six distinct symbols.

• Mary Queen of Scots cipher (16th century): nomenclator combining substitution and a table of code-named entities. Broken by Phelippes in 1586.
• Beale ciphers (19th century): famous American puzzle, partially solved.
• Zodiac Cipher 340 (1969): homophonic cipher cracked in 2020 by David Oranchak and Jarl Van Eycke.

More resistant than pure monoalphabetic, but still vulnerable to advanced statistical attacks (Markov chain models on bigrams).

Symbolic substitutions

The so-called symbolic ciphers (Pigpen, Templar, Dancing Men, Aurebesh) are usually monoalphabetic substitutions where the substituted symbol is a glyph instead of a letter. Cryptanalysis is unchanged — frequency analysis applied to the glyphs cracks them as fast as a lettered cipher. The glyph is just a visual costume; it serves to intrigue or to fit a fictional universe (Star Wars, Sherlock Holmes), not to add security.

Substitution versus transposition

	Substitution	Transposition
Action	Replaces letters	Reorders letters
Plaintext frequency	Modified (mono) or flattened (poly)	Strictly preserved
Index of coincidence	Varies	Same as plaintext
Anagram of plaintext?	No	Yes
Classical examples	Caesar, Vigenère, Playfair	Scytale, Rail Fence, Columnar

Both principles routinely combine: ADFGVX pairs substitution and transposition; Enigma stacks polyalphabetic substitutions; and AES alternates substitution (S-Box) and permutation/transposition (ShiftRows, MixColumns) on each round. That’s Shannon’s doctrine: “confusion + diffusion”. Substitution brings confusion (makes the relationship between key and ciphertext opaque); transposition brings diffusion (spreads the effect of one plaintext bit across the whole ciphertext).

Substitution in modern S-Boxes

The legacy of classical substitution lives on in modern block ciphers’ S-Boxes (substitution boxes). An S-Box is a small lookup table — typically 8 bits in, 8 bits out — that performs a non-linear substitution on a chunk of state. AES uses a single S-Box derived from the multiplicative inverse in GF(2⁸); DES uses eight different 6-bit-to-4-bit S-Boxes whose design choices were classified for two decades after release. The cryptographic strength of these designs hinges on the S-Box’s resistance to differential and linear cryptanalysis — the modern descendants of frequency analysis. So when you encrypt a file with AES, conceptually you’re applying a beefed-up monoalphabetic substitution sixteen times in a row at the byte level, with permutations between each round.

To dig further

• AES = 10 rounds of SubBytes (non-linear S-Box substitution) + ShiftRows (cyclic transposition) + MixColumns (linear mixing) + AddRoundKey. It’s polyalphabetic substitution at the byte level, on 128 bits.
• DES = combination of substitution (S-boxes) and permutation (P-box) over 16 Feistel rounds.

Key takeaways:

• Substitution = replace plaintext elements. Transposition = reorder them. The two fundamental classical encryption principles.
• Four sub-families: monoalphabetic, polyalphabetic, polygraphic, homophonic. Increasing security.
• Symbolic ciphers (Pigpen, Templar) are glyph-based monoalphabetic substitutions — no stronger than Caesar.
• AES and DES combine substitution + transposition each round (Shannon’s confusion + diffusion doctrine).