Substitution Cipher

Updated 11 Aug 2026

• •

  Definition

  • •

    a Shannon Cipher where the key is a permutation on some alphabet $\Sigma$, and encryption applies the permutation to each symbol of the message independently

  • •

    $E(k,m):=(k(m[0]),k(m[1]), \dots ,k(m[L−1]))$; decryption applies the inverse permutation $k^{-1}$

• •

  Key space size

  • •

    for the 26-letter alphabet, a key is a permutation of 26 letters: $26! \approx 2^{88}$ possible keys — a large key space, yet still trivially breakable

• •

  Caesar cipher

  • •

    a degenerate substitution cipher with no real key at all — the substitution is a fixed shift by 3 (A->D, B->E, ...); since the "key" isn't secret or random, anyone who knows the scheme can decrypt instantly

• •

  Why it's not perfectly secure

  • •

    repeated symbols in the plaintext produce repeated symbols in the ciphertext (if $m[0] = m[1]$, then $c[0] = c[1]$ too, regardless of the key) — this alone distinguishes message distributions

  • •

    known-structure attacks — e.g. if messages are known to start with a fixed header, an attacker who intercepts $c$ immediately learns which ciphertext symbols correspond to which header letters throughout the message, enabling frequency analysis

• •

  Breaking it via letter-frequency cryptanalysis (ciphertext-only attack)

  • •

    count letter frequencies in the ciphertext; the most frequent ciphertext letter is very likely the encryption of E (12.7% of English text), the second most frequent is likely T (9.1%), the third is likely A (8.1%)

  • •

    once single-letter frequencies stop resolving the rest of the table, move to digram frequencies (common pairs like HE, AN, IN, TH) and then trigrams, filling in the remaining key entries by trial and error

  • •

    this fully recovers the key table — a large key space (2^88) is irrelevant if the cipher leaks this much structure

• •

  Related

  • •

    Shannon Cipher

  • •

    Perfect Security

  • •

    Vigenère Cipher

◌ Explore connections in Graph view