#!/usr/bin/env python3
"""Break a substitution cipher without ever looking at the key.

403,291,461,126,605,635,584,000,000 possible keys, and the message below falls
in three rounds of a loop -- to letter counts, two cribs, and a list of the
commonest English words. That gap, between an enormous keyspace and no security
at all, is the lesson: a big key does not help when the ciphertext still has the
shape of the language in it.

Run:  python3 frequency_analysis_py.py
"""

import string
from collections import Counter

ALPHABET = string.ascii_lowercase

# The secret substitution alphabet. Fixed here so the run is reproducible; in a
# real message this is the key, and nothing below ever reads it. It is used
# once, to make the ciphertext, and once at the very end to mark the answer.
KEY = "qwertyuiopasdfghjklzxcvbnm"

# Letter frequencies in English text, as percentages. Any published table will
# do -- they agree to within a point, and only the ORDER is used here.
ENGLISH_FREQ = {
    "e": 12.7, "t": 9.1, "a": 8.2, "o": 7.5, "i": 7.0, "n": 6.7, "s": 6.3,
    "h": 6.1, "r": 6.0, "d": 4.3, "l": 4.0, "c": 2.8, "u": 2.8, "m": 2.4,
    "w": 2.4, "f": 2.2, "g": 2.0, "y": 2.0, "p": 1.9, "b": 1.5, "v": 1.0,
    "k": 0.8, "j": 0.15, "x": 0.15, "q": 0.10, "z": 0.07,
}

# The commonest words in English -- roughly the first two hundred, which is what
# somebody doing this on paper carries in their head. Note what is NOT in it:
# every content word of the message below. A real attacker has a whole
# dictionary; this list is deliberately just the function words, so that what it
# achieves is a floor and not a trick.
COMMON = (
    "the be to of and a in that have i it for not on with he as you do at this "
    "but his by from they we say her she or an will my one all would there their "
    "what so up out if about who get which go me when make can like time no just "
    "him know take people into year your good some could them see other than then "
    "now look only come its over think also back after use two how our work first "
    "well way even new want because any these give day most us is are was were "
    "very much where should each many those may said little own under while such "
    "through does before between"
).split()

MESSAGE = (
    "the trouble with a substitution cipher is not that the key is small "
    "but that the language shows through it. every letter keeps the company "
    "it always kept. the letter that stands for e will still be the one you "
    "see most often and it will still sit beside the letters that follow e "
    "in ordinary writing. you are not attacking the cipher at all. you are "
    "reading the shape of english through a coat of paint."
)


def substitute(text: str, table: str) -> str:
    """Apply a 26-letter substitution alphabet. Anything else passes through."""
    return "".join(table[ALPHABET.index(c)] if c in ALPHABET else c for c in text)


def shape(word: str) -> tuple[int, ...]:
    """A word's repetition pattern: 'letter' and 'kettle' are both (0,1,2,2,1,3).

    A substitution cipher cannot change this, which is what makes it usable.
    """
    seen: dict[str, int] = {}
    return tuple(seen.setdefault(c, len(seen)) for c in word)


