03 — Classical Cryptography

Ciphers from Antiquity to 1949 (Shannon's paper). Substitution, transposition, polyalphabetic, electromechanical machines. Every cipher in this section is broken; presented to understand the evolution and the attacks.

1. Steganography (not cryptography, but related)

Hiding the existence of the message, not its content. Historical:

2. Monoalphabetic substitution ciphers

Each letter mapped to another letter fixedly.

Atbash (Hebrew, ~600 BC)

\(A \to Z, B \to Y, C \to X, \dots\) Reverse substitution. Appears in the Tanakh (Jeremiah).

Caesar cipher (~50 BC)

Fixed shift \(k\) (classic \(k=3\)):

ROT13 (\(k=13\)) is a special case — its own inverse, used on Usenet for spoilers.

Break: 25 possibilities; brute force is trivial.

Generic monoalphabetic substitution

Arbitrary map \(\pi: \mathcal{A} \to \mathcal{A}\). Key space \(26! \approx 4 \times 10^{26}\) — seems large.

Break: frequency analysis (al-Kindi, ~850). Letter frequency in typical text:

Doubled letters (LL, SS, EE), n-grams (TH, HE, IN in English; QUE, NTE, COM in pt-BR), short-word patterns (THE, AND, OF; QUE, COM, DE) — destroy any monoalphabetic cipher in minutes.

Nomenclator ciphers (15th–18th c.)

Substitution + a list of homophones (several substitutions for frequent letters) + codes for frequent words (cities, names, verbs). Harder than pure monoalphabetic but still breakable with enough text.

Grand Chiffre of Louis XIV (Antoine + Bonaventure Rossignol, ~1670): a nomenclator with 587 entries, ~codes for syllables. Remained unbroken until Étienne Bazeries in 1893. Famous for unraveling the identity of the Man in the Iron Mask.

3. Polyalphabetic substitution ciphers

Uses several alphabets cyclically. Reduces statistical patterns.

Alberti cipher (1466)

Rotating disk with a scrambled inner alphabet. Rotation every N letters (controlled by uppercase indicator letters). The first polyalphabetic cipher of the West.

Vigenère cipher (Bellaso 1553, misattributed to Vigenère 1586)

Key \(K = k_1 k_2 \dots k_m\) repeated cyclically.

Decipher with the tabula recta (Trithemius's 26×26 table).

Break:

1. Kasiski test (Friedrich Kasiski 1863; Babbage independently in 1854): repetitions in the ciphertext at distances that are multiples of \(m\) indicate the key length.
2. Index of coincidence (William Friedman 1922): \(\text{IC} \approx 0.067\) for monoalphabetic English, \(\approx 0.038\) for uniformly random text; used to estimate \(m\).
3. Knowing \(m\), split the ciphertext into \(m\) monoalphabetic "streams", attack each one by frequency.

Autokey (Vigenère 1586, original)

The key is the keyword itself followed by the plaintext: \(K = k_1 k_2 \dots k_m p_1 p_2 p_3 \dots\). Stronger than pure Vigenère but still breakable.

Beaufort (Francis Beaufort, ~1857)

\(c_i = (k_i - p_i) \mod 26\) — its own inverse. Used in 19th-century commerce.

Running-key cipher

Key = a passage from a chosen book. No cyclic repetition. Stronger but still attackable because the key is natural text (not random) — the attacker exploits the statistics of two overlapping languages.

4. One-Time Pad (OTP)

Concept: Frank Miller (1882) proposes it; Gilbert Vernam patents it in 1917 (US 1,310,719) using punched paper tape with XOR; Joseph Mauborgne insists on a single-use random key.

with \(|K| = |P|\), \(K\) uniformly random, used only once.

Shannon's proof (1949)

The OTP has perfect secrecy: for all \(P, P', C\):

The ciphertext gives no information about the plaintext beyond its length.

Practical limitations (devastating)

• Key the size of the message.
• Key distribution: needs a secure channel with bandwidth equal to the traffic.
• Reuse is catastrophic (two-time pad).
• Generating true randomness at scale is hard.

Two-time pad attack

If \(C_1 = P_1 \oplus K\) and \(C_2 = P_2 \oplus K\), then:

And \(P_1 \oplus P_2\) has the statistics of natural text, decipherable by hand with crib-dragging.

Real-world use

• Venona (1943–1980): NSA/GCHQ operation that deciphered ~3000 KGB messages encrypted with OTP, because the Soviets reused pads due to a logistical bind in 1942–1945.
• The Washington-Moscow hotline since 1963 uses OTP.
• Modern espionage: numbers stations (number stations on shortwave radio) still transmit OTP-encrypted messages.

5. Transposition ciphers

Rearrange letters without substituting.

Spartan scytale (~500 BC)

Strip wound around a rod of fixed diameter \(d\). Message written along the axis; once unwound, the letters are scrambled. An attacker with a rod of the same diameter reconstructs it.

Rail fence (zigzag)

Writes in a zigzag of \(n\) rows, reads row by row.

plaintext: HELLO WORLD
n=3:
H . . . O . . . R . .
. E . L . W . O . L .
. . L . . . . . . . D
ciphertext: HOR ELWOL LD

Columnar transposition

Writes in an \(r \times c\) matrix, reads columns in the order given by a keyword.

Single columnar: breakable by anagramming. Double columnar: applied twice with distinct keys; used as ADFGVX (Germany WWI).

ADFGVX (1918)

German WWI cipher, authored by Fritz Nebel. Combines substitution (5×5 Polybius) + double columnar transposition. Uses only the letters A, D, F, G, V, X (chosen because their Morse is distinctive).

Break: Georges Painvin (French cryptanalyst) in Jun 1918. Considered one of the greatest cryptanalytic achievements of WWI.

6. Bigram and polygram ciphers

Playfair (Wheatstone 1854)

Cipher by bigrams. A 5×5 square derived from a keyword (I=J).

Rules for enciphering a bigram \((a, b)\):

1. If on the same row: each letter → letter to the right.
2. If in the same column: each letter → letter below.
3. General case: the letters form a rectangle diagonal; they swap to the corners on the same row.

Identical bigrams (LL) separated by X.

Use: the British in the 2nd Boer War, WWI tactical, WWII coastal. Considered unbreakable for decades; breakable with ~600 letters of ciphertext via bigram frequency analysis.

Hill cipher (Lester Hill 1929)

The first algebraic cipher. Plaintext in blocks of \(n\) letters, a vector \(\mathbf{p} \in \mathbb{Z}_{26}^n\). Key an invertible matrix \(K \in \mathbb{Z}_{26}^{n \times n}\).

Decryption with \(K^{-1} \mod 26\).

Vulnerability: linearity. Knowing \(n\) linearly independent pairs \((\mathbf{p}, \mathbf{c})\), one solves for \(K\).

Historically important: it inspires modern linear S-boxes (which must be broken with non-linearity — hence AES MixColumns + S-box).

7. Electromechanical machines (1918–1945)

Enigma (Scherbius 1918; military 1926–1945)

Components:

• 3 (later 4) rotors chosen from a set of 5 (M3) or 8 (M4 naval). Each rotor implements a fixed permutation of 26 letters.
• Plugboard (Steckerbrett): 10 cables form an additional fixed, symmetric permutation.
• Reflector: fixed symmetric permutation at the end.
• Ring settings (Ringstellung): offset between rotor and indicator.
• Rotor stepping: with each keystroke, the fast rotor advances; the middle rotor advances every 26 of the fast one (with the "double-stepping" quirk).

Signal: key → plugboard → rotor 1 → 2 → 3 → reflector → 3 → 2 → 1 → plugboard → lamp.

Critical mathematical property: because of the reflector, encrypt = decrypt (an involution), but no letter ever enciphers to itself — exploited by Bletchley.

Theoretical key space: ~\(1.59 \times 10^{20}\) (rotors chosen × ring × Stecker × initial position).

Breaks:

1. Marian Rejewski + Jerzy Różycki + Henryk Zygalski (Biuro Szyfrów, Poland, 1932–1939): exploit the indicator system (double encipherment of the message key). Rejewski derives the rotor wiring using permutation theory (a theorem on the number of cycles in conjugate permutations). They build the Bomba kryptologiczna (a replica of 6 Enigmas in parallel).
2. Bletchley Park (1939–1945): Turing redesigns the Bombe to exploit cribs (probable plaintext-ciphertext pairs, like "wetterbericht" in Luftwaffe messages at 6 in the morning). Gordon Welchman adds the diagonal board. Hundreds of Bombes. Banbury sheets, Hut 6, Hut 8 (naval). Bletchley employed ~10,000 people at its peak.
3. Capture operations: U-110 (May 1941) — the Royal Navy captures an M3 Enigma and codebook. U-559 (Oct 1942) — the M4's short signal codebook. Without these captures, Bletchley would not have entered the M4 in time.

Estimate: breaking Enigma shortened WWII by ~2 years and saved ~14 million lives (estimate by Hinsley, British Intelligence in the Second World War).

Lorenz SZ40/SZ42 ("Tunny")

German machine for strategic (not tactical) communication — Hitler ↔ generals. A binary Vernam pseudo-OTP stream cipher with 12 rotors (5 chi + 5 psi + 2 motor). Stronger than Enigma.

Break: Bill Tutte derives the complete structure looking only at ciphertext (Jan 1942) — a feat of mathematics considered one of the greatest in history. Tommy Flowers builds Colossus (1943) — the first programmable electronic computer, 1500–2400 valves, specifically to break Lorenz. 10 Colossi operational by the end of the war.

Type B / Purple (Japan WWII)

Japanese diplomatic cipher machine — substitution in the Latin alphabet via stepping switches (electric telephone rotary switches). Not rotors like Enigma.

Break: William Friedman + Frank Rowlett (US SIS) by pure reverse engineering with no machine capture — only traffic analysis (1940). Codename Magic. Allowed reading Japanese diplomatic traffic including the eve of Pearl Harbor (but the message reached the Pacific command too late).

M-209 (Hagelin)

American portable machine (Boris Hagelin, Crypto AG). Purely mechanical (no electricity). 6 pin rotors, plus lugs on a drum. Breakable by the Germans in hours on tactical communications; used for low-level C2 because strategic military ciphers used others.

SIGABA (ECM Mark II)

American high-end machine (Friedman + Rowlett 1939–1941). 15 rotors in three banks with pseudo-random stepping. Never broken during WWII. Retired in the 1950s.

Crypto AG / Hagelin post-WWII

Boris Hagelin emigrates to Switzerland post-WWII. Founds Crypto AG (CAG). Sells machines to governments worldwide. Decades later (revealed 2020 via the Washington Post + ZDF): the company was secretly bought by the CIA + German BND in Operation Rubicon / Thesaurus / Minerva, and the machines sold to 130+ countries had deliberate backdoors. The NSA and BND reading "encrypted" traffic from Argentina, Iran, Libya, the Vatican, Brazil… until 2018.

8. Cold War paper ciphers

VIC cipher

Cipher used by the Soviet agent Reino Häyhänen and discovered by Hans Stuhmüller. A combination of straddling checkerboard substitution + two transposition tableaux + a key derived from a date + personal ID. Manual but very strong; broken by the NSA only after a defector handed over the manual.

Solitaire (Schneier, 1999)

Bruce Schneier designs it for Neal Stephenson to use in Cryptonomicon. A stream cipher based on a deck of 52 cards + 2 jokers. A break demonstrated by Crowley in 1999: the sequence has a detectable statistical bias.

Numbers stations

Shortwave radio stations transmit strings of numbers in a synthesized voice. OTP-encrypted instructions for agents. Still active in 2026: "Lincolnshire Poacher" (UK, decommissioned 2008), "The Buzzer" (UVB-76, Russia, active since 1982), the Cuban "Atención" stations.

9. The dividing line: Shannon 1949

Communication Theory of Secrecy Systems (BSTJ 28, Oct 1949):

1. Defines perfect secrecy mathematically.
2. Proves the theorem \(|K| \geq |M|\).
3. Proposes the product cipher alternating substitution (non-linear S-boxes) and transposition (linear P-boxes).
4. Introduces confusion and diffusion.
5. Establishes a formal adversary model.

After Shannon, classical cryptography ends; modern cryptography begins. Everything after (Feistel, DES, AES, RSA) derives from this foundation.

Summary: vulnerabilities of the classical ciphers

Lesson: no classical cipher (except a perfectly used OTP) survives systematic cryptanalysis. Modernity begins when a formal security proof replaces intuitive trust.