Breaking the Substitution Cipher

Breaking the Substitution Cipher: No Key to Repeat, So Nothing to Kasiski

Introduction

Every cipher broken so far on this site, Caesar, Affine, Vigenère, Beaufort, has one thing in common: a small key that repeats or cycles predictably. That’s exactly what Kasiski examination and the Index of Coincidence exploit. The general monoalphabetic substitution cipher breaks that pattern. Its key is a single arbitrary rearrangement of all 26 letters, applied consistently across the whole message. There’s no shift to brute-force (26! ≈ 4 × 10²⁶ possible keys, not 26) and no repeating period to detect. Instead, this cipher falls to two different ideas entirely: frequency analysis to make an educated first guess, and a hill-climbing search that refines that guess by repeatedly asking “does this swap make the text look more like English?”

Table of Contents

• Why Kasiski and the IC Don’t Apply Here
• Step 1: Frequency Analysis, A Starting Guess
• Step 2: Hill-Climbing With Digram Statistics
• Step 3: Locking In the Recovered Key
• A Worked Example
• Python Implementation
• Interactive Visualizer
• Substitution vs. the Repeating-Key Ciphers
• FAQ
• References

Why Kasiski and the IC Don’t Apply Here

Kasiski examination works by finding repeated ciphertext sequences and reasoning about the distances between them. That signal only exists because a short key cycles back on itself. The Index of Coincidence measures how “clumped” a text’s letters are once it’s been split into interleaved streams at the correct key length. Both techniques are, fundamentally, ways of recovering a key length.

A monoalphabetic substitution cipher doesn’t have a key length to recover. The “key” is a single mapping, one fixed replacement for each of the 26 letters, applied uniformly to the entire message. There’s nothing to split into columns and nothing that repeats at an interval. What does survive the substitution, though, is the statistical shape of the underlying language: E is still the most common letter in the plaintext, TH is still a common pair, THE is still a common word. They’re just wearing different disguises now. That’s the opening an attacker uses instead.

Step 1: Frequency Analysis, A Starting Guess

The first move is the same one people have used by hand for centuries: count how often each ciphertext letter appears, then match the most frequent ciphertext letters to English’s most frequent letters, in order: E, T, A, O, I, N, S, H, R, D, L, C, U, M, W, F, G, Y, P, B, V, K, J, X, Q, Z.

This alone rarely produces a perfect key. English letter frequencies are a population average, not a guarantee for any one specific message, and short or unusual texts drift from the expected order. But it’s an excellent starting point, usually good enough to get the high-frequency letters (E, T, A) right immediately, which matters a lot for what comes next.

Step 2: Hill-Climbing With Digram Statistics

From that starting key, the search improves itself iteratively:

1. Swap two letters in the candidate key at random.
2. Score the resulting decryption. The score combines two signals:
   • Digram (letter-pair) log-frequencies: how often each adjacent letter pair in the decrypted text actually occurs in real English. TH, HE, IN, and ER score well; QZ or XJ score poorly.
   • A bonus for whole recognized words: whenever a decrypted word exactly matches a common English word, the score gets a flat boost. This is what finally resolves rare letters (J, K, Q, V, X) that digram statistics alone can’t always pin down. Two rare letters can look equally implausible to a digram-only scorer, even when only one of them is correct.
3. Keep the swap if the score improved. If not, usually reject it and try a different swap, but occasionally accept a slightly worse swap anyway. This is simulated annealing: early in the search, the tolerance for a worse move is high (to explore broadly); it cools down over time until the search only accepts genuine improvements. Without this, a pure “only ever accept improvements” hill climb reliably gets stuck: two or three letters end up swapped with each other in a way that looks almost as good as the true key. A single swap out of that trap always looks like a step backward. A bit of tolerated randomness is what lets the search step through that dip.
4. Repeat for thousands of swaps, from multiple random starting keys. Because this is a randomized search rather than an exhaustive one, running it a few times from different starting points is worth it. Keeping the best-scoring result found across all of them makes landing on the true key far more reliable than a single run.

Step 3: Locking In the Recovered Key

Whichever candidate key scored highest across every restart is the answer. Applying it to the full ciphertext produces the recovered plaintext. The readability of that output is itself the final confirmation that the search actually converged on the truth, rather than merely a locally good-looking impostor.

A Worked Example

Using the visualizer’s default ciphertext (738 letters, encrypted with a keyword-derived key):

1. Frequency analysis counts each ciphertext letter and proposes an initial guess. For example, whichever ciphertext letter is most frequent gets tentatively mapped to E. This gets several high-frequency letters right immediately but leaves plenty of mistakes, especially among rarer letters. Applying that raw frequency-order guess to just this ciphertext’s first 14 letters produces MDSDARWHAGETOL, against a true plaintext of MONOALPHABETIC: 6 of the 14 letters (M, A, H, A, E, T) are already correct, all of them common ones, while the rarer letters in between are still wrong. That’s the head start hill-climbing gets to build on, not a finished answer.
2. The hill-climbing search starts from that guess (plus three additional random restarts) and runs several thousand candidate swaps per restart, scoring each by digram statistics and common-word matches, occasionally tolerating a worse swap early on to avoid getting stuck.
3. Across all restarts, the best-scoring key found reaches a fit score of 230.29, decisively ahead of any of the near-miss keys the search passes through along the way, which typically score several hundred points lower.
4. Decrypting the full ciphertext with that key reveals a coherent passage: the same passage this article uses to describe the attack, recovered rather than assumed:

“Monoalphabetic substitution ciphers replace each letter of the alphabet with another letter according to a fixed mapping… An attacker starts by matching the most frequent ciphertext letters to the most frequent letters in English, then refines that initial guess using a hill-climbing search…”

One small caveat about uniqueness: the recovered key is only pinned down for letters that actually appear somewhere in the ciphertext. Any letter absent from the message entirely leaves its corresponding key entry unconstrained. Nothing in the ciphertext ever tests it, so the search is free to leave it wherever a random shuffle or swap happened to put it, without affecting the score at all.

Python Implementation

The interactive visualizer above runs this exact pipeline in JavaScript, including the same digram-frequency and common-word tables (both computed from a large public-domain English text). Here’s the same attack in Python.

Key Features

