28-02 — Classical Ciphers

Phase: Cryptography | Subject: 28-02 Prerequisites: 28-01-modular-arithmetic-review.md Next subject: 28-03-symmetric-encryption.md

Learning Objectives

By the end of this subject, you will be able to:

1. Encrypt and decrypt using Caesar, Vigenère, and substitution ciphers
2. Perform frequency analysis to break simple substitution ciphers
3. Compute the Index of Coincidence and use it to determine key length
4. Explain the weaknesses of classical ciphers and the lessons for modern crypto
5. Describe the Enigma machine's operation and the mathematical basis of its flaws

Core Content

The Caesar Cipher

The simplest substitution cipher, shifting each letter by a fixed amount $k$:

$$E_k(x) = (x + k) \bmod 26$$ $$D_k(y) = (y - k) \bmod 26$$

where letters are mapped to numbers: A=0, B=1, ..., Z=25.

Example ($k = 3$): "HELLO" → "KHOOR".

Weakness: Only 25 possible keys. Trivial to brute force. A single known plaintext letter breaks it.

Substitution Ciphers

A monoalphabetic substitution cipher uses an arbitrary permutation of the 26 letters as the key. The key space is $26! \approx 4 \times 10^{26}$ — far too large to brute force.

But it's trivially broken by frequency analysis.

Letter frequencies in English:

The most frequent ciphertext letter likely maps to 'E'. Common digrams: TH, HE, IN, ER, AN. Common trigrams: THE, AND, ING.

Breaking method: 1. Count letter frequencies in ciphertext 2. Match most frequent to 'E', next to 'T', etc. 3. Look for common words (THE, AND, THAT) 4. Iterate and refine

⚠️ CRITICAL: Frequency analysis becomes harder with shorter ciphertexts. At ~200+ characters, English letter frequencies become statistically reliable.

The Vigenère Cipher

A polyalphabetic cipher: uses a keyword to determine a different shift for each letter.

Encryption: $c_i = (p_i + k_{i \bmod m}) \bmod 26$, where $m$ is the keyword length.

Example: Key = "KEY" (K=10, E=4, Y=24). Plaintext "ATTACK": - A(0) + K(10) = 10 = K - T(19) + E(4) = 23 = X - T(19) + Y(24) = 17 = R - A(0) + K(10) = 10 = K - C(2) + E(4) = 6 = G - K(10) + Y(24) = 8 = I Result: "KXRKGI"

The Vigenère cipher was considered "unbreakable" for 300 years — but it's not.

Breaking the Vigenère Cipher

Step 1: Find the key length using the Index of Coincidence (IC).

The IC for a text is the probability that two randomly chosen letters are the same:

$$\text{IC} = \frac{\sum_{i=0}^{25} f_i(f_i - 1)}{N(N-1)}$$

where $f_i$ is the frequency of letter $i$ and $N$ is total length.

• Random text: IC ≈ 0.038 (= 1/26)
• English text: IC ≈ 0.065
• Vigenère with key length $m$: split into $m$ columns, each should have IC ≈ 0.065

Step 2: For each column (monoalphabetic), use frequency analysis to find the shift.

Alternatively, use the Kasiski examination: look for repeated trigrams. The distance between repeats is likely a multiple of the key length.

The One-Time Pad

The Vigenère with a truly random key as long as the message, used only once:

$$c_i = (p_i + k_i) \bmod 26$$

Claude Shannon proved this is perfectly secure (information-theoretic security) — the ciphertext reveals NO information about the plaintext. But it requires: 1. Key as long as the message 2. Truly random key 3. Key never reused 4. Key securely shared

These practical limitations prevented widespread use.

The Enigma Machine

A WWII electromechanical cipher device. Mathematically, it implemented a polyalphabetic substitution with: - Plugboard (Steckerbrett): swapped pairs of letters (involution) - Rotors: 3-5 rotors, each a fixed permutation, advancing like an odometer - Reflector: sent the signal back through the rotors, making encryption = decryption

Key space: $3! \times 26^3 \times \binom{26}{2,2,\ldots} \approx 1.07 \times 10^{23}$ (with 10 plugboard pairs).

Critical design flaw: No letter ever encrypted to itself. This, combined with predictable message formats (cillies, weather reports), enabled Alan Turing and the Bletchley Park team to break it.

Mathematical lessons from Enigma: - An involution (encryption = decryption) reduces security - Known-plaintext attacks are powerful - Protocol mistakes are as dangerous as mathematical weaknesses

