Secret codes

Chidi and Ngozi sit at opposite ends of their classroom in Lagos. Chidi wants to pass Ngozi a note about the surprise party they are planning for their friend Tobi — but the note will pass through many hands, and Tobi might see it. So Chidi writes:

PHHW DW QRRQ

Ngozi knows the secret: every letter has been moved 3 places along the alphabet. She moves each letter 3 places back — P to M, H to E, W to T — and reads: MEET AT NOON.

More than two thousand years ago, the Roman general Julius Caesar hid his letters in exactly this way. The Roman writer Suetonius tells us that Caesar replaced each letter by the one three places later: D for A, E for B, and so on. That is why this kind of code is called a Caesar shift.

Write the alphabet round a circle, and a second copy on a smaller wheel inside it. Turn the inside wheel 3 places. Now every letter on the outside sits next to its code letter on the inside: A next to D, B next to E, …

On a wheel, the alphabet has no end. After Z comes A again, just as after 12 o'clock on a clock comes 1 o'clock. So with a shift of 3, X becomes A, Y becomes B and Z becomes C. That is what wrapping round means.

Two more facts follow from the wheel. Shifting by $a$ and then by $b$ is the same as one shift by $a + b$ (for example, 10 and then 20 is 30, which is once round and 4 more: a shift by 4). And a shift never sends two different letters to the same code letter — the inside wheel has each letter exactly once — which is why every coded message can be decoded.

Why letter-counting breaks substitution ciphers. A substitution cipher changes which letters are used, but not how often they are used. In English, E is the most common letter: in a long text, roughly one letter in every eight is an E. Next come T, A, O, I and N. So if the most common letter of a long coded message is Q, then Q very probably stands for E. A few good guesses like this, plus short words like THE and A, and the whole message starts to appear. This is called frequency analysis.

Here is a secret message, made with a Caesar shift:

WOOD WO XOKB DRO QBOOX QKDO LOCSNO DRO BSFOB KD COFOX DRSC OFOXSXQ. LBSXQ DRO WKZ, DRO BYZO KXN DRBOO ZOXMSVC. GO GSVV COXN DRO XOHD COMBOD WOCCKQO GROX DRO WYYX SC RSQR.

The chart shows how many times each of its ten most common letters appears.

What to try:

• Which letter is most common? If it stands for E, how many places is it from E? That is probably the key.
• Decode the first few words with your key. Do they make sense? If not, try the second most common letter as E.
• Look for a short word that appears many times. In English, a common three-letter word is THE.

Gideon only plays with statements that are exactly true or exactly false. Decide, and give a reason.

1. "With a shift of 3, Y becomes B." — True. Y, Z, A, B: three places on, wrapping round.
2. "A shift forward by 5 is undone by a shift forward by 21." — True. $5 + 21 = 26$, once round the wheel.
3. "There are 26 Caesar shifts that change a message." — False. There are 26 shifts, but the shift by 0 changes nothing: 25 change the message.
4. "A message that looks like nonsense is safe." — False. A Caesar message can be cracked by trying 25 keys.
5. "A shift by 10 and then a shift by 20 is the same as a shift by 4." — True. 30 places is once round and 4 more.

/-- A Caesar shift by `k` on letter numbers (A = 0, …, Z = 25): move `k` places on, wrapping
round from 25 back to 0. -/
def shift (k n : Nat) : Nat := (n + k) % 26

/-- Shifting by 3 wraps round the end of the alphabet: X (23) → A (0), Y (24) → B (1),
Z (25) → C (2). And M (12) → P (15) needs no wrapping. -/
theorem wrap_around : shift 3 23 = 0 ∧ shift 3 24 = 1 ∧ shift 3 25 = 2 ∧ shift 3 12 = 15 := by
  decide

/-- A shift always lands on one of the 26 letters: a remainder on division by 26 is less
than 26. This applies core Lean's `Nat.mod_lt`. -/
theorem shift_lt (k n : Nat) : shift k n < 26 :=
  Nat.mod_lt _ (by decide)

/-- **A shift forward by `k` is undone by a shift forward by `26 − k`**: together they move
26 places, once round the whole wheel. -/
theorem shift_undo (k n : Nat) (hk : k ≤ 26) (hn : n < 26) : shift (26 - k) (shift k n) = n := by
  unfold shift
  omega

/-- Two shifts, one after the other, are one shift: by `a`, then by `b`, is the same as by
`a + b`. (So the order of two shifts does not matter.) -/
theorem shift_shift (a b n : Nat) : shift b (shift a n) = shift (a + b) n := by
  unfold shift
  omega