• Digram table with full coverage: Unlike a short hand-picked list of “the 50 most common pairs,” BIGRAMS here covers roughly 390 letter pairs, including rare ones like KE, QU, and EX. That matters because rare letters (J, K, Q, V, X) are exactly where a sparse table leaves the scorer unable to tell a correct pairing from an incorrect one. It’s the same table the Autokey and simplified Enigma breakers use, for the same reason: those raw log-frequency values are also only meaningful relative to each other, not as some absolute threshold.
• The word bonus (+10 in score_key) is a tuned constant, not a derived one. It just needs to be large enough that landing on a real word reliably outweighs a run of merely plausible digrams, without being so large that one lucky word match overrides otherwise-strong digram evidence elsewhere in the message. 10 works well at the demo’s ~738-letter scale; a very different message length could call for retuning it.
• Word-bonus scoring: score_key adds a flat bonus whenever a fully decoded word matches a set of ~300 common English words. This is what breaks the ties that digram statistics alone leave ambiguous.
• Simulated annealing, not pure hill-climbing: anneal occasionally accepts a worse-scoring swap based on a cooling “temperature,” which is what lets the search escape the multi-letter local optima that a strict always-improve search gets trapped in.
• Multiple restarts: break_substitution runs the search once from the frequency-analysis guess and several more times from random keys, keeping whichever result scores best overall.

Code

# substitution_breaker.py
#
# Breaks a general monoalphabetic substitution cipher. Unlike Caesar,
# Affine, Vigenere or Beaufort, the key here is an arbitrary permutation
# of the 26 letters (26! possibilities) rather than a small numeric key
# or a short repeating keyword -- so Kasiski examination and the Index
# of Coincidence, which both rely on a *repeating* key, don't apply.
# Instead: frequency analysis for a starting guess, then a hill-climbing
# / simulated-annealing search that keeps the swap whenever it makes the
# decryption look more like real English.

import re
import math
import random

ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ENGLISH_ORDER = 'ETAOINSHRDLCUMWFGYPBVKJXQZ'

