DEV Community: 이준김

You don't search for the key, you search for English: how cipher auto-solvers actually work

이준김 — Fri, 21 Aug 2026 21:53:08 +0000

You've figured out which cipher you're staring at — say a monoalphabetic cryptogram, or a Vigenère — but you don't have the key. No keyword, no shift, no crib. Manually, this is where people grind for hours. Automatically, a good solver recovers it in about a second. Here's how that actually works, so the tool isn't a black box.

The whole game rests on one idea: you don't search for the key, you search for English. A wrong key produces gibberish; the right key produces text that looks like a real language. So if you can score how English-like a candidate decryption is, breaking the cipher becomes an optimization problem — find the key that maximizes the score. Everything below is a variation on that theme.

The scoring function is the secret, and single letters aren't enough

The naive score is letter frequency: real English is ~12.7% E, ~9% T, and so on, so reward decryptions whose letter distribution matches. This is too weak. A decryption that's 95% correct can score as well as or better than the true plaintext on single-letter counts alone, because shuffling a few letters barely moves the histogram. The search then happily settles on a near-miss garble and calls it done.

The fix is n-grams — scoring sequences of letters, not single ones. English is far richer in some letter-pairs and triples (TH, HE, IN, ER; THE, AND, ING) than in others (QZ, JX, VKZ). Any decoding error injects rare, low-probability pairs and triples, which a bigram or trigram score punishes hard. So the fitness function is the sum of log-probabilities of every trigram in the candidate plaintext, using a frequency table built from a large English corpus. Truth scores strictly higher than any near-miss, which is exactly what you need to climb toward.

A useful diagnostic if you ever build one of these: if your solver lands on garbage, check whether score(true plaintext) > score(found). If truth scores higher, your fitness function is fine and your search is stuck — don't tune the scorer, fix the optimizer (next section). If truth scores lower, the scorer itself is too weak (you're probably on single letters — go to trigrams).

Cracking a monoalphabetic substitution (cryptogram)

A simple substitution maps each letter to another, fixed for the whole message. There are 26! ≈ 4×10²⁶ possible alphabets — brute force is hopeless. But the scoring trick makes it tractable:

Seed with frequency analysis. Count letters in the ciphertext; map the most common cipher letter to E, the next to T, and so on. This is usually 30–60% correct — a decent starting point, not the answer. (You can do this step by hand with a frequency analysis tool.)
Improve by local search. Swap two letters in the key, re-score, keep the swap if the score went up. Repeat. This is hill-climbing — and on its own it gets stuck in local optima: a key that's better than all its neighbors but still wrong.
Escape local optima with simulated annealing. The fix is to sometimes accept a worse swap, with a probability that starts high and "cools" toward zero. Early on the search roams freely and jumps out of bad valleys; late on it behaves like pure hill-climbing and locks onto the peak. Run a few random restarts and keep the best result. This reliably recovers normal English prose.

That's precisely what the substitution cipher solver does — frequency-seeded, then simulated annealing on trigram fitness — and it recovers both the message and the full cipher alphabet with no key or crib. Paste a cryptogram and it solves in well under a second.

Cracking a Vigenère without the keyword

Vigenère uses a repeating keyword, so it's polyalphabetic — letter frequencies are smeared flat and the substitution trick above doesn't directly apply. You break it in two stages:

Find the key length. Two classic methods. Kasiski examination looks for repeated sequences in the ciphertext and measures the distances between them — those distances tend to be multiples of the key length. The Index of Coincidence approach tries each candidate length and watches for the one where the slices look like natural (peaky) English. Run both, because they fail in different ways: Kasiski needs repeats, which short or repetitive text may not supply, while the IoC needs enough letters per column to be stable. When the two agree you almost certainly have the right length; when they disagree you do not have it yet.
Solve each column independently. Once you know the key length L, every L-th letter was enciphered with the same shift — so the ciphertext splits into L columns, and each column is just a Caesar cipher. Solve each one by frequency / chi-squared against English (only 26 shifts per column), and you've recovered the keyword letter by letter.

