Substitution, transposition and frequency analysis

Classical ciphers move symbols or replace them

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.

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.

Caesar has only 26 possible shifts

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.

Try it — worked example

Caesar cipher with shift n = 3: what do a, b and c encrypt to?

Show answer and steps

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

1. $n = 3$. Each letter’s numeric value moves up by 3, modulo 26.
2. $a$ is $0$: $(0+3) \bmod 26 = 3$, which is $d$.
3. $b$ is $1$: $(1+3) \bmod 26 = 4$, which is $e$.
4. $c$ is $2$: $(2+3) \bmod 26 = 5$, which is $f$.
5. 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.

Caesar’s key is a number from 0 to 25: a keyspace of 26, including the shift of 0 that leaves plaintext unchanged. Brute-forcing all 26 takes seconds.

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.

A fixed substitution preserves letter frequencies

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.

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.

Rail fence changes positions without changing letters

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.

Try it — worked example

Encrypt MEET ME AFTER THE TOGA PARTY with a rail fence cipher of depth 2.

Show answer and steps

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

1. Remove spaces: MEETMEAFTERTHETOGAPARTY, 23 letters.
2. Assign alternating positions to two rails: rail 1 takes positions 1, 3, 5, …; rail 2 takes positions 2, 4, 6, …

3. 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

4. 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.

Classical cipher workbench

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

CipherCaesarVigenereRail fence

ModeEncryptDecrypt

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.