# Digram (letter-pair) frequencies, as a percentage of all within-word
# adjacent letter pairs, computed from a large public-domain English novel.
BIGRAMS = {"HE": 3.5637, "TH": 3.3246, "ER": 2.706, "IN": 2.4173, "AN": 1.9097, "RE": 1.7599, "HA": 1.5132, "EN": 1.4942, "ON": 1.4774, "OU": 1.4742, "AT": 1.3883, "ND": 1.3435, "ED": 1.2794, "TO": 1.2408, "IS": 1.1669, "IT": 1.1623, "AS": 1.1473, "NG": 1.1462, "HI": 1.0715, "TE": 1.0665, "VE": 1.0235, "AR": 0.9992, "BE": 0.9838, "OF": 0.9627, "NE": 0.9617, "OR": 0.931, "SE": 0.9101, "ST": 0.8866, "ES": 0.8682, "LE": 0.8646, "NT": 0.8177, "NO": 0.8058, "TI": 0.7947, "EL": 0.7821, "LL": 0.7803, "ME": 0.7578, "LI": 0.7559, "EA": 0.75, "CO": 0.7481, "SH": 0.699, "AL": 0.6925, "OT": 0.6475, "WA": 0.6392, "HO": 0.6282, "UR": 0.6195, "ET": 0.617, "DE": 0.6119, "WI": 0.5965, "CE": 0.5951, "LY": 0.5938, "AD": 0.5795, "WH": 0.5568, "CH": 0.5531, "IO": 0.5481, "OM": 0.5276, "FO": 0.5276, "SI": 0.5106, "RI": 0.501, "YO": 0.4978, "DI": 0.4681, "RS": 0.4594, "IL": 0.4559, "RO": 0.4546, "EE": 0.4546, "MA": 0.4532, "SS": 0.4481, "US": 0.4474, "UT": 0.4426, "SO": 0.4332, "OW": 0.4327, "WE": 0.4213, "UL": 0.4201, "PE": 0.4183, "IM": 0.4061, "EC": 0.3951, "LD": 0.3948, "NC": 0.3925, "AI": 0.3723, "RA": 0.3703, "GH": 0.3696, "TA": 0.3682, "AB": 0.368, "IC": 0.3618, "MI": 0.3602, "SU": 0.3576, "IE": 0.3565, "NS": 0.3535, "IR": 0.353, "LA": 0.3443, "UN": 0.3397, "EV": 0.3381, "CA": 0.3374, "EM": 0.3264, "GE": 0.3252, "PR": 0.325, "AV": 0.323, "SA": 0.3188, "LO": 0.3184, "RY": 0.3151, "CT": 0.3151, "ID": 0.3131, "AM": 0.3122, "MO": 0.3112, "OO": 0.3108, "RT": 0.3078, "AY": 0.286, "TT": 0.2807, "AC": 0.2729, "EY": 0.2724, "OS": 0.2708, "FE": 0.2704, "MR": 0.2669, "BU": 0.2651, "EI": 0.2522, "KE": 0.2517, "DA": 0.2501, "PO": 0.2451, "OL": 0.2446, "UC": 0.2442, "BL": 0.2439, "WO": 0.2416, "PA": 0.2364, "TR": 0.2297, "HT": 0.2281, "IG": 0.2194, "DO": 0.218, "IV": 0.2145, "PL": 0.2104, "NI": 0.2083, "VI": 0.206, "UG": 0.2051, "RD": 0.2035, "AG": 0.2017, "FI": 0.2012, "FR": 0.1994, "MY": 0.1941, "AP": 0.1927, "FA": 0.1877, "NN": 0.1867, "TY": 0.1844, "IZ": 0.1838, "TU": 0.1812, "IF": 0.1766, "EX": 0.1759, "GA": 0.1716, "MP": 0.1714, "IA": 0.1702, "MU": 0.1693, "BY": 0.1681, "TL": 0.1681, "SP": 0.1663, "PP": 0.1642, "RC": 0.1619, "EF": 0.1596, "ZA": 0.1539, "BO": 0.1537, "GR": 0.1525, "LF": 0.1498, "QU": 0.1488, "OP": 0.1477, "EP": 0.1463, "RN": 0.1413, "NY": 0.1401, "FF": 0.1397, "AK": 0.139, "NA": 0.1383, "RR": 0.1374, "GI": 0.1309, "AU": 0.1298, "GO": 0.1293, "OV": 0.1279, "OD": 0.1279, "CI": 0.1263, "TS": 0.1245, "CY": 0.1217, "KI": 0.1171, "GL": 0.1169, "RL": 0.1137, "LU": 0.1116, "KN": 0.1112, "WN": 0.1107, "AF": 0.1103, "UA": 0.1075, "UP": 0.1075, "CK": 0.1045, "BI": 0.1018, "FT": 0.1015, "PI": 0.1008, "DY": 0.0983, "RM": 0.0976, "DS": 0.0942, "UE": 0.0935, "OK": 0.0919, "NL": 0.0914, "CU": 0.088, "EW": 0.0871, "FU": 0.0861, "NK": 0.0861, "UI": 0.0859, "VA": 0.0852, "PT": 0.0838, "YE": 0.0834, "OB": 0.0827, "YS": 0.0825, "SC": 0.0806, "OI": 0.0806, "AW": 0.0795, "CR": 0.0792, "CL": 0.0783, "EG": 0.0772, "CC": 0.0769, "BR": 0.0767, "IB": 0.0724, "BA": 0.0719, "JA": 0.0714, "MS": 0.0712, "RU": 0.071, "XP": 0.0689, "HU": 0.0682, "LT": 0.0634, "UD": 0.0629, "NV": 0.0595, "TW": 0.0588, "RG": 0.0586, "MM": 0.0586, "IK": 0.0583, "UM": 0.0581, "UB": 0.057, "DR": 0.0565, "JE": 0.056, "VO": 0.0558, "LK": 0.0556, "GS": 0.0549, "LS": 0.0549, "DU": 0.0544, "NF": 0.0528, "OC": 0.0519, "RF": 0.0517, "DD": 0.0501, "RV": 0.0501, "MB": 0.0473, "JU": 0.0471, "KH": 0.0462, "YT": 0.0455, "EQ": 0.0443, "BJ": 0.0436, "PS": 0.0427, "PU": 0.0416, "IP": 0.0416, "YD": 0.0404, "NU": 0.0395, "HR": 0.0386, "YI": 0.0384, "XC": 0.0377, "BS": 0.0372, "GU": 0.037, "DL": 0.0368, "JO": 0.0361, "EH": 0.0351, "XT": 0.0351, "SL": 0.0345, "SM": 0.034, "FL": 0.0319, "SW": 0.031, "SF": 0.031, "PY": 0.031, "EO": 0.0305, "RP": 0.0301, "DG": 0.0296, "WR": 0.0296, "LW": 0.0292, "RH": 0.0289, "GN": 0.0289, "RK": 0.028, "LV": 0.0271, "BT": 0.0266, "OG": 0.0264, "PH": 0.0255, "OA": 0.0253, "KS": 0.0248, "TC": 0.0239, "SK": 0.0237, "DV": 0.0237, "ZZ": 0.0237, "OE": 0.0234, "XI": 0.023, "CQ": 0.023, "OH": 0.0227, "ZY": 0.0225, "DM": 0.0218, "TF": 0.0214, "EK": 0.0202, "WS": 0.0202, "GB": 0.0202, "HM": 0.0195, "RW": 0.0193, "LM": 0.0184, "HY": 0.0181, "TN": 0.0175, "OY": 0.0172, "XA": 0.017, "NQ": 0.017, "NJ": 0.017, "TM": 0.0163, "YB": 0.0161, "SY": 0.0156, "XE": 0.0154, "IX": 0.0154, "WL": 0.0152, "DN": 0.0149, "SB": 0.0136, "MF": 0.0136, "RB": 0.0131, "UF": 0.0126, "HB": 0.0122, "EJ": 0.0117, "HL": 0.0108, "NX": 0.0108, "LP": 0.0106, "XX": 0.0106, "ZE": 0.0106, "II": 0.0101, "YM": 0.0099, "EB": 0.0096, "FY": 0.0096, "GT": 0.0094, "KF": 0.0092, "SG": 0.009, "YR": 0.009, "TZ": 0.0085, "ZW": 0.0085, "GG": 0.0083, "NW": 0.008, "SD": 0.0078, "NH": 0.0071, "LC": 0.0071, "LR": 0.0067, "HS": 0.0064, "LN": 0.0055, "SN": 0.0055, "GY": 0.0055, "GM": 0.0053, "AZ": 0.0053, "YN": 0.0051, "LG": 0.0048, "IU": 0.0048, "MN": 0.0048, "NP": 0.0048, "YL": 0.0046, "DF": 0.0046, "DW": 0.0044, "KA": 0.0041, "KY": 0.0041, "XV": 0.0041, "EU": 0.0041, "NR": 0.0039, "KW": 0.0037, "AO": 0.0037, "ML": 0.0034, "KL": 0.0034, "WK": 0.0032, "XL": 0.0032, "CS": 0.003, "ZI": 0.0028, "NM": 0.0028, "XH": 0.0025, "HF": 0.0023, "HN": 0.0021, "BB": 0.0021, "UO": 0.0021, "HD": 0.0021, "YF": 0.0018, "MT": 0.0018, "VY": 0.0018, "OX": 0.0016, "SR": 0.0016, "BH": 0.0016, "VU": 0.0014, "HW": 0.0014, "IQ": 0.0014, "YP": 0.0014, "OQ": 0.0014, "AE": 0.0014, "AH": 0.0014, "WD": 0.0014, "SQ": 0.0011, "WF": 0.0011, "AX": 0.0011, "UY": 0.0011, "YA": 0.0011, "IH": 0.0011}
FLOOR = 0.005  # fallback frequency for any digram not in the table