Key Terms

• Caesar Cipher — fixed shift cipher, keyspace of 25
• Monoalphabetic Substitution — arbitrary permutation of alphabet
• Frequency Analysis — exploiting letter frequency patterns
• Polyalphabetic Cipher — uses multiple different shifts
• Vigenère Cipher — key-word-driven polyalphabetic cipher
• Index of Coincidence (IC) — statistical measure for key length detection
• Kasiski Examination — finding key length from repeated patterns
• One-Time Pad — theoretically perfect, practically difficult
• Enigma — WWII rotor-based cipher machine
• Known-Plaintext Attack — attacker knows some plaintext-ciphertext pairs

Worked Examples

Example 1: Frequency Analysis

Given the ciphertext "WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ" (Caesar with unknown shift), find the plaintext.

Solution:

Count: W=2, K=2, H=2, R=3... Most frequent ciphertext letters are roughly evenly distributed. But the word structure suggests short words. "WKH" appears twice — likely "THE". If W→T, K→H, H→E, the shift is W(22) → T(19): $22 + k \equiv 19 \pmod{26} \Rightarrow k \equiv -3 \equiv 23 \pmod{26}$, or equivalently forward shift of 3.

Check: T(19) + 3 = 22 = W? Wait — Caesar encrypts by adding $k$. If W encrypts to T is impossible with addition. Let me check: decrypt by subtracting $k$. If W(22) decrypts to T(19), then $22 - k \equiv 19 \Rightarrow k = 3$. So shift is 3.

Decrypt: subtract 3 from each. "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG". ✓

Example 2: Vigenère Encryption and IC

Encrypt "TO BE OR NOT TO BE" with key "HAMLET". Then compute the IC.

Solution:

H=7, A=0, M=12, L=11, E=4, T=19.

T(19)+H(7)=26→0=A, O(14)+A(0)=14=O, space skip, B(1)+M(12)=13=N, E(4)+L(11)=15=P, (space), O(14)+E(4)=18=S, R(17)+T(19)=36→10=K, (space), N(13)+H(7)=20=U, O(14)+A(0)=14=O, T(19)+M(12)=31→5=F, (space), T(19)+L(11)=30→4=E, O(14)+E(4)=18=S, (space), B(1)+T(19)=20=U, E(4)+H(7)=11=L.

Ciphertext: "AONP SK UOFES UL" (without spaces: "AONPSKUOFESUL").

IC (without spaces, 12 chars): $f_A=1, f_O=2, f_N=1, f_P=1, f_S=2, f_K=1, f_U=2, f_F=1, f_E=1, f_L=1$.

IC = $[1(0) + 2(1) + 1(0) + 1(0) + 2(1) + 1(0) + 2(1) + 1(0) + 1(0) + 1(0)] / (12 \cdot 11) = [2+2+2] / 132 = 6/132 \approx 0.045$.

With more text, each column would approach 0.065, confirming key length of 6.

Example 3: Breaking Vigenère with Kasiski

Ciphertext: "...RSAVF BKRSA VFBKRS AVFBKR..." (ellipsis for surrounding text). Identify the likely key length.

Solution:

"RSA" appears at positions 1, 7, 14, 21. Distances: 6, 7, 7. Common factor? All divisible by 1, but key length is likely 7 (since 7 repeats, and 6 could be from the wrap at the end). Also "FBK" appears at positions 5, 13, 20. Distances: 8, 7. Mixed. The strongest signal is 7.

Try key length 7: split into 7 columns, compute IC per column. If each column's IC ≈ 0.065, key length is confirmed.

Quiz

Q1: What does the concept of Kasiski examination primarily refer to in this subject?

A) A historical anecdote about Kasiski examination B) A computational error related to Kasiski examination C) A visual representation of Kasiski examination D) The definition and application of Kasiski examination

Correct: D)

• If you chose A: This is incorrect. Kasiski examination is defined as: the definition and application of kasiski examination. The other options describe different aspects that are not the primary focus.
• If you chose B: This is incorrect. Kasiski examination is defined as: the definition and application of kasiski examination. The other options describe different aspects that are not the primary focus.
• If you chose C: This is incorrect. Kasiski examination is defined as: the definition and application of kasiski examination. The other options describe different aspects that are not the primary focus.
• If you chose D: Kasiski examination is defined as: the definition and application of kasiski examination. The other options describe different aspects that are not the primary focus. Correct!

Q2: Which of the following is the key formula discussed in this subject?

