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

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:

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:

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

1. 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.
2. 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.
3. 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.