COMMON_WORDS = {"THE","TO","OF","AND","HER","I","A","IN","WAS","SHE","THAT","IT","NOT","YOU","HE","HIS","BE","AS","HAD","WITH","FOR","BUT","IS","HAVE","AT","MR","HIM","ON","MY","BY","ALL","THEY","SO","WERE","WHICH","BEEN","COULD","FROM","NO","VERY","WHAT","WOULD","THIS","ME","THEIR","YOUR","THEM","WILL","SAID","SUCH","WHEN","AN","THERE","ARE","IF","MRS","DO","MUCH","MORE","AM","OR","MISS","MUST","THAN","WHO","ONE","ANY","DID","WE","SHOULD","HAS","KNOW","THOUGH","HERSELF","HOW","WELL","NEVER","BEFORE","ONLY","OTHER","THINK","CAN","SOON","SISTER","NOW","SOME","GOOD","MIGHT","MAY","AFTER","TIME","MOST","LADY","OWN","LITTLE","NOTHING","EVERY","BEING","AGAIN","WITHOUT","THEN","MAKE","DEAR","SHALL","FIRST","SAY","MAN","ROOM","FAMILY","SEE","GREAT","DAY","TOO","TWO","INTO","OUT","MOTHER","HOWEVER","EVER","FATHER","HIMSELF","YOUNG","MADE","ABOUT","GIVE","US","ALWAYS","HOPE","ITS","MANY","AWAY","LONG","LAST","LETTER","WAY","UP","FRIEND","CANNOT","THOUGHT","ENOUGH","HOUSE","GO","FELT","SURE","REPLIED","LOVE","SAW","INDEED","QUITE","BETTER","WISH","COME","MYSELF","MANNER","TILL","OVER","EVEN","PLEASURE","CAME","HAVING","DONE","WHERE","OH","FEELINGS","OFTEN","DOES","REALLY","CRIED","BELIEVE","PERHAPS","LIKE","WHOM","AUNT","SUBJECT","HEARD","DAUGHTER","TAKE","LADIES","HAPPY","ANYTHING","LESS","WHOLE","WHILE","SEEN","PLACE","ILL","DOWN","SIR","BROTHER","THESE","JUST","YET","MORNING","CERTAINLY","STILL","LET","SISTERS","SOMETHING","OUR","LOOKED","YES","THEREFORE","HERE","EVENING","SAME","BOTH","NOR","LEAST","PRESENT","WORLD","UPON","ADDED","HALF","FEW","NEXT","HAPPINESS","KIND","TOLD","MOMENT","HEAR","WENT","SPEAK","TELL","TOWARDS","ATTENTION","UNCLE","CHARACTER","BETWEEN","FOUND","TOWN","COLONEL","SEEMED","OPINION","HOME","MARRIAGE","WOMAN","LEFT","ALMOST","EACH","ANSWER","TOGETHER","THOSE","BECAUSE","THREE","LEAVE","EITHER","RATHER","ONCE","OFF","FAR","GONE","AFFECTION","OTHERS","PART","FIND","PASSED","RECEIVED","PARTY","POSSIBLE","GIVEN","ANOTHER","LOOK","WHOSE","MARRIED","EVERYTHING","COMING","LONDON","WHETHER","MEANS","SINCE","BEGAN","SEEING","LIFE","CERTAIN","KNEW","MIND","SIDE","KNOWN","GOING","PRIDE","TOOK","FRIENDS","BEHAVIOUR","GENERAL","EYES","WHY","GAVE","ABLE","PERFECTLY","AGAINST","GET","REASON","COURSE","VISIT","HUSBAND","WORD","CONTINUED","IDEA","DAUGHTERS","RETURN","PERSON","WALK","HARDLY","WIFE","COUSIN","REGARD","PEOPLE","SENSE","SUPPOSE","AGREEABLE","YOURSELF","WANT","POINT","MANNERS","SETTLED","OBJECT","BUSINESS","IMPOSSIBLE","GIRLS","BEST"}


def clean(text):
    text = re.sub(r'[^A-Za-z ]', '', text.upper())
    return re.sub(r'\s+', ' ', text).strip()


def bigram_log_freq(pair):
    return math.log(BIGRAMS.get(pair, FLOOR))


def score_key(cipher_words, key):
    score = 0.0
    for w in cipher_words:
        prev_plain = -1
        decoded = []
        for i, ch in enumerate(w):
            p = key[ord(ch) - 65]
            decoded.append(chr(p + 65))
            if i > 0:
                score += bigram_log_freq(chr(prev_plain + 65) + chr(p + 65))
            prev_plain = p
        if ''.join(decoded) in COMMON_WORDS:
            score += 10
    return score


def letter_counts(ciphertext):
    counts = [0] * 26
    for ch in ciphertext:
        if ch != ' ':
            counts[ord(ch) - 65] += 1
    return counts


def frequency_order_key(counts):
    cipher_order = sorted(range(26), key=lambda i: -counts[i])
    english_order = [ord(c) - 65 for c in ENGLISH_ORDER]
    key = [0] * 26
    for rank, ci in enumerate(cipher_order):
        key[ci] = english_order[rank]
    return key


def random_key():
    key = list(range(26))
    random.shuffle(key)
    return key


def random_swap(key):
    a, b = random.sample(range(26), 2)
    new_key = key[:]
    new_key[a], new_key[b] = new_key[b], new_key[a]
    return new_key


def decrypt_with_key(ciphertext, key):
    return ''.join(' ' if ch == ' ' else chr(key[ord(ch) - 65] + 65) for ch in ciphertext)


# Simulated annealing: like hill-climbing, but early on it will sometimes accept
# a worse-scoring swap anyway (probability shrinks as `t` cools), which is what
# lets it escape the multi-letter local optima a strict hill climb gets stuck in.
def anneal(cipher_words, start_key, steps):
    key = start_key[:]
    score = score_key(cipher_words, key)
    best_key, best_score = key[:], score
    t0, t1 = 4.0, 0.02
    for s in range(steps):
        t = t0 * (t1 / t0) ** (s / steps)
        candidate = random_swap(key)
        cand_score = score_key(cipher_words, candidate)
        delta = cand_score - score
        if delta > 0 or random.random() < math.exp(delta / t):
            key, score = candidate, cand_score
            if score > best_score:
                best_key, best_score = key[:], score
    return best_key, best_score


def break_substitution(ciphertext, restarts=4, steps=4000):
    cipher_words = ciphertext.split(' ')
    counts = letter_counts(ciphertext)
    start_key = frequency_order_key(counts)

    global_best_key = start_key[:]
    global_best_score = score_key(cipher_words, start_key)

    for r in range(restarts):
        key = start_key[:] if r == 0 else random_key()
        found_key, found_score = anneal(cipher_words, key, steps)
        if found_score > global_best_score:
            global_best_key, global_best_score = found_key, found_score

    plaintext = decrypt_with_key(ciphertext, global_best_key)
    return {'key': global_best_key, 'score': global_best_score, 'plaintext': plaintext}


