Classical ciphers and historical cryptography

Updated 04 Nov 2026

• •

  Substitution ciphers and frequency cryptanalysis

  • •

    Monoalphabetic substitution cipher

    • •

      Definition -> a Shannon cipher where the secret key $k$ is an arbitrary permutation on an alphabet $\Sigma$.

    • •

      Encryption -> applies permutation $k$ to each character of message $m$ independently:
      $$E(k, m) := (k(m[0]), k(m[1]), \dots, k(m[L-1]))$$

    • •

      Decryption -> applies the inverse permutation $k^{-1}$:
      $$D(k, c) := (k^{-1}(c[0]), k^{-1}(c[1]), \dots, k^{-1}(c[L-1]))$$

  • •

    Key space size

    • •

      for the standard 26-letter English alphabet, the key space consists of all permutations of 26 elements:
      $$|K| = 26! \approx 4.03 \times 10^{26} \approx 2^{88.4}$$

    • •

      despite possessing $2^{88}$ potential keys (far exceeding what can be brute-forced by hand), the cipher is trivially breakable.

  • •

    Caesar cipher

    • •

      a degenerate monoalphabetic substitution where the permutation is a fixed modular shift by 3:
      $$c[i] = (m[i] + 3) \pmod{26}$$

    • •

      features zero real secrecy: because the shift is fixed, anyone who knows the algorithm decrypts instantly without search.

  • •

    Why monoalphabetic substitution fails

    • •

      Structural preservation -> identical plaintext letters always produce identical ciphertext letters at corresponding positions: if $m[i] = m[j]$, then $c[i] = c[j]$ for all keys $k$.

    • •

      Known-structure leakage -> intercepting messages with predictable headers (e.g. "From:", "HTTP/1.1") immediately reveals character mappings throughout the entire text.

  • •

    Letter-frequency cryptanalysis (ciphertext-only attack)

    • •

      natural human languages exhibit non-uniform unigram frequency distributions.

    • •

      English unigram baseline -> E ($\approx 12.7\%$), T ($\approx 9.1\%$), A ($\approx 8.1\%$), O ($\approx 7.5\%$), I ($\approx 7.0\%$), N ($\approx 6.7\%$).

    • •

      Attack procedure

      1. 1.

         tally letter counts across the intercepted ciphertext.

      2. 2.

         map the most frequent ciphertext letter to E, the second to T, and the third to A.

      3. 3.

         for ambiguous mappings, compute digram frequencies (common pairs: TH, HE, IN, ER, AN, RE) and trigrams (THE, AND, THA, ENT, ION).

      4. 4.

         complete the key table via trial and error on remaining infrequent characters.

    • •

      Core cryptographic principle -> a large key space ($2^{88}$) is necessary for security, but entirely insufficient on its own if the cipher leaks statistical structure.

  • •

    

  • •

    

• •

  Polyalphabetic substitution: The Vigenère cipher

  • •

    Mechanism

    • •

      16th-century cipher designed to defeat single-letter frequency cryptanalysis.

    • •

      secret key $k$ is a short word of length $d$. The key repeats cyclically across the length of the message.

    • •

      Encryption -> adds key letter mod 26: $c[i] = (m[i] + k[i \pmod d]) \pmod{26}$.

    • •

      Decryption -> subtracts key letter mod 26: $m[i] = (c[i] - k[i \pmod d]) \pmod{26}$.

  • •

    Defense against naive frequency analysis

    • •

      the same plaintext letter maps to different ciphertext letters depending on its position mod $d$, flattening the global letter frequency histogram.

  • •

    Cryptanalysis (Kasiski examination and coset decomposition)

    • •

      Recovering key length $d$

      • •

        repeated words in the plaintext produce identical ciphertext sequences whenever the distance between occurrences is a multiple of key length $d$.

      • •

        inding the greatest common divisor (GCD) of distances between repeated ciphertext sequences identifies candidates for $d$.

      • •

        alternatively, test candidate lengths $d = 1, 2, 3, \dots$ computing the Index of Coincidence for each coset until it matches English text ($\approx 0.067$).

    • •

      Solving the key

      • •

        once $d$ is determined, partition ciphertext $c$ into $d$ separate groups:
        $$C_j = \{ c[j], c[j + d], c[j + 2d], \dots \} \quad \text{for } j \in \{0, \dots, d-1\}$$

      • •

        every character within slice $C_j$ was shifted by the exact same single key letter $k[j]$.

      • •

        perform standard monoalphabetic frequency analysis on each slice $C_j$ independently to recover $k[j]$.

  • •

    Cryptographic assessment

    • •

      modular addition is a sound cryptographic primitive that directly anticipates keystream addition in stream ciphers.

    • •

      Vigenère's fatal vulnerability was using a short, repeating key rather than an independent keystream.

◌ Explore connections in Graph view