def main() -> None:
    ciphertext = substitute(MESSAGE, KEY)
    words = [w.strip(".,") for w in ciphertext.split()]

    print("1. THE KEYSPACE IS ENORMOUS, AND IT WILL NOT MATTER")
    keyspace = 1
    for n in range(2, 27):
        keyspace *= n
    print("   A substitution alphabet is any ordering of 26 letters, so there are 26! keys.")
    print(f"   26! = {keyspace:,}")
    print(f"       = {keyspace:.3e}   -- more keys than a brute-force search will ever see")
    print("   Nothing below tries even one of them.")
    print()

    print("2. THE CIPHERTEXT, WHICH IS ALL THE ATTACKER HAS")
    for i in range(0, 240, 80):
        print(f"   {ciphertext[i:i + 80]}")
    print("   ...")
    print()

    print("3. COUNT THE LETTERS: THE CIPHER RENAMED THEM AND KEPT EVERY COUNT")
    counts = Counter(c for c in ciphertext if c in ALPHABET)
    total = sum(counts.values())
    english_order = sorted(ENGLISH_FREQ, key=lambda c: -ENGLISH_FREQ[c])
    print("   cipher letter    count    share      same rank in English")
    for rank, (letter, n) in enumerate(counts.most_common(5)):
        plain = english_order[rank]
        print(f"        {letter}            {n:>4}    {100 * n / total:5.1f}%           "
              f"{plain!r}  ({ENGLISH_FREQ[plain]}%)")
    top = counts.most_common(1)[0][0]
    print(f"   The top letter of any English text is 'e', so {top!r} is probably 'e'.")
    print("   One guess, and it is only a guess -- until something else agrees with it.")
    print()

    print("4. CRIB ONE: THE COMMONEST THREE-LETTER WORD IS 'the'")
    three = Counter(w for w in words if len(w) == 3).most_common(3)
    for w, n in three:
        print(f"   {w!r} appears {n} times")
    crib = three[0][0]
    key: dict[str, str] = dict(zip(crib, "the"))
    print(f"   So {crib!r} = 'the', which fixes three letters at once:")
    print("   " + ", ".join(f"{c} -> {p}" for c, p in key.items()))
    e_letter = crib[2]
    order = [c for c, _ in counts.most_common()]
    rank = order.index(e_letter) + 1
    print(f"   Now check it against section 3. The crib says {e_letter!r} is 'e';")
    if rank == 1:
        print("   the counts said so too. Two independent methods agree, and that")
        print("   agreement -- not either one alone -- is the moment you know.")
    else:
        print(f"   the counts ranked {e_letter!r} number {rank}, and put {top!r} first instead.")
        print(f"   So the frequency guess was WRONG, and the crib has just corrected it.")
        print("   In four hundred letters the counts are noisy; a word is structural.")
        print("   That is why you never rest a break on one method.")
    print()

    print("5. CRIB TWO: A ONE-LETTER WORD IS 'a' OR 'i'")
    singles = sorted(set(w for w in words if len(w) == 1))
    print(f"   one-letter words in the ciphertext: {singles}")
    fresh = [w for w in singles if w not in key]
    for w in fresh:
        key[w] = "a"
    known = [w for w in singles if w not in fresh]
    if known:
        print(f"   {known} the crib already named, so they are evidence, not guesses:")
        print(f"   a one-letter word reading {'/'.join(key[w] for w in known)!r} is exactly what")
        print("   the crib predicted, which is one more thing that had to line up.")
    print(f"   {fresh} is new. Taking it as 'a' gives a fourth letter for free.")
    print()

    def render(word: str) -> str:
        return "".join(key.get(c, "_") for c in word)

    print("6. NOW PROPAGATE. A WORD WHOSE SHAPE AND KNOWN LETTERS FIT EXACTLY ONE")
    print("   COMMON WORD MUST BE THAT WORD -- WHICH FIXES MORE LETTERS, AND REPEATS.")
    rounds = 0
    changed = True
    while changed:
        changed = False
        rounds += 1
        taken = set(key.values())
        for w in words:
            if "_" not in render(w):
                continue
            fits = []
            for cand in COMMON:
                if len(cand) != len(w) or shape(cand) != shape(w):
                    continue
                if all(key.get(c, p) == p and (p not in taken or c in key)
                       for c, p in zip(w, cand)):
                    fits.append(cand)
            if len(fits) == 1:
                for c, p in zip(w, fits[0]):
                    if c not in key:
                        key[c] = p
                        taken.add(p)
                        changed = True
        print(f"   after round {rounds}: {len(key)} of 26 letters known")
    print()

    print("7. THE MESSAGE")
    recovered = "".join(key.get(c, "_") if c in ALPHABET else c for c in ciphertext)
    for i in range(0, 400, 80):
        print(f"   {recovered[i:i + 80]}")
    print()

    print("8. WHAT IT COST, AND WHAT IS LEFT")
    right = sum(1 for a, b in zip(recovered, MESSAGE) if a == b)
    print(f"   characters recovered: {right} of {len(MESSAGE)} "
          f"({100 * right / len(MESSAGE):.1f}%)")
    print(f"   letters of the key:   {len(key)} of 26")
    missing = sorted(set(MESSAGE) & set(ALPHABET) - set(key.values()))
    print(f"   still unknown:        {missing}")
    print("   Every one of those appears only in words the 200-word list does not")
    print("   contain, so nothing pinned it. A real attacker has a whole dictionary")
    print("   and never gets this far by hand -- and a person just reads the gaps.")
    print()
    print("   No key was tried. No key was guessed. The ciphertext told on itself,")
    print("   because a substitution cipher renames the letters and leaves every")
    print("   relationship between them exactly where it was.")


if __name__ == "__main__":
    main()