if __name__ == '__main__':
    ciphertext = "HJIJFGKYFRUPAE OSROPAPSPAJI EAKYUMO MUKGFEU UFEY GUPPUM JN PYU FGKYFRUP VAPY FIJPYUM GUPPUM FEEJMQAIC PJ F NAWUQ HFKKAIC OJ PYU OFHU KGFAIPUWP GUPPUM FGVFXO RUEJHUO PYU OFHU EAKYUMPUWP GUPPUM PYMJSCYJSP PYU UIPAMU HUOOFCU PYU ISHRUM JN KJOOARGU DUXO AO PVUIPX OAW NFEPJMAFG VYAEY AO FI FOPMJIJHAEFGGX GFMCU ISHRUM NFM PJJ HFIX PJ PMX RX RMSPU NJMEU RSP PYU EAKYUM OPAGG GUFDO PYU OPFPAOPAEFG NAICUMKMAIP JN PYU SIQUMGXAIC GFICSFCU RUEFSOU GUPPUM NMULSUIEAUO VJMQ KFPPUMIO FIQ EJHHJI GUPPUM KFAMAICO OSMTATU PYU OSROPAPSPAJI SIEYFICUQ FI FPPFEDUM OPFMPO RX HFPEYAIC PYU HJOP NMULSUIP EAKYUMPUWP GUPPUMO PJ PYU HJOP NMULSUIP GUPPUMO AI UICGAOY PYUI MUNAIUO PYFP AIAPAFG CSUOO SOAIC F YAGG EGAHRAIC OUFMEY PYFP MUKUFPUQGX OVFKO PVJ GUPPUMO AI PYU EFIQAQFPU DUX FIQ DUUKO PYU OVFK VYUIUTUM AP HFDUO PYU QUEMXKPUQ PUWP GJJD HJMU GADU MUFG UICGAOY FEEJMQAIC PJ QACMFH OPFPAOPAEO"

    result = break_substitution(ciphertext)
    print('Recovered key (cipher -> plain):', ''.join(chr(k + 65) for k in result['key']))
    print(f"Best fit score: {result['score']:.2f}")
    print()
    print('Recovered plaintext:')
    print(result['plaintext'])

The script above is complete and runnable as-is: same ~390-entry digram table, ~300-word common-word list, and demo ciphertext as the JavaScript visualizer. Running it converges to the same key across all four restarts, recovers a fit score of 230.29, and decrypts to the exact same passage the visualizer above finds, letter for letter, punctuation-free cryptogram back to readable English.

For Fun: The Same Thing in ~20 Lines

Same spirit as the Caesar Cipher Breaker’s 5-line one-liner and the Vigenère Breaker’s ~20-line version. This isn’t something to learn the algorithm from; that’s what the readable version above is for. It’s just a demonstration of how much Python’s expression syntax can absorb into single lines. This compresses the same frequency-analysis-plus-simulated-annealing pipeline, same digram table, same common-word set, and the same demo ciphertext used above, down to about 20 lines by turning most of the helper functions into lambdas.

