Substitution Techniques

1. Substitution = Replace Letters, Keep Order

A substitution cipher replaces each plaintext symbol by another symbol; positions never move. General monoalphabetic map over 26 letters:

C = E(P), \quad \text{e.g. } f: A \to D, B \to E, \dots

Key space $26! \approx 4 \times 10^{26}$ — brute force impossible, yet every monoalphabetic cipher falls to statistics (Section 3). Contrast with transposition (Topic 8: move letters, keep identity).

2. The Classical Family

Cipher	Rule ( $p$ = 0–25)	Key space	Worked example
Caesar	$C = (p + k) \bmod 26$ , decrypt $(c - k)$	25	$k = 3$ : HELLO → KHOOR
Monoalphabetic	Arbitrary permutation	$26! \approx 2^{88}$	Plain: ABC... / Cipher: DKV... — HELLO → "ULSSI"-style
Playfair ( $5 \times 5$ )	Digraph rules (same row → right, same col → down, rectangle → swap)	$25!$	MONARCHY square: HI → BM; decrypt reverses
Hill ( $m \times m$ matrix $K$ )	$\mathbf{c} = K\mathbf{p} \bmod 26$ ; need $\det K$ invertible mod 26 ( $\gcd(\det,26) = 1$ )	large	$K = [[3,3],[2,5]]$ , "HI" $= (7,8)$ : $\mathbf{c} = (45, 54) \bmod 26 = (19, 2)$ → "TC"
Polyalphabetic (Vigenère)	$C_i = (p_i + k_{i \bmod m}) \bmod 26$	$26^m$	Key LEMON over ATTACKATDICK → LXFOPVEFRNHR
Autokey	Key extends with plaintext itself	—	Key QUEEN + plaintext MEET... → cipher varies after key runs out
Vernam / One-Time Pad	$C_i = p_i \oplus k_i$ , key random, length = message, never reused	$2^n$	Only unconditionally secure cipher (Shannon)

Vigenère table check: A(0)+L(11) = L(11) ✓; T(19)+E(4) = X(23) ✓ — first two letters "AT" → "LX".

3. Breaking Monoalphabetic Ciphers — Frequency Analysis

English letter frequencies ( $\approx$ E 12.7%, T 9.1%, A 8.2%, O 7.5%, ...) transfer to ciphertext 1-to-1. Attack:

Count ciphertext frequencies; guess most frequent = E, next = T/A/O.
Use digrams (TH, HE most common) and trigrams (THE, AND) to confirm.
Words: single-letter words are A/I; "TH-T" pattern is THAT.

Worked mini-break: $C =$ "WKH TXHHQ RI WKH...": each letter is Caesar $+3$ (W→T? no — frequency says H most common → H = E means shift 3): subtract 3 → "THE QUEEN OF THE..." ✓. Monoalphabetic with $26!$ keys broke by hand — key size ≠ security.

Kasiski test (Vigenère): repeated blocks ("VTW" twice, distance 9) reveal key length $m \mid$ distances; then each of the $m$ Caesar columns falls to frequency analysis separately.

4. Why Polyalphabetic Matters and OTP Is Perfect

Monoalphabetic: one $P$ letter → one $C$ letter — statistics survive.
Polyalphabetic: one $P$ letter → many $C$ letters (flattens frequencies); key length $m$ is the security knob — $m = 1$ is Caesar, $m \to$ message length with random key is OTP.
OTP: $C = P \oplus K$ with $|K| = |P|$ , $K$ truly random, used once → $C$ is uniform random regardless of $P$ → zero leakage (unconditional security). Two-time pad ( $K$ reused) breaks instantly: $C_1 \oplus C_2 = P_1 \oplus P_2$ .

Exam Points

Formulas $C = (p+k) \bmod 26$ , Vigenère $C_i = (p_i+k_{i \bmod m})$ , Hill $\mathbf{c} = K\mathbf{p}$ — 2-mark each.
Caesar "HELLO → KHOOR" and Vigenère "ATTACK/LEMON → LXFOPVEFRNHR" — standard numericals.
Frequency-analysis steps + Kasiski key-length trick — 5-mark theory core.
OTP three conditions (random, full-length, once) + two-time-pad break.

Substitution Techniques