/-- Shifting by `k + 26` is the same as shifting by `k`. So every shift is one of the shifts
0, 1, …, 25: there are **at most** 26 different shifts. -/
theorem shift_add_twenty_six (k n : Nat) : shift (k + 26) n = shift k n := by
  unfold shift
  omega

/-- The shifts 0, 1, …, 25 are all different: shift `k` sends A (0) to letter number `k`. So
there are **exactly** 26 shifts — and only 25 that change the message. -/
theorem shifts_differ (k : Nat) (hk : k < 26) : shift k 0 = k := by
  unfold shift
  omega

/-- A shift never sends two different letters to the same letter. That is why a coded message
can always be decoded. -/
theorem shift_injective (k n m : Nat) (hn : n < 26) (hm : m < 26)
    (h : shift k n = shift k m) : n = m := by
  unfold shift at h
  omega

/-- Shift one character. Computers store `A` as the number 65, …, `Z` as 90. A capital letter
is turned into its letter number (subtract 65), shifted, and turned back (add 65); spaces and
other characters are left as they are. -/
def shiftChar (k : Nat) (c : Char) : Char :=
  if 65 ≤ c.toNat ∧ c.toNat ≤ 90 then Char.ofNat ((c.toNat - 65 + k) % 26 + 65) else c

/-- The Caesar cipher with key `k`: shift every letter of the message by `k`. -/
def caesar (k : Nat) (message : String) : String :=
  String.ofList (message.toList.map (shiftChar k))

/-- Julius Caesar's shift of 3: MEET AT NOON becomes PHHW DW QRRQ. -/
theorem meet_at_noon : caesar 3 "MEET AT NOON" = "PHHW DW QRRQ" := by
  decide

/-- Wrapping round: with a shift of 3, ZEBRA becomes CHEUD (Z → C). -/
theorem zebra : caesar 3 "ZEBRA" = "CHEUD" := by
  decide

/-- To decode a shift of 3, shift forward by 26 − 3 = 23. -/
theorem decode_by_23 : caesar 23 "PHHW DW QRRQ" = "MEET AT NOON" := by
  decide

/-- Breaking a Caesar cipher by trying every key: among the 26 shifts of WKLV LV IXQ, one
reads THIS IS FUN. -/
theorem try_every_shift : "THIS IS FUN" ∈ (List.range 26).map (fun k => caesar k "WKLV LV IXQ") := by
  decide

/-- **Decoding undoes encoding, for every message and every key**: the Caesar cipher with key
`26 − k` decodes the Caesar cipher with key `k`. -/
theorem caesar_undo (k : Nat) (hk : k ≤ 26) (message : String) :
    caesar (26 - k) (caesar k message) = message := by
  unfold caesar
  rw [String.toList_ofList, List.map_map]
  have : (shiftChar (26 - k) ∘ shiftChar k) = id := funext (shiftChar_undo k hk)
  rw [this, List.map_id, String.ofList_toList]

/-- A substitution key chooses a code letter for A (26 choices), then for B (25 left), and so
on: 26 × 25 × ⋯ × 1 keys — more than 400 million million million million. -/
theorem substitution_keys : factorial 26 = 403291461126605635584000000 := by
  decide

"""Caesar shifts: encoding, wrapping round, and breaking by trying every key.

Letters are numbered A = 0, ..., Z = 25, and a Caesar shift by k sends
letter n to (n + k) mod 26, so Z wraps round to A. The program encodes and
decodes the lesson's examples, then breaks a secret message by trying all
26 shifts. To pick out the right one automatically, it gives each attempt a
score that measures how far its letter counts are from typical English
letter frequencies (smaller is more English-like).
"""

import textwrap

ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

# Typical percentages of each letter in long English texts (A to Z).
ENGLISH = [8.2, 1.5, 2.8, 4.3, 12.7, 2.2, 2.0, 6.1, 7.0, 0.15, 0.8, 4.0, 2.4,
           6.7, 7.5, 1.9, 0.1, 6.0, 6.3, 9.1, 2.8, 1.0, 2.4, 0.15, 2.0, 0.07]

SECRET = "ESP ECPLDFCP TD FYOPC ESP XLYRZ ECPP"

def shift_letter(letter, k):
    """Shift one capital letter k places along the alphabet, wrapping round."""
    return ALPHABET[(ALPHABET.index(letter) + k) % 26]

def caesar(message, k):
    """Shift every capital letter of the message; leave other characters."""
    return "".join(shift_letter(c, k) if c in ALPHABET else c
                   for c in message)