import re, math, random
ENGLISH_ORDER = 'ETAOINSHRDLCUMWFGYPBVKJXQZ'
FLOOR = 0.005
BIGRAMS = {"HE": 3.5637, "TH": 3.3246, "ER": 2.706, "IN": 2.4173, "AN": 1.9097, "RE": 1.7599, "HA": 1.5132, "EN": 1.4942, "ON": 1.4774, "OU": 1.4742, "AT": 1.3883, "ND": 1.3435, "ED": 1.2794, "TO": 1.2408, "IS": 1.1669, "IT": 1.1623, "AS": 1.1473, "NG": 1.1462, "HI": 1.0715, "TE": 1.0665, "VE": 1.0235, "AR": 0.9992, "BE": 0.9838, "OF": 0.9627, "NE": 0.9617, "OR": 0.931, "SE": 0.9101, "ST": 0.8866, "ES": 0.8682, "LE": 0.8646, "NT": 0.8177, "NO": 0.8058, "TI": 0.7947, "EL": 0.7821, "LL": 0.7803, "ME": 0.7578, "LI": 0.7559, "EA": 0.75, "CO": 0.7481, "SH": 0.699, "AL": 0.6925, "OT": 0.6475, "WA": 0.6392, "HO": 0.6282, "UR": 0.6195, "ET": 0.617, "DE": 0.6119, "WI": 0.5965, "CE": 0.5951, "LY": 0.5938, "AD": 0.5795, "WH": 0.5568, "CH": 0.5531, "IO": 0.5481, "OM": 0.5276, "FO": 0.5276, "SI": 0.5106, "RI": 0.501, "YO": 0.4978, "DI": 0.4681, "RS": 0.4594, "IL": 0.4559, "RO": 0.4546, "EE": 0.4546, "MA": 0.4532, "SS": 0.4481, "US": 0.4474, "UT": 0.4426, "SO": 0.4332, "OW": 0.4327, "WE": 0.4213, "UL": 0.4201, "PE": 0.4183, "IM": 0.4061, "EC": 0.3951, "LD": 0.3948, "NC": 0.3925, "AI": 0.3723, "RA": 0.3703, "GH": 0.3696, "TA": 0.3682, "AB": 0.368, "IC": 0.3618, "MI": 0.3602, "SU": 0.3576, "IE": 0.3565, "NS": 0.3535, "IR": 0.353, "LA": 0.3443, "UN": 0.3397, "EV": 0.3381, "CA": 0.3374, "EM": 0.3264, "GE": 0.3252, "PR": 0.325, "AV": 0.323, "SA": 0.3188, "LO": 0.3184, "RY": 0.3151, "CT": 0.3151, "ID": 0.3131, "AM": 0.3122, "MO": 0.3112, "OO": 0.3108, "RT": 0.3078, "AY": 0.286, "TT": 0.2807, "AC": 0.2729, "EY": 0.2724, "OS": 0.2708, "FE": 0.2704, "MR": 0.2669, "BU": 0.2651, "EI": 0.2522, "KE": 0.2517, "DA": 0.2501, "PO": 0.2451, "OL": 0.2446, "UC": 0.2442, "BL": 0.2439, "WO": 0.2416, "PA": 0.2364, "TR": 0.2297, "HT": 0.2281, "IG": 0.2194, "DO": 0.218, "IV": 0.2145, "PL": 0.2104, "NI": 0.2083, "VI": 0.206, "UG": 0.2051, "RD": 0.2035, "AG": 0.2017, "FI": 0.2012, "FR": 0.1994, "MY": 0.1941, "AP": 0.1927, "FA": 0.1877, "NN": 0.1867, "TY": 0.1844, "IZ": 0.1838, "TU": 0.1812, "IF": 0.1766, "EX": 0.1759, "GA": 0.1716, "MP": 0.1714, "IA": 0.1702, "MU": 0.1693, "BY": 0.1681, "TL": 0.1681, "SP": 0.1663, "PP": 0.1642, "RC": 0.1619, "EF": 0.1596, "ZA": 0.1539, "BO": 0.1537, "GR": 0.1525, "LF": 0.1498, "QU": 0.1488, "OP": 0.1477, "EP": 0.1463, "RN": 0.1413, "NY": 0.1401, "FF": 0.1397, "AK": 0.139, "NA": 0.1383, "RR": 0.1374, "GI": 0.1309, "AU": 0.1298, "GO": 0.1293, "OV": 0.1279, "OD": 0.1279, "CI": 0.1263, "TS": 0.1245, "CY": 0.1217, "KI": 0.1171, "GL": 0.1169, "RL": 0.1137, "LU": 0.1116, "KN": 0.1112, "WN": 0.1107, "AF": 0.1103, "UA": 0.1075, "UP": 0.1075, "CK": 0.1045, "BI": 0.1018, "FT": 0.1015, "PI": 0.1008, "DY": 0.0983, "RM": 0.0976, "DS": 0.0942, "UE": 0.0935, "OK": 0.0919, "NL": 0.0914, "CU": 0.088, "EW": 0.0871, "FU": 0.0861, "NK": 0.0861, "UI": 0.0859, "VA": 0.0852, "PT": 0.0838, "YE": 0.0834, "OB": 0.0827, "YS": 0.0825, "SC": 0.0806, "OI": 0.0806, "AW": 0.0795, "CR": 0.0792, "CL": 0.0783, "EG": 0.0772, "CC": 0.0769, "BR": 0.0767, "IB": 0.0724, "BA": 0.0719, "JA": 0.0714, "MS": 0.0712, "RU": 0.071, "XP": 0.0689, "HU": 0.0682, "LT": 0.0634, "UD": 0.0629, "NV": 0.0595, "TW": 0.0588, "RG": 0.0586, "MM": 0.0586, "IK": 0.0583, "UM": 0.0581, "UB": 0.057, "DR": 0.0565, "JE": 0.056, "VO": 0.0558, "LK": 0.0556, "GS": 0.0549, "LS": 0.0549, "DU": 0.0544, "NF": 0.0528, "OC": 0.0519, "RF": 0.0517, "DD": 0.0501, "RV": 0.0501, "MB": 0.0473, "JU": 0.0471, "KH": 0.0462, "YT": 0.0455, "EQ": 0.0443, "BJ": 0.0436, "PS": 0.0427, "PU": 0.0416, "IP": 0.0416, "YD": 0.0404, "NU": 0.0395, "HR": 0.0386, "YI": 0.0384, "XC": 0.0377, "BS": 0.0372, "GU": 0.037, "DL": 0.0368, "JO": 0.0361, "EH": 0.0351, "XT": 0.0351, "SL": 0.0345, "SM": 0.034, "FL": 0.0319, "SW": 0.031, "SF": 0.031, "PY": 0.031, "EO": 0.0305, "RP": 0.0301, "DG": 0.0296, "WR": 0.0296, "LW": 0.0292, "RH": 0.0289, "GN": 0.0289, "RK": 0.028, "LV": 0.0271, "BT": 0.0266, "OG": 0.0264, "PH": 0.0255, "OA": 0.0253, "KS": 0.0248, "TC": 0.0239, "SK": 0.0237, "DV": 0.0237, "ZZ": 0.0237, "OE": 0.0234, "XI": 0.023, "CQ": 0.023, "OH": 0.0227, "ZY": 0.0225, "DM": 0.0218, "TF": 0.0214, "EK": 0.0202, "WS": 0.0202, "GB": 0.0202, "HM": 0.0195, "RW": 0.0193, "LM": 0.0184, "HY": 0.0181, "TN": 0.0175, "OY": 0.0172, "XA": 0.017, "NQ": 0.017, "NJ": 0.017, "TM": 0.0163, "YB": 0.0161, "SY": 0.0156, "XE": 0.0154, "IX": 0.0154, "WL": 0.0152, "DN": 0.0149, "SB": 0.0136, "MF": 0.0136, "RB": 0.0131, "UF": 0.0126, "HB": 0.0122, "EJ": 0.0117, "HL": 0.0108, "NX": 0.0108, "LP": 0.0106, "XX": 0.0106, "ZE": 0.0106, "II": 0.0101, "YM": 0.0099, "EB": 0.0096, "FY": 0.0096, "GT": 0.0094, "KF": 0.0092, "SG": 0.009, "YR": 0.009, "TZ": 0.0085, "ZW": 0.0085, "GG": 0.0083, "NW": 0.008, "SD": 0.0078, "NH": 0.0071, "LC": 0.0071, "LR": 0.0067, "HS": 0.0064, "LN": 0.0055, "SN": 0.0055, "GY": 0.0055, "GM": 0.0053, "AZ": 0.0053, "YN": 0.0051, "LG": 0.0048, "IU": 0.0048, "MN": 0.0048, "NP": 0.0048, "YL": 0.0046, "DF": 0.0046, "DW": 0.0044, "KA": 0.0041, "KY": 0.0041, "XV": 0.0041, "EU": 0.0041, "NR": 0.0039, "KW": 0.0037, "AO": 0.0037, "ML": 0.0034, "KL": 0.0034, "WK": 0.0032, "XL": 0.0032, "CS": 0.003, "ZI": 0.0028, "NM": 0.0028, "XH": 0.0025, "HF": 0.0023, "HN": 0.0021, "BB": 0.0021, "UO": 0.0021, "HD": 0.0021, "YF": 0.0018, "MT": 0.0018, "VY": 0.0018, "OX": 0.0016, "SR": 0.0016, "BH": 0.0016, "VU": 0.0014, "HW": 0.0014, "IQ": 0.0014, "YP": 0.0014, "OQ": 0.0014, "AE": 0.0014, "AH": 0.0014, "WD": 0.0014, "SQ": 0.0011, "WF": 0.0011, "AX": 0.0011, "UY": 0.0011, "YA": 0.0011, "IH": 0.0011}
COMMON_WORDS = {"THE","TO","OF","AND","HER","I","A","IN","WAS","SHE","THAT","IT","NOT","YOU","HE","HIS","BE","AS","HAD","WITH","FOR","BUT","IS","HAVE","AT","MR","HIM","ON","MY","BY","ALL","THEY","SO","WERE","WHICH","BEEN","COULD","FROM","NO","VERY","WHAT","WOULD","THIS","ME","THEIR","YOUR","THEM","WILL","SAID","SUCH","WHEN","AN","THERE","ARE","IF","MRS","DO","MUCH","MORE","AM","OR","MISS","MUST","THAN","WHO","ONE","ANY","DID","WE","SHOULD","HAS","KNOW","THOUGH","HERSELF","HOW","WELL","NEVER","BEFORE","ONLY","OTHER","THINK","CAN","SOON","SISTER","NOW","SOME","GOOD","MIGHT","MAY","AFTER","TIME","MOST","LADY","OWN","LITTLE","NOTHING","EVERY","BEING","AGAIN","WITHOUT","THEN","MAKE","DEAR","SHALL","FIRST","SAY","MAN","ROOM","FAMILY","SEE","GREAT","DAY","TOO","TWO","INTO","OUT","MOTHER","HOWEVER","EVER","FATHER","HIMSELF","YOUNG","MADE","ABOUT","GIVE","US","ALWAYS","HOPE","ITS","MANY","AWAY","LONG","LAST","LETTER","WAY","UP","FRIEND","CANNOT","THOUGHT","ENOUGH","HOUSE","GO","FELT","SURE","REPLIED","LOVE","SAW","INDEED","QUITE","BETTER","WISH","COME","MYSELF","MANNER","TILL","OVER","EVEN","PLEASURE","CAME","HAVING","DONE","WHERE","OH","FEELINGS","OFTEN","DOES","REALLY","CRIED","BELIEVE","PERHAPS","LIKE","WHOM","AUNT","SUBJECT","HEARD","DAUGHTER","TAKE","LADIES","HAPPY","ANYTHING","LESS","WHOLE","WHILE","SEEN","PLACE","ILL","DOWN","SIR","BROTHER","THESE","JUST","YET","MORNING","CERTAINLY","STILL","LET","SISTERS","SOMETHING","OUR","LOOKED","YES","THEREFORE","HERE","EVENING","SAME","BOTH","NOR","LEAST","PRESENT","WORLD","UPON","ADDED","HALF","FEW","NEXT","HAPPINESS","KIND","TOLD","MOMENT","HEAR","WENT","SPEAK","TELL","TOWARDS","ATTENTION","UNCLE","CHARACTER","BETWEEN","FOUND","TOWN","COLONEL","SEEMED","OPINION","HOME","MARRIAGE","WOMAN","LEFT","ALMOST","EACH","ANSWER","TOGETHER","THOSE","BECAUSE","THREE","LEAVE","EITHER","RATHER","ONCE","OFF","FAR","GONE","AFFECTION","OTHERS","PART","FIND","PASSED","RECEIVED","PARTY","POSSIBLE","GIVEN","ANOTHER","LOOK","WHOSE","MARRIED","EVERYTHING","COMING","LONDON","WHETHER","MEANS","SINCE","BEGAN","SEEING","LIFE","CERTAIN","KNEW","MIND","SIDE","KNOWN","GOING","PRIDE","TOOK","FRIENDS","BEHAVIOUR","GENERAL","EYES","WHY","GAVE","ABLE","PERFECTLY","AGAINST","GET","REASON","COURSE","VISIT","HUSBAND","WORD","CONTINUED","IDEA","DAUGHTERS","RETURN","PERSON","WALK","HARDLY","WIFE","COUSIN","REGARD","PEOPLE","SENSE","SUPPOSE","AGREEABLE","YOURSELF","WANT","POINT","MANNERS","SETTLED","OBJECT","BUSINESS","IMPOSSIBLE","GIRLS","BEST"}

