Polyalphabetic Ciphers

For 300 years the Vigenere cipher was considered unbreakable. Then mathematician Charles Babbage (the same one who designed the Difference Engine) broke it in 1854 - and did not publish, because the Crimean War was underway and the method was needed by British intelligence. Nine more years passed before Kasiski independently rediscovered the same attack. This is a story about how every generation believes it has found an unbreakable cipher.

• **Enigma and World War II:** breaking the rotor machine at Bletchley Park shortened the war by an estimated 2-4 years
• **One-time pad:** the only theoretically perfect polyalphabetic cipher - when the key equals the message length and is used exactly once
• **Modern stream ciphers:** RC4, ChaCha20 are direct descendants of the Vigenere idea, with a cryptographically strong keystream generator

The Vigenere Cipher

For three centuries the Vigenere cipher bore the label 'le chiffre indéchiffrable' - the unbreakable cipher. The idea: instead of one Caesar shift alphabet, cycle through multiple alphabets according to a keyword. The same letter 'A' in plaintext encrypts differently at each position - frequency analysis loses its foothold.

**Mechanics:** the keyword repeats along the plaintext. Each keyword letter defines the Caesar shift for the corresponding plaintext letter. Formula: `C[i] = (P[i] + K[i]) mod 26`, decryption: `P[i] = (C[i] - K[i] + 26) mod 26`.

**Kasiski attack (1863):** find repeated fragments in the ciphertext - the distance between them is a multiple of the key length. Knowing the key length splits the problem into several Caesar ciphers, each breakable by frequency analysis.

The Beaufort Cipher

Admiral Francis Beaufort - the same one whose wind scale hangs in every port - proposed a Vigenere variant with one elegant property: encryption and decryption are the same operation. This halves the complexity of any mechanical implementation.

**Difference from Vigenere:** instead of `(P + K) mod 26` the formula is `(K - P + 26) mod 26`. Applying the same operation to the ciphertext recovers the plaintext - the cipher is its own inverse.

**Variant Beaufort** is a third form: `C = (P - K + 26) mod 26`. This is literally Vigenere with the decryption key used for encryption. All three variants (Vigenere, Beaufort, Variant Beaufort) are vulnerable to the Kasiski test.

The Enigma Machine: How It Works

1940, Bletchley Park. Alan Turing and his team are working on the German Enigma - a machine that German commanders believed to be absolutely secure. Enigma is an electromechanical Vigenere cipher with a key space of approximately 10^{16} combinations.

**Three Enigma components:** the rotor (a substitution disc that steps after each keypress), the reflector (bounces the signal back, ensuring involution), and the plugboard (adds 11 letter-swap pairs). Pressing a key sends a signal through all rotors forward, reflects off the reflector, and returns via a different path.

**Critical Enigma weakness:** the reflector prevents any letter from encrypting to itself. This sounds minor, but it allowed Turing to build the 'bombe' - an enumeration device that eliminated rotor positions where any letter encrypted to itself.

Rotor Machines and Cryptanalysis

Enigma is the most famous rotor machine, but not the only one. The American SIGABA (1940) used 15 rotors with irregular stepping - it was never broken by the enemy in the field. The Swedish Hagelin C-38 became a manufacturing foundation: its licensed variant M-209 served in the US Army.

**Turing's cryptanalysis method:** the Allies knew message structures - weather reports always began with 'WETTER' (weather) and ended with operator callsigns. These known plaintext fragments (cribs), combined with the impossibility of self-encryption, allowed building constraint chains and testing rotor positions mechanically.

**Lesson for modern cryptography:** any algebraic property of a cipher (self-encryption impossible, permutation parity fixed, etc.) is a potential attack surface. Modern ciphers (AES) are designed to exhibit none of these properties.

Polyalphabetic Ciphers

• Vigenere: each position uses a distinct Caesar shift keyed by a keyword - direct frequency analysis fails
• Beaufort: C=(K-P) mod 26, an involution - encryption and decryption share one function
• Kasiski test: ciphertext repetitions expose key length, after which Vigenere reduces to a set of Caesar ciphers
• Enigma: electromechanical polyalphabetic cipher with ~10^{16} key space, broken through the self-encryption impossibility
• Rotor machines teach: any algebraic property of a cipher is a potential attack surface

Related Topics

Polyalphabetic ciphers bridge manual cryptography and the machine age.

• Substitution Ciphers (Caesar, Atbash) — Vigenere = multiple Caesar ciphers cycling by keyword
• Transposition Ciphers — Next class: positions change, not the letters themselves
• Symmetric Encryption (AES) — Modern descendant: no algebraic weaknesses, no exploitable structure

Вопросы для размышления

• Why is the one-time pad (OTP) theoretically perfectly secure when used exactly once - and why is it almost never used in practice?
• What role did Enigma operator mistakes play - and what does this imply about the security of modern protocols?
• If Turing had not known that Enigma cannot encrypt a letter to itself, how much harder would breaking it have been?

Связанные уроки

• nt-03
• ml-01