The robust way to drive this — and what the Vigenère solver does — is to solve at every plausible key length, then rank the resulting decryptions by English fitness and present the best, rather than committing to a single length guessed from a threshold (which fails on repetitive plaintext). A monoalphabetic message naturally collapses to a one-letter key, so the same tool degrades gracefully.

When automatic solving struggles

Auto-solvers are statistical, so they need enough text to be confident:

Too short. Under ~40–50 letters there often isn't enough signal; the trigram statistics are noisy. Get more ciphertext if you can.
Not English. The fitness table is language-specific. A French or German plaintext needs a French/German n-gram model.
Homophones, nulls, or padding. Homophonic substitution (several cipher symbols per plaintext letter) and inserted null characters break the one-to-one assumption — identify and strip those first.
It's not actually a simple substitution/Vigenère. If the solver can't find anything English-like at any setting, re-check the cipher type — start again with the cipher identifier.

The two-minute version

Identify the cipher (character set, IoC, structure) — or confirm it's a cryptogram / Vigenère.
Paste it into the matching auto-solver — substitution for cryptograms, Vigenère for keyword ciphers.
Read off the plaintext and the recovered key. If it stalls, check the message length and language, and re-confirm the cipher type.

No key, no problem — the statistics of English do the work for you. All of these run entirely in your browser; nothing you paste is uploaded.

I shipped a Kasiski calculator with 21 passing tests. It got 3 of 5 key lengths wrong.

이준김 — Fri, 21 Aug 2026 21:33:46 +0000

Kasiski examination is the oldest way to break a Vigenère cipher. Find sequences
that repeat in the ciphertext, measure the gaps between them, and factor the
gaps. Because the key repeats on a fixed cycle, a repeat that comes from the
same plaintext encrypted at the same key offset sits at a distance that is a
multiple of the key length. Factor enough of those distances and the key length
should fall out.

The standard procedure, in every textbook I have read and every implementation I
have written, ends like this: tally how many distances each candidate factor
divides, and take the factor with the biggest tally.

That last step is wrong. Not subtly wrong on adversarial input — wrong on
ordinary English prose, most of the time, in a way that a unit test suite will
cheerfully certify as correct.

The tests were green and the tool was broken

My implementation had 21 unit tests. All passing. Then I ran it on five
realistic ciphertexts, enciphered with five realistic keys, and read the number
the page prints in the largest font:

True key length	What it answered
5	5 ✅
6	3 ❌
7	7 ✅
9	3 ❌
13	2 ❌

Three of five. And look at the failures: 3 divides 6, 3 divides 9, 2 divides
13... no it does not. 2 divides nothing about 13. It just wins anyway.

Why the fixtures lied

Every fixture in those 21 tests was a hand-built string, and I built each one so
that its repeat distances were clean multiples of the key length. That is what
the method is supposed to produce, so it felt like the honest thing to test.

It is not. On real text, most repeated trigrams are coincidences. THE appears
everywhere; two occurrences of THE at unrelated key offsets encipher
differently, but plenty of other short sequences collide by accident and
contribute a distance that carries no information about the key at all.

A hand-built fixture has no coincidental repeats. So it never exercises the
one thing the ranking step exists to survive.

What each factor scores for nothing

Here is the arithmetic the tally step skips.

Take a set of distances with no signal in it whatsoever — pure noise. How many
does the factor 2 divide? Half of them. How many does 3 divide? A third.
How many does 13 divide? One in thirteen.

So the raw tally is not a measurement of evidence. It is a measurement of
evidence plus a free head start that shrinks as the factor grows. Ranking
small factors against large ones on that number is like ranking sprinters
against marathoners by how long they were on the track.

The fix is to divide the head start out. Call it lift:

lift(f) = f × (distances divisible by f) / (total distances)

lift = 1.0 means "exactly what chance would give you". lift = 3.2 means
"3.2× more than chance". Now every candidate is on the same scale.