clean = lambda t: re.sub(r'\s+', ' ', re.sub(r'[^A-Za-z ]', '', t.upper())).strip()
bigram_log_freq = lambda p: math.log(BIGRAMS.get(p, FLOOR))
score_key = lambda cw, key: sum((lambda d: sum(bigram_log_freq(d[i-1:i+1]) for i in range(1, len(d))) + (10 if d in COMMON_WORDS else 0))(''.join(chr(key[ord(ch)-65]+65) for ch in w)) for w in cw)
letter_counts = lambda ct: [ct.count(chr(i+65)) for i in range(26)]
frequency_order_key = lambda counts: (lambda key, co, eo: ([key.__setitem__(co[r], eo[r]) for r in range(26)], key)[1])([0]*26, sorted(range(26), key=lambda i: -counts[i]), [ord(ch)-65 for ch in ENGLISH_ORDER])
random_key = lambda: random.sample(range(26), 26)
random_swap = lambda key: (lambda nk, a, b: (nk.__setitem__(a, key[b]), nk.__setitem__(b, key[a]), nk)[2])(key[:], *random.sample(range(26), 2))
decrypt_with_key = lambda ct, key: ''.join(' ' if ch == ' ' else chr(key[ord(ch)-65]+65) for ch in ct)

def anneal(cw, k, steps):
    sc = score_key(cw, k); bk, bs = k[:], sc; t0, t1 = 4.0, 0.02
    for s in range(steps):
        t = t0 * (t1/t0) ** (s/steps); cand = random_swap(k); csc = score_key(cw, cand); delta = csc - sc
        k, sc = (cand, csc) if delta > 0 or random.random() < math.exp(delta/t) else (k, sc)
        bk, bs = (k[:], sc) if sc > bs else (bk, bs)
    return bk, bs

def break_substitution(ct, restarts=4, steps=4000):
    cw = ct.split(' '); counts = letter_counts(ct); sk = frequency_order_key(counts); gbk, gbs = sk[:], score_key(cw, sk)
    for r in range(restarts):
        key = sk[:] if r == 0 else random_key(); fk, fs = anneal(cw, key, steps)
        gbk, gbs = (fk, fs) if fs > gbs else (gbk, gbs)
    return {'key': gbk, 'score': gbs, 'plaintext': decrypt_with_key(ct, gbk)}