A) E_k(x) = (x + k) \bmod 26 B) An unrelated formula from a different topic C) The inverse operation of the formula in question D) A simplified version of E_k(x) = (x + k) \bmod 26...

Correct: A)

• If you chose A: The formula E_k(x) = (x + k) \bmod 26 is central to this subject. The other options are either simplified versions or unrelated. Correct!
• If you chose B: This is incorrect. The formula E_k(x) = (x + k) \bmod 26 is central to this subject. The other options are either simplified versions or unrelated.
• If you chose C: This is incorrect. The formula E_k(x) = (x + k) \bmod 26 is central to this subject. The other options are either simplified versions or unrelated.
• If you chose D: This is incorrect. The formula E_k(x) = (x + k) \bmod 26 is central to this subject. The other options are either simplified versions or unrelated.

Q3: What is the primary purpose of Caesar Cipher?

A) It is used only in advanced research contexts B) It is primarily a historical notation system C) It replaces all other methods in this domain D) It is used to caesar cipher in mathematical analysis

Correct: D)

• If you chose A: This is incorrect. Caesar Cipher serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose B: This is incorrect. Caesar Cipher serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose C: This is incorrect. Caesar Cipher serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose D: Caesar Cipher serves the purpose described in the correct answer. The other options misrepresent its role. Correct!

Q4: Which statement about Monoalphabetic Substitution is TRUE?

A) Monoalphabetic Substitution is mentioned only as a historical footnote B) Monoalphabetic Substitution is an advanced topic beyond this subject's scope C) Monoalphabetic Substitution is a fundamental concept covered in this subject D) Monoalphabetic Substitution is not related to this subject

Correct: C)

• If you chose A: This is incorrect. Monoalphabetic Substitution is a fundamental concept covered in this subject. This subject covers Monoalphabetic Substitution as part of its core content.
• If you chose B: This is incorrect. Monoalphabetic Substitution is a fundamental concept covered in this subject. This subject covers Monoalphabetic Substitution as part of its core content.
• If you chose C: Monoalphabetic Substitution is a fundamental concept covered in this subject. This subject covers Monoalphabetic Substitution as part of its core content. Correct!
• If you chose D: This is incorrect. Monoalphabetic Substitution is a fundamental concept covered in this subject. This subject covers Monoalphabetic Substitution as part of its core content.

Q5: Based on the worked examples in this subject, what is the correct result?

A) A different result from a common mistake B) An unrelated numerical value C) The inverse of the correct answer D) "KXRKGI"

Correct: D)

• If you chose A: This is incorrect. The worked examples show that the result is "KXRKGI". The other options represent common errors.
• If you chose B: This is incorrect. The worked examples show that the result is "KXRKGI". The other options represent common errors.
• If you chose C: This is incorrect. The worked examples show that the result is "KXRKGI". The other options represent common errors.
• If you chose D: The worked examples show that the result is "KXRKGI". The other options represent common errors. Correct!

Q6: How are Monoalphabetic Substitution and Frequency Analysis related?

A) Monoalphabetic Substitution and Frequency Analysis are completely unrelated topics B) Monoalphabetic Substitution and Frequency Analysis are closely related concepts C) Monoalphabetic Substitution is a special case of Frequency Analysis D) Monoalphabetic Substitution is the inverse of Frequency Analysis

Correct: B)

• If you chose A: This is incorrect. Both Monoalphabetic Substitution and Frequency Analysis are covered in this subject as interconnected topics.
• If you chose B: Both Monoalphabetic Substitution and Frequency Analysis are covered in this subject as interconnected topics. Correct!
• If you chose C: This is incorrect. Both Monoalphabetic Substitution and Frequency Analysis are covered in this subject as interconnected topics.
• If you chose D: This is incorrect. Both Monoalphabetic Substitution and Frequency Analysis are covered in this subject as interconnected topics.

Q7: What is a common pitfall when working with Polyalphabetic Cipher?

A) Polyalphabetic Cipher has no common misconceptions B) The main error with Polyalphabetic Cipher is using it when it is not needed C) A common mistake is confusing Polyalphabetic Cipher with a similar concept D) Polyalphabetic Cipher is always computed the same way in all contexts

Correct: C)

• If you chose A: This is incorrect. Students often confuse Polyalphabetic Cipher with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose B: This is incorrect. Students often confuse Polyalphabetic Cipher with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose C: Students often confuse Polyalphabetic Cipher with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!
• If you chose D: This is incorrect. Students often confuse Polyalphabetic Cipher with similar-sounding or related concepts. Pay attention to the precise definitions.