def english_score(text):
    """How far the letter counts are from English (chi-squared statistic)."""
    letters = [c for c in text if c in ALPHABET]
    total = len(letters)
    score = 0.0
    for i, letter in enumerate(ALPHABET):
        expected = total * ENGLISH[i] / 100
        observed = letters.count(letter)
        score += (observed - expected) ** 2 / expected
    return score

def best_shift(secret):
    """The decoding shift whose result has the most English-like letters."""
    return min(range(26), key=lambda k: english_score(caesar(secret, k)))

def main():
    for message, k, note in [("MEET AT NOON", 3, ""),
                             ("ZEBRA", 3, "  (Z wraps round to C)"),
                             ("PHHW DW QRRQ", 23, "  (23 undoes 3)")]:
        label = f"{message}, shift {k}:"
        print(f"{label:<25}{caesar(message, k)}{note}")
    print()
    print(f"Secret message: {SECRET}")
    print("Every possible decoding (shift forward by k):")
    best = best_shift(SECRET)
    for k in range(26):
        attempt = caesar(SECRET, k)
        mark = "  <- most English-like" if k == best else ""
        print(f"  k = {k:>2}: {attempt}{mark}")
    print(f"The sender shifted by {(26 - best) % 26};"
          f" shifting by {best} undoes it.")
    print()
    print(textwrap.fill(
        "Epistemic status: exact and exhaustive - every one of the 26 shifts "
        "was tried, so the message cannot hide from this search. The "
        "'English-like' score is only a heuristic: for very short or unusual "
        "messages it can point to the wrong shift, so a person still reads "
        "the answer to check that it makes sense.",
        width=78,
    ))

if __name__ == "__main__":
    main()

Trying every key is exhaustive: the message cannot hide from it. The score is only a helpful guess, so a person still reads the answer to check it makes sense.

"""Breaking a substitution cipher by counting letters.

A substitution cipher replaces each letter by another letter, using a
scrambled alphabet as the key. There are 26 x 25 x ... x 1 keys - far too
many to try - but the cipher keeps the pattern of how often each letter is
used. The program encodes a paragraph of English with a random key (from a
seeded random number generator), counts the letters of the secret message,
and compares the most common ones with the most common letters of English.
Then it tries the simplest possible attack - match the letters by rank -
and reports how much of the message that alone gets right.
"""

import math
import random
import textwrap
from collections import Counter

ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
ENGLISH_ORDER = "ETAOINSHRDLCUMWFGYPBVKJXQZ"

PLAIN = (
    "PEOPLE HAVE SENT SECRET MESSAGES FOR THOUSANDS OF YEARS. A SIMPLE WAY "
    "TO HIDE A MESSAGE IS TO REPLACE EVERY LETTER WITH ANOTHER LETTER. THE "
    "MESSAGE THEN LOOKS LIKE NONSENSE, BUT A CLEVER READER CAN STILL BREAK "
    "THE CODE. IN ENGLISH THE LETTER E APPEARS MORE OFTEN THAN ANY OTHER "
    "LETTER, AND THE WORD THE IS VERY COMMON. SO THE CODE BREAKER COUNTS "
    "THE LETTERS IN THE SECRET MESSAGE AND GUESSES THAT THE MOST COMMON ONE "
    "STANDS FOR E. THEN SHE LOOKS FOR SHORT WORDS AND REPEATED PATTERNS, "
    "AND THE HIDDEN MESSAGE SLOWLY APPEARS."
)

def random_key(seed):
    """A scrambled alphabet: plain letter ALPHABET[i] becomes key[i]."""
    letters = list(ALPHABET)
    random.Random(seed).shuffle(letters)
    return "".join(letters)

def substitute(text, key):
    """Replace each capital letter using the key; keep other characters."""
    table = dict(zip(ALPHABET, key))
    return "".join(table.get(c, c) for c in text)

def letter_counts(text):
    """How many times each capital letter appears, most common first."""
    return Counter(c for c in text if c in ALPHABET).most_common()

def rank_guess(secret):
    """Guess a decoding key by matching letters by frequency rank."""
    ranked = [letter for letter, _ in letter_counts(secret)]
    unused = [c for c in ALPHABET if c not in ranked]
    return dict(zip(ranked + unused, ENGLISH_ORDER))

