1
The key space must be large
A shift cipher has 26 keys and falls to exhaustive search in seconds. Large key space is necessary and far from sufficient.
Lesson · Number Theory and Cryptography · Cryptography
Classical Ciphers
Three ciphers built from modular arithmetic, each broken by a different attack. They are worth studying because the reasons they fail are the requirements a real cipher must meet.
shift E(x) = (x + k) mod 26 26 keys — brute force
affine E(x) = (ax + b) mod 26 needs gcd(a,26) = 1
Vigenère repeating key of shifts period found, then 26 shifts
one-time pad: key as long as the message, never reused — unbreakable
Three ciphers, three breaks
Core ideas
What this lesson establishes
Each cipher is modular arithmetic on letters. Each is broken, and the break teaches the design requirement.
2
Structure survives substitution
Any cipher mapping each letter to a fixed other letter preserves letter frequencies, and English frequencies are distinctive enough to break it.
3
Key reuse is the recurring fatal flaw
Vigenère falls because the key repeats. The one-time pad is provably secure precisely because it never does.
The material
Three ciphers
Construction, decryption and attack for each.
The shift cipher
Definition · Shift cipher
Encode letters as 0 … 25. Encryption is E(x) = (x + k) mod 26 and decryption is D(y) = (y − k) mod 26. Caesar's cipher is k = 3.
There are 25 useful keys, so an attacker tries them all and reads the output. This takes seconds by hand. The lesson is that a key space must be far too large to enumerate — modern ciphers use 2¹²⁸ keys or more.
The affine cipher
Definition · Affine cipher
E(x) = (ax + b) mod 26, with gcd(a, 26) = 1 so that a is invertible. Decryption is D(y) = a⁻¹(y − b) mod 26.
The coprimality condition is exactly “Bézout's Identity and Modular Inverses”'s: without it the map is not injective and decryption is impossible. Since 26 = 2 · 13, the valid multipliers are the twelve values coprime to 26, giving 12 · 26 = 312 keys.
Example · Encrypting and decrypting
a = 5, b = 8. The letter H is 7, so E(7) = 5·7 + 8 = 43 ≡ 17 = R. To decrypt, 5⁻¹ ≡ 21 (mod 26) since 5 · 21 = 105 = 4·26 + 1, so D(17) = 21(17 − 8) = 21 · 9 = 189 ≡ 7 = H. ✓
312 keys is still trivially searchable, and the cipher has a worse problem: it is a substitution, so letter frequencies survive. E is the commonest letter in English at about 12%, and whatever it maps to will be the commonest ciphertext letter. Two frequency matches determine a and b.
The Vigenère cipher
Definition · Vigenère cipher
A keyword gives a repeating sequence of shifts: the ith letter of the message is shifted by the (i mod L)th letter of the key, where L is the key length.
This defeats simple frequency analysis, because one plaintext letter encrypts to different ciphertext letters depending on its position. It was called le chiffre indéchiffrable for three centuries.
It falls in two stages. First find the key length: repeated plaintext fragments aligned with the same key position produce repeated ciphertext, and the distances between repetitions are multiples of L (Kasiski's method). Second, split the ciphertext into L columns, each of which is a single shift cipher, and break each by frequency.
The structural failure is key reuse. Once the period is known, a message of any length gives as much frequency data as needed.
The one-time pad
Theorem · Perfect secrecy
If the key is uniformly random, at least as long as the message, and never reused, then the ciphertext gives an attacker no information about the plaintext: every plaintext of that length is equally consistent with the observed ciphertext.
This is Shannon's theorem, and the one-time pad is genuinely unbreakable. It is also nearly unusable: the key is as long as the message and must be distributed securely in advance, which is the problem encryption was meant to solve.
Reusing a one-time pad destroys it completely. Two messages encrypted with the same key satisfy c₁ ⊕ c₂ = m₁ ⊕ m₂, from which both plaintexts can usually be recovered — the failure that broke the Soviet VENONA traffic.
“RSA Encryption”'s RSA answers the key-distribution problem instead: no shared secret is needed at all.
Interactive
Number theory workbench
Algorithms with their traces
Method
Encrypting and breaking
The requirement first, then the attack.
1
Check the key is valid
For an affine cipher gcd(a, 26) = 1, or the map is not invertible and decryption fails.
2
Encrypt letter by letter
Convert to 0 … 25, apply the map modulo 26, convert back.
3
To break a substitution, count letters
English frequencies are distinctive: E about 12%, T 9%, A 8%. Two matches determine an affine key.
4
To break Vigenère, find the period first
Repeated fragments give multiples of the key length. Then each column is a shift cipher.
Classical ciphers
Score 0 / 0Choose the answer you can justify.
Breaking an affine cipher
Ciphertext frequency analysis gives the two commonest letters.
Suppose the two commonest ciphertext letters are R (17) and I (8),
and the two commonest English letters are E (4) and T (19).
Guess E → R and T → I:
4a + b ≡ 17 (mod 26)
19a + b ≡ 8 (mod 26)
Subtract: 15a ≡ −9 ≡ 17 (mod 26)
gcd(15,26) = 1, and 15⁻¹ ≡ 7 (since 15·7 = 105 ≡ 1)
a ≡ 7 · 17 = 119 ≡ 119 − 4·26 = 15 (mod 26)
b ≡ 17 − 4·15 = 17 − 60 = −43 ≡ 9 (mod 26)
Key (a, b) = (15, 9). gcd(15,26) = 1, so it is valid.
Decrypt with a⁻¹ = 7: D(y) = 7(y − 9) mod 26
Two frequency guesses gave a linear system, which “Linear Congruences” solves. If the decryption is nonsense the next guess is E→R, T→ something else, and there are only a few to try. The cipher offers no resistance beyond that.
Common mistakes
1
Choosing an affine multiplier sharing a factor with 2613, 2 and any even value make the map non-injective. Decryption becomes impossible, not merely difficult.
2
Believing a large key space is sufficientThe affine cipher has 312 keys and would be broken by frequency analysis even with millions, because the structure survives.
3
Reusing a one-time padTwo messages under one key give m₁ ⊕ m₂, from which both are usually recoverable. The pad is secure only for a single use.
Check your understanding
✓
Finish when you can break an affine cipher from two frequencies.
Given that the two commonest ciphertext letters are K and D, solve for a and b assuming they correspond to E and T. The system is two linear congruences, which “Linear Congruences” handles; the key comes out as (3, 24), and the lab will confirm E → K and T → D.
Note: Every cipher here shares one weakness that “RSA Encryption” removes: both parties need the key in advance. Public-key cryptography changed that, and it is the single most consequential idea in the subject.