Q8: When should you apply Index of Coincidence (IC)?

A) Apply Index of Coincidence (IC) to solve problems in this subject's domain B) Index of Coincidence (IC) is not practically useful C) Use Index of Coincidence (IC) only in pure mathematics contexts D) Avoid Index of Coincidence (IC) unless explicitly instructed

Correct: A)

• If you chose A: Index of Coincidence (IC) is a practical tool used throughout this subject to solve relevant problems. Correct!
• If you chose B: This is incorrect. Index of Coincidence (IC) is a practical tool used throughout this subject to solve relevant problems.
• If you chose C: This is incorrect. Index of Coincidence (IC) is a practical tool used throughout this subject to solve relevant problems.
• If you chose D: This is incorrect. Index of Coincidence (IC) is a practical tool used throughout this subject to solve relevant problems.

Practice Problems

1. Decrypt "EBIIL" assuming a Caesar cipher with unknown key.
   

   Click for answer

   Try shifts. With key=3 (subtract 3): E(4)→B(1), B(1)→Y(24), I(8)→F(5), I→F, L(11)→I(8): "BYFFI" — not English. Try key=23 (add 3): E→H, B→E, I→L, I→L, L→O: "HELLO". ✓

2. If English text has IC ≈ 0.065, what would you expect the IC of a Vigenère ciphertext to be if the keyword is "SECRET" (length 6)?
   

   Click for answer

   The overall IC would be a mix of the columns. Overall IC ≈ 0.038 + (0.065-0.038)/6 ≈ 0.0425 (rough approximation). Each column individually would be ~0.065 if the text is long enough.

3. Compute the Vigenère encryption of "MATH" with key "PI".
   

   Click for answer

   P=15, I=8. M(12)+15=27→1=B, A(0)+8=8=I, T(19)+15=34→8=I, H(7)+8=15=P. Ciphertext: "BIIP".

4. Why is the Caesar cipher not a substitution cipher in the sense of having $26!$ keys?
   

   Click for answer

   A Caesar cipher only uses shifts of the alphabet — just 25 possible permutations, not all $26!$. It's a subset of substitution ciphers (specifically, a shift cipher).

5. Why can't you reuse a one-time pad key?
   

   Click for answer

   If the same key $k$ encrypts two messages: $c_1 = p_1 \oplus k$, $c_2 = p_2 \oplus k$. Then $c_1 \oplus c_2 = p_1 \oplus p_2$. The key cancels out. An attacker gets the XOR of two plaintexts, which leaks significant information.

Summary

Key takeaways:

• Caesar: trivial 25-key brute force; substitution: $26!$ keys but broken by frequency analysis
• Vigenère resists simple frequency analysis but falls to Kasiski + Index of Coincidence
• One-time pad is theoretically perfect but practically constrained
• Enigma's mathematical structure (involution) and operational patterns enabled its breaking
• Classical ciphers teach foundational principles for modern cryptanalysis

Pitfalls

• Assuming Vigenère is unbreakable. The Vigenère cipher was called "le chiffre indéchiffrable" for centuries, but it falls to Kasiski examination and the Index of Coincidence. A polyalphabetic cipher is not a one-time pad — the repeating key introduces exploitable structure.
• Confusing the overall IC with the per-column IC. When testing key length hypotheses, you must split the ciphertext into columns and compute the IC for each column separately. The IC of the full (mixed) ciphertext is close to random (~0.038) and tells you nothing about the correct key length.
• Applying the shift in the wrong direction. Caesar encryption adds the key: $E_k(x) = (x + k) \bmod 26$. Decryption subtracts: $D_k(y) = (y - k) \bmod 26$. A frequent mistake is adding the key for decryption or subtracting for encryption.
• Thinking a large keyspace guarantees security. Monoalphabetic substitution has $26! \approx 4 \times 10^{26}$ possible keys, but frequency analysis breaks it in seconds with enough ciphertext. Large keyspace $\neq$ security — the cipher must resist cryptanalysis, not just brute force.
• Treating the one-time pad as a stream cipher with a reusable key. The one-time pad's perfect secrecy proof relies on the key being truly random, as long as the message, and NEVER reused. Reusing a one-time pad key is catastrophic: $c_1 \oplus c_2 = p_1 \oplus p_2$.

Next Steps

Next up: 28-03-symmetric-encryption.md — modern symmetric ciphers like DES and AES.