def main():
    key = random_key(1586)
    secret = substitute(PLAIN, key)
    print(f"Possible keys: 26! = {math.factorial(26):,}")
    print("Secret message (start): " + secret[:52] + "...")
    counts = letter_counts(secret)
    total = sum(n for _, n in counts)
    decode = {code: plain for plain, code in zip(ALPHABET, key)}
    print(f"Most common letters in the secret message ({total} letters):")
    print("  code letter  count  share  really stands for  English rank")
    for rank, (code, n) in enumerate(counts[:6]):
        line = (f"  {code:^11}  {n:>5}  {100 * n / total:>4.0f}%"
                f"  {decode[code]:^17}  {ENGLISH_ORDER[rank]:^12}")
        print(line.rstrip())
    guess = rank_guess(secret)
    attempt = "".join(guess.get(c, c) for c in secret)
    right = sum(1 for p, a in zip(PLAIN, attempt) if p in ALPHABET and p == a)
    print(f"Matching letters by rank alone gets {right} of {total} letters"
          f" right ({100 * right / total:.0f}%):")
    print("  " + attempt[:60] + "...")
    print("A code breaker then fixes it using words such as THE and patterns.")
    print()
    print(textwrap.fill(
        "Epistemic status: exact counting, but one experiment - one "
        "paragraph and one random key. Long English texts usually have E as "
        "their most common letter, but short or unusual texts may not, so "
        "frequency analysis gives good guesses, not certainties. Here the "
        "guesses are checked against the real key.",
        width=78,
    ))

if __name__ == "__main__":
    main()

The most common code letter really did stand for E. But matching letters by rank alone got well under half of the message right: the counts in one paragraph are not exactly the same as in English as a whole. Real code breakers use the counts to make a start, and then use short words, repeated letters and patterns to finish the job. This was one experiment, with one paragraph and one key — evidence, not a law.

Make your own alphabet wheel from two paper circles and a split pin — it makes encoding and decoding quick. You can ask for a hint whenever you like.

A cipher's key pairs up the alphabet with itself, so that every letter has exactly one code letter, and every code letter comes from exactly one letter. In the language of sets and functions, it is a one-to-one correspondence (a bijection) from the set of 26 letters to itself. Decoding is the inverse pairing: follow every arrow backwards. And doing one shift and then another is a chain of actions, just like those in One thing after another; undoing a shift by $k$ with a shift by $26 - k$ is like undoing a quarter turn with three more quarter turns.

The alphabet wheel is a clock with 26 hours. This optional trail explores what arithmetic on a clock can do:

• Rome. The writer Suetonius (about 121 CE) reports that Julius Caesar wrote secret letters with a shift of three, and that the emperor Augustus used a shift of one.
• Baghdad. In the 9th century the scholar Abū Yūsuf Yaʿqūb al-Kindī wrote A Manuscript on Deciphering Cryptographic Messages, the earliest known description of breaking codes by counting how often letters appear — frequency analysis.
• Scotland and England. In 1586 Mary, Queen of Scots, wrote coded letters from prison. Thomas Phelippes, a code breaker working for Queen Elizabeth I's government, used frequency analysis to read them. The letters were used as evidence against her, and she was executed in 1587.
• A secret that need not be secret. In 1883 the Dutch-born cryptographer Auguste Kerckhoffs, working in France, wrote that a military cipher should stay safe even if the enemy captures the method: only the key should need to be secret.
• Codes that were never broken. In the Second World War, Navajo Code Talkers in the United States Marine Corps sent messages in a code based on the Navajo language. It was never broken.
• Machines. The German Enigma machine was first broken in 1932 by the Polish mathematicians Marian Rejewski, Jerzy Różycki and Henryk Zygalski. In 1939 they shared their methods with Britain and France, and at Bletchley Park in England a team including Alan Turing broke Enigma messages throughout the war.
• Codes for everyone. In 1976 Whitfield Diffie and Martin Hellman, and in 1977 Ron Rivest, Adi Shamir and Leonard Adleman, published new kinds of ciphers whose safety comes from number theory — ideas found a few years earlier, in secret, by James Ellis, Clifford Cocks and Malcolm Williamson at Britain's GCHQ. These ideas protect messages and payments on the internet today; see Cryptography.

• Simon Singh, The Code Book (1999), and its version for young readers, The Code Book: How to Make It, Break It, Hack It, Crack It (2001) — the history of codes from Caesar to the internet.
• Janet Beissinger and Vera Pless, The Cryptoclub: Using Mathematics to Make and Break Secret Codes (2006) — a book written for children aged about 10–14, with activities.
• David Kahn, The Codebreakers (1967) — the classic, detailed history of cryptography.