Lift fixes half of it, and creates the other half

Let D be the total number of distances and p the fraction of them that are
genuine — actual multiples of the true key length L.

For a proper divisor d of L: every genuine distance is divisible by d
(since d | L | kL), and the noise contributes 1/d of the rest.

hits/D  = p + (1−p)/d
lift(d) = d × (p + (1−p)/d) = p·d + (1−p)

Since d < L, that is strictly less than lift(L) = p·L + (1−p). Divisors
solved. Lift demotes them automatically, with no special case.

For a multiple kL: a genuine distance mL is divisible by kL only when
k | m, so roughly p/k of them survive, and the noise contributes
(1−p)/(kL).

hits/D    = p/k + (1−p)/(kL)
lift(kL)  = kL × (p/k + (1−p)/(kL)) = p·L + (1−p)

That is lift(L). Exactly. Not approximately, not usually — the multiples
of the true key length tie with the true key length on lift, forever, at every
sample size. Lift cannot break that tie, because there is nothing left in it to
break the tie with.

The tie-breaker is the noise, not the signal

The two candidates have the same expected lift. What differs is how far each is
entitled to wander on its own.

A factor f divides a random distance with probability 1/f. Over D
distances that is a binomial, and after scaling by f the standard deviation of
the lift works out to sqrt((f−1)/D). Larger factors are noisier — of course
they are; they are estimating a rarer event from the same sample.

So measure each candidate in units of its own noise:

z(f) = (lift(f) − 1) / sqrt((f − 1) / D)

Substitute the two cases:

z(L)  = p·(L−1) / sqrt((L−1)/D)  = p·sqrt((L−1)·D)
z(kL) = p·(L−1) / sqrt((kL−1)/D) < z(L)      because kL − 1 > L − 1
z(d)  = p·(d−1) / sqrt((d−1)/D)  = p·sqrt((d−1)·D) < z(L)   because d < L

z(L) is strictly the maximum. Divisors lose because their lift is smaller;
multiples lose because their noise is larger. One formula, both failure
directions, and — the part I care about most — no tuned constants. The
previous version of this code had a hand-picked threshold and a "skip obvious
artefacts" list. Both are now gone, because the arithmetic does their job.

Results

Same engine, same fixtures, sweeping every key length from 2 to 16 on ordinary
prose:

Sample size	Exact hits
~900 letters	15 / 15
~330 letters	13 / 15

The two misses at 330 letters are the long keys, which is honest: a 15-letter
key over 330 letters gives you 22 cycles, and there is genuinely not enough
evidence there. The tool now says so instead of confidently printing 2.

The one bug I would have shipped anyway

There was a second defect underneath, and it is worth naming because it is a
shape, not a fact about ciphers.

The old code ranked first, then walked the ranked list skipping artefacts. That
loop only ever demotes an artefact that appears after the real answer. So
whichever artefact happened to outrank the real answer got taken first, and the
rule that existed to catch exactly that never ran.

Reduce the field before you sort it, never during. I have now found this same
inverted-order bug in two separate tools in the same codebase.

Three things I would tell past me

Before ranking by a count, ask what each candidate scores for nothing, and divide it out. A leaderboard over quantities with different baselines is not a leaderboard.
Then ask how far that corrected figure wanders on its own, and divide that out too. Half the tie-breaks live in the variance, not the mean.
A hand-built fixture cannot test a statistic. Sweep the whole parameter range on real input. The arithmetic still deserves its unit test — just do not mistake that for a test of the statistic.

Try it

Both tools run entirely in the browser, no upload, no account:

Kasiski examination — shows the lift and the z-score for every factor, so you can see the ranking rather than trust it.
Index of coincidence calculator — the other route to key length, and a good cross-check. If Kasiski and the IC disagree, you have not found the key length yet.

Paste a Vigenère ciphertext into both. If they agree, split the text into that
many columns and each column is a plain Caesar shift, which
frequency analysis
finishes in a few seconds.