Substitution, transposition and frequency analysis

Transposition and substitution as the two primitives behind classical ciphers, the Caesar cipher and its tiny keyspace, why frequency analysis breaks it, and the rail-fence cipher worked letter by letter.

Distinguish transposition from substitution as the two primitives behind classical ciphers.
Compute the Caesar cipher's keyspace and explain why it is trivially small.
Explain why frequency analysis breaks a monoalphabetic substitution cipher.
Encrypt a message by hand with the rail-fence transposition cipher.

14 min read

Intuition

Before computers, hiding a message meant one of two moves: move the letters around, or replace them. Transposition and substitution are the two primitives underneath every classical cipher, usually governed by a key so only someone holding it can reverse the disguise. They are often combined in the same cipher, but each is worth understanding on its own first.

Mechanism

Transposition shifts the positions of symbols in a message according to a rule, without changing the symbols themselves. Substitution replaces symbols with other symbols according to a rule, without changing their positions. Both are usually parameterised by a key, so that only someone with the key can correctly reverse the process.

Mechanism

The Caesar cipher is the simplest substitution cipher: every letter of the plaintext is shifted by the same fixed amount $n$ through the alphabet. It is a special case of monoalphabetic substitution: one where the substitution rule happens to be “shift by $n$ ,” rather than an arbitrary relabelling of all 26 letters.

Formula

Caesar cipher

C_i = (P_i + n) \bmod 26, \qquad P_i = (C_i - n) \bmod 26

$P_i, C_i$: the numeric value (A=0 .. Z=25) of the i-th plaintext and ciphertext letter
$n$: the shift, a fixed integer from 0 to 25

Every letter uses the same n: the whole message shares one substitution rule.

Worked example

AnswerShift n=3: a -> d, b -> e, c -> f

$n = 3$ . Each letter’s numeric value moves up by 3, modulo 26.
$a$ is $0$ : $(0+3) \bmod 26 = 3$ , which is $d$ .
$b$ is $1$ : $(1+3) \bmod 26 = 4$ , which is $e$ .
$c$ is $2$ : $(2+3) \bmod 26 = 5$ , which is $f$ .
The same rule continues through the whole alphabet, wrapping at the end: $\ldots, w \to z, x \to a, y \to b, z \to c$ .

The lecture gives exactly this mapping for $n=3$ ; it is the same shift-by- $n$ rule applied to every letter of a message, not just the first three.

Mechanism

Because Caesar only ever shifts, the key is a single number from 0 to 25, a keyspace of 26, one of which (a shift of 0) leaves the plaintext unchanged. Trying all 26 shifts by hand or by computer takes seconds. This is why the lecture’s own security judgement on the Caesar cipher is blunt: brute-forcing it takes only a few seconds on a modern computer.

Pitfall

Do not extend that 26-key figure to substitution ciphers in general. It belongs to Caesar specifically, because Caesar restricts itself to shifts. A general monoalphabetic substitution can map each of the 26 letters to any other letter, with no shift restriction at all: a keyspace of $26!$ , not 26. Caesar is the tiny, shift-only special case of that much larger family, which is exactly why it is so much weaker than substitution in general.

Threat

Frequency analysis breaks a monoalphabetic substitution cipher, Caesar included, because the cipher applies one fixed mapping to the entire message. English has a well-known letter-frequency profile: E is the most common letter, and that shape survives substitution unchanged, just relabelled onto different symbols. An attacker identifies the most frequent symbol in the ciphertext, guesses it stands for E, and works outward from there, often helped by a dictionary lookup to confirm guesses.

Control

The fix is to stop using one fixed substitution rule for the whole message. A polyalphabetic cipher applies a different substitution depending on position, so the same plaintext letter can land on different ciphertext letters at different points in the message, exactly the direction the next topic, the Vigenère cipher, takes.

Mechanism

Transposition ciphers rearrange letters instead of replacing them. The rail fence cipher writes the plaintext in a zigzag across a fixed number of rows (“rails”), then reads the result off one rail at a time. With 2 rails the zigzag collapses to strictly alternating rows: no diagonal is needed to see the pattern.

Worked example

AnswerMEET ME AFTER THE TOGA PARTY, depth 2 -> MEMATRHTGPRYETEFETEOAAT

Remove spaces: MEETMEAFTERTHETOGAPARTY, 23 letters.
Assign alternating positions to two rails: rail 1 takes positions 1, 3, 5, …; rail 2 takes positions 2, 4, 6, …
Rail 1 (odd positions): M E M A T R H T G P R Y
Rail 2 (even positions): E T E F E T E O A A T
Read rail 1 in full, then rail 2, and concatenate: MEMATRHTGPRY + ETEFETEOAAT.

Result: MEMATRHTGPRYETEFETEOAAT, matching the lecture’s own worked example exactly.

Exam detail

Rail fence and Caesar are the same two primitives from opposite ends: Caesar substitutes without moving any letter’s position, rail fence moves every letter’s position without substituting a single one. Real ciphers, as the lecture notes, commonly combine both in the same design.

Encrypt or decrypt with Caesar, Vigenere or rail fence, then read the ciphertext's letter frequencies and Kasiski trigram gaps.

Cipher

Mode

Shift

Text

Result

Letter frequency of the current ciphertext (bars) vs English (dashed line)

Kasiski minimum sequence length

Kasiski examination

Sequence	Positions	Gaps

Recall

Why is a rail-fence cipher's keyspace also too small to matter for security?

With the rail count as its only parameter, the keyspace is just the small set of practical rail counts, nowhere near large enough to resist an attacker who tries each one and checks whether the result reads as language. Like Caesar, its weakness is not in the size of the keyspace.

Source

Week 4 notes PDF