kasiski-key-length

Kasiski examination that ranks candidate key lengths against chance instead of by raw divisor count. Zero dependencies, ESM, ~150 lines.

import { kasiskiAnalyse } from "kasiski-key-length";

const r = kasiskiAnalyse(ciphertext);
r.suggested;   // [5, 7]  key lengths worth trying, best first
r.factors[0];  // { factor: 5, distances: 133, grams: 73, lift: 4.1, z: 12.3 }

Why not just count divisors

The textbook procedure ends like this: tally how many repeat distances each candidate factor divides, take the biggest tally. Every implementation I have written did that, including mine.

It is wrong on ordinary text, and a unit test suite will not tell you.

My implementation had 21 passing tests. Every fixture in them was a hand-built string whose repeat distances were clean multiples of the key, because that is what the method is supposed to produce. A hand-built fixture has no coincidental repeats, so it never exercises the one thing the ranking step exists to survive. On real prose the same code answered 3 for a six-letter key, 3 for a nine-letter key, and 2 for a thirteen-letter key.

The reason is that the tallies were never comparable. Over distances with no signal in them at all, 2 divides half of them for free, 3 divides a third, 13 divides one in thirteen. The raw count measures evidence plus a head start that shrinks as the factor grows.

Two corrections, no tuned constants

1. Divide out the free share — lift

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

lift = 1.0 is exactly what an arbitrary factor scores for nothing.

Let p be the fraction of distances that are genuine multiples of the true key length L. For a proper divisor d of L, every genuine distance is divisible by d and the noise contributes 1/d of the rest:

lift(d) = d × (p + (1−p)/d) = p·d + (1−p)   <   p·L + (1−p) = lift(L)

Divisors are demoted automatically, with no special case.

2. Divide out the noise — z

For a multiple kL, a genuine distance mL is divisible only when k | m:

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

Exactly equal. Not approximately — multiples of the true key length tie with it on lift forever, at every sample size. Lift alone cannot break that.

What differs is how far each candidate is entitled to wander. A factor f divides a random distance with probability 1/f; over D distances that is a binomial whose scaled standard deviation is sqrt((f−1)/D). Larger factors are noisier because they are estimating a rarer event from the same sample. So:

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

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

z(L) is strictly the maximum. Divisors lose on lift, multiples lose on noise, one formula covers both, and no hand-picked threshold or artefact list is needed — the previous version of this code had both and they are gone.

The ordering bug underneath

The old code ranked first, then walked the ranked list skipping artefacts. That only ever demotes an artefact appearing after the real answer, so whichever artefact outranked it was taken first and the rule never ran.

Reduce the field before you sort it, never during. suggestFromFactors filters, then sorts.

Measured

Sweeping every key length 2–16 over the same English prose, asserting the exact answer (npm test reproduces all of it):

| Sample | Exact | | --- | --- | | 330 letters | 12 / 15 | | 698 letters | 15 / 15 | | 1,396 letters | 15 / 15 |

The three misses at 330 letters are 5→15, 7→14 and 10→20: every one a multiple of the true length, never a divisor. That is the residue of the tie above, where 330 letters leaves the noise term too little resolution. It is also the benign direction to fail in — splitting into 15 columns still recovers a 5-letter key, with a third of the data per column. A divisor would be flatly wrong, and does not occur at any length measured. The test asserts that direction, not just the count.

API

| Export | | | --- | --- | | kasiskiAnalyse(text, opts?) | full report: letterCount, gram, totalDistances, repeats, factors, suggested | | suggestFromFactors(factors, limit?) | the filter-then-rank step on its own | | nullZ(factor, hits, total) | the score, if you want to rank something else with it | | lettersOf(text) | A–Z upper-casing filter | | MIN_Z | the two-sigma bar a factor must clear to be offered |

opts: gram (2–8, default 3), maxFactor (default 20), suggestLimit (default 5).

Related

The same engine, with the per-factor lift and z shown in a UI, runs at textmachine.org/en/text-tools/kasiski-examination. Kasiski needs repeats, so it is worth cross-checking against an index of coincidence calculator, which needs letters per column instead and therefore fails in a different direction. When the two agree you almost certainly have the length; when they disagree you do not have it yet.

Longer write-up of how the bug was found: I shipped a Kasiski calculator with 21 passing tests.

License

MIT