if __name__ == '__main__':
    ct = "HJIJFGKYFRUPAE OSROPAPSPAJI EAKYUMO MUKGFEU UFEY GUPPUM JN PYU FGKYFRUP VAPY FIJPYUM GUPPUM FEEJMQAIC PJ F NAWUQ HFKKAIC OJ PYU OFHU KGFAIPUWP GUPPUM FGVFXO RUEJHUO PYU OFHU EAKYUMPUWP GUPPUM PYMJSCYJSP PYU UIPAMU HUOOFCU PYU ISHRUM JN KJOOARGU DUXO AO PVUIPX OAW NFEPJMAFG VYAEY AO FI FOPMJIJHAEFGGX GFMCU ISHRUM NFM PJJ HFIX PJ PMX RX RMSPU NJMEU RSP PYU EAKYUM OPAGG GUFDO PYU OPFPAOPAEFG NAICUMKMAIP JN PYU SIQUMGXAIC GFICSFCU RUEFSOU GUPPUM NMULSUIEAUO VJMQ KFPPUMIO FIQ EJHHJI GUPPUM KFAMAICO OSMTATU PYU OSROPAPSPAJI SIEYFICUQ FI FPPFEDUM OPFMPO RX HFPEYAIC PYU HJOP NMULSUIP EAKYUMPUWP GUPPUMO PJ PYU HJOP NMULSUIP GUPPUMO AI UICGAOY PYUI MUNAIUO PYFP AIAPAFG CSUOO SOAIC F YAGG EGAHRAIC OUFMEY PYFP MUKUFPUQGX OVFKO PVJ GUPPUMO AI PYU EFIQAQFPU DUX FIQ DUUKO PYU OVFK VYUIUTUM AP HFDUO PYU QUEMXKPUQ PUWP GJJD HJMU GADU MUFG UICGAOY FEEJMQAIC PJ QACMFH OPFPAOPAEO"
    r = break_substitution(ct)
    print('Recovered key (cipher -> plain):', ''.join(chr(k + 65) for k in r['key']))
    print(f"Best fit score: {r['score']:.2f}")
    print()
    print('Recovered plaintext:')
    print(r['plaintext'])

Same ~390-entry digram table, ~300-word common-word set, and demo ciphertext as the readable version above. The difference is clean, bigram_log_freq, score_key, letter_counts, frequency_order_key, random_key, random_swap, and decrypt_with_key collapsed into one-line lambdas, plus the tuple-swap trick ((a, b) if cond else (c, d)) standing in for the if/else blocks in the readable anneal. It’s the exact same algorithm, same annealing schedule, same restart loop, just leaning harder on Python’s expression syntax than a normal codebase ever should. Verified to produce the same recovered key and plaintext as the full version above, decrypting to the exact same passage.

Interactive Visualizer

Try it above: paste any substitution-encrypted cryptogram (word spacing preserved, punctuation stripped), or use the default. Watch all three stages run: the letter-frequency bars with their initial guesses, the hill-climbing search’s live decryption preview updating restart by restart, and the final cipher-to-plaintext key locking in one letter at a time.

Substitution vs. the Repeating-Key Ciphers

The pattern across every classic cipher on this site is the same: whatever structure makes a cipher usable by hand, a short numeric key, a repeating keyword, is exactly the structure an attacker exploits. Substitution ciphers remove the repetition, so Kasiski and the IC lose their footing entirely, but they can’t remove the fact that English itself is statistically predictable. That’s a much harder property to design away.

That head start isn’t universal, though. The Playfair breaker attacks a cipher one step removed from this one, substituting letter pairs instead of single letters, and single-letter frequency analysis gives that search almost nothing to work with: pairing the same letter with different neighbors scrambles its frequency down to nearly flat. Playfair’s search has to lean entirely on quadgram statistics and a richer set of moves instead, with no frequency-based starting guess to shrink the search space first.

FAQ

Why can’t Kasiski examination or the Index of Coincidence break a substitution cipher?

Both techniques recover a repeating key length: Kasiski by measuring distances between repeated ciphertext sequences, the IC by finding the split that makes each column’s letter distribution look most like English. A monoalphabetic substitution cipher has no repeating key; the entire message uses one fixed 26-letter mapping. There’s no length to find.

If frequency analysis alone rarely produces the exact key, why start with it?

Because it’s a nearly-free way to get most of the high-frequency letters right immediately, which gives the hill-climbing search a huge head start compared to beginning from a purely random key. It shrinks the search space the annealing process actually has to explore.

Why does the search need simulated annealing instead of just always taking whichever swap improves the score?

A pure “always improve” hill climb reliably gets trapped: a handful of rare letters (commonly among J, K, Q, V, X) end up cyclically swapped with each other in a way that scores nearly as well as the correct key. Any single swap out of that arrangement looks like a step backward. Simulated annealing tolerates occasional worse-scoring swaps, with a probability that shrinks over the course of the search, which is enough to step through that kind of dead end.

How long does the ciphertext need to be for this to work reliably?

Longer is better, since digram and word statistics need enough letters to produce a reliable signal. Texts under roughly 150 letters give the search much less to work with and are meaningfully less reliable. The visualizer’s default example runs to 738 letters (872 with spaces), comfortably in the range where this attack converges consistently.

Does removing spaces and punctuation make a substitution cipher harder to break?

It removes a very real piece of the classical, by-hand attack: word-length patterns and short common words (A, I, THE, AND) are a major part of how humans solve newspaper cryptograms. This visualizer keeps word spacing (like a traditional cryptogram) specifically because word-boundary information sharpens both the human-style attack and the word-bonus term in the automated scorer. Without spaces, digram statistics computed across the whole letter stream still work, but the search generally needs more text and more restarts to converge with the same confidence.

References

1. Wikipedia. “Substitution cipher.” Available at: https://en.wikipedia.org/wiki/Substitution_cipher

2. Jakobsen, Thomas. “A fast method for cryptanalysis of substitution ciphers.” Cryptologia, 1995.

3. Practical Cryptography. “Substitution Cipher.” Available at: http://practicalcryptography.com/ciphers/simple-substitution-cipher/

4. Singh, Simon. “The Code Book.” Doubleday, 1999.

5. Kirkpatrick, S., Gelatt, C. D., Vecchi, M. P. “Optimization by Simulated Annealing.” Science, 1983.