Chi-Squared vs N-Gram Scoring for Vigenère: A Controlled Key-Recovery Test

Chi-squared scoring and n-gram scoring are often discussed as though they solve the same Vigenère problem.

They do not.

Chi-squared is naturally suited to the individual Caesar-shifted columns that appear after a Vigenère period is known.

N-gram scoring is naturally suited to the reconstructed full plaintext, where adjacent letters are adjacent in language again.

That difference matters most when the ciphertext is short.

A column can be too small for its correct Caesar shift to win a monogram-frequency contest outright, yet the complete key containing that shift can produce much stronger word-like and phrase-like structure once all columns are recombined.

This article measures that effect under one controlled pipeline.

Both methods learn from the same 4,000-letter training segment.

Both rank candidates drawn from the same key pool.

The evaluation text is a disjoint 2,498-letter held-out segment.

Across 146 ciphertext samples:

chi-squared exact recovery:
103 / 146 = 70.5%

tetragram reranking exact recovery:
136 / 146 = 93.2%

The n-gram method recovered the true key in every trial where the true key survived the candidate-generation stage.

That is a strong result for this benchmark.

It is not evidence that n-grams always beat chi-squared or that tetragrams can recover a key that was never included among the candidates.

If you already know the key and simply need to transform text, use the Vigenère Cipher Decoder and Encoder. This experiment is about ranking key hypotheses during cryptanalysis.

The comparison has to be designed carefully

A misleading comparison would give chi-squared one set of candidates and n-grams another.

Another misleading comparison would train the n-gram model on one corpus but use unrelated monogram frequencies for chi-squared.

This benchmark avoids both problems.

The source is the same verified 6,498-letter Alice’s Adventures in Wonderland corpus used in earlier experiments, derived from Project Gutenberg eBook #11.

It is split deterministically:

first 4,000 letters:
training data

last 2,498 letters:
held-out evaluation data

No evaluation block is part of the training segment.

The hashes are:

full 6,498-letter corpus:
3070aad2cd74ac31a8a6a39c2ecc780392bbe9291904b599d41a352585b0957e

training segment:
bf8113be5f5dccacf2009de0fa5341a421f99fa39b9a001231eb914f0f628f13

held-out segment:
f4b43d408b910f3ff858737c5f4f365c904f78afde70f4e290a9a9e7893f11a1

From the 4,000-letter training segment:

• chi-squared learns the 26 monogram frequencies;
• tetragram scoring learns the overlapping 4-gram frequencies.

So both methods see the same language sample.

The difference being tested is principally:

independent letter-frequency fit
versus
full-sequence language fit

What part of Vigenère recovery is being tested?

The true key period is supplied:

period = 5

The true key is:

ORBIT

Period detection is therefore outside the experiment.

That separation is intentional.

Kasiski, Index of Coincidence, Friedman, and autocorrelation address the earlier question of how often the key repeats. The site’s key-length methods comparison covers that stage.

This benchmark asks a later question:

Once period 5 is known, which scoring method ranks the correct five-letter key more effectively among plausible candidates?

Why one period-5 key is enough for this controlled test

The benchmark uses ORBIT rather than repeating the experiment with several arbitrary five-letter keys.

That avoids inflating the apparent sample count with mathematically redundant cases.

For standard additive Vigenère, changing a fixed key from one primitive five-letter sequence to another merely relabels the Caesar shifts in each column.

The statistical difficulty comes from:

• the plaintext sample;
• the period;
• the amount of text in each column;
• the scoring method.

Using LEMON, RIVER, or another primitive period-5 key on the same plaintext blocks would not create independent language evidence.

The 146 trials therefore correspond to 146 different held-out plaintext blocks, not the same blocks multiplied by several equivalent keys.

The tested ciphertext lengths

The 2,498-letter held-out segment is partitioned independently at each tested length:

50
75
100
150
200
300
500 letters

All lengths are multiples of 5.

That means every key column receives exactly the same number of letters within a trial.

Total:

146 ciphertext samples

Within each length, blocks are consecutive and non-overlapping.

The partition is restarted for the next length, so a 100-letter condition is a separate experiment from the 50-letter partition.

Stage 1: chi-squared produces three shifts per column

For each ciphertext, split the text into five Vigenère columns.

For one column of length N, try all 26 Caesar shifts.

After undoing candidate shift s, compare the resulting letter counts with the monogram frequencies learned from the training segment:

χ²(s)
=
Σ (Oᵢ(s) - Npᵢ)²
------------------
       Npᵢ

where:

Oᵢ(s) = observed count after candidate shift s
pᵢ    = training-corpus frequency of letter i

Smaller chi-squared is better.

Instead of keeping only the single best shift, retain the top:

3

for every key position.

With period 5, this creates:

3^5 = 243

complete candidate keys.

The same 243-key pool is then ranked in two different ways.

Method A: rank the pool by chi-squared

For a full candidate key:

k₁ k₂ k₃ k₄ k₅

its score is:

χ²_total
=
χ²₁(k₁)
+
χ²₂(k₂)
+
χ²₃(k₃)
+
χ²₄(k₄)
+
χ²₅(k₅)

Smaller is better.

Because the five terms are independent, the minimum full-key score is exactly the key formed by choosing the best chi-squared shift in every column.

This is the conventional independent-column approach.

Method B: rank the same pool by tetragram score

Every one of the same 243 keys decrypts the complete ciphertext.

The resulting plaintext is restored to its original sequence order.

A tetragram model trained on the same 4,000-letter segment then scores overlapping four-letter sequences.

The model uses:

n = 4
additive smoothing α = 0.01
natural logarithms

For tetragram g:

P(g)
=
count(g) + α
-------------------------
T + α × 26^4

and a candidate plaintext receives:

Score
=
Σ ln P(g)

divided by its number of tetragrams.

Larger—meaning less negative—is better.

The mechanics and smoothing rationale are developed in the dedicated n-gram scoring guide. Here the important point is that n-grams evaluate the reconstructed language sequence, not the isolated Vigenère columns.

Candidate-pool coverage is a separate metric

Before comparing the two ranking methods, ask whether the true key is even present in the 243-key pool.

For ORBIT to survive, every correct key letter must appear within the top three chi-squared shifts for its column.

If one true shift ranks fourth, the true key is absent.

No amount of downstream n-gram scoring can recover a candidate that was discarded before ranking.

This creates three distinct questions:

1. Did the shortlist contain the true key?

2. If yes, did chi-squared rank it first?

3. If yes, did n-gram scoring rank it first?

Keeping those questions separate prevents the candidate generator from being confused with the reranker.

Main benchmark result

The difference is concentrated in short and medium samples.

By 200 letters—40 letters per key column—both methods are perfect in this benchmark.

At 50 letters, each column has only:

10 letters

Chi-squared recovers the exact key in:

19 / 49
38.8%

while tetragram reranking recovers it in:

42 / 49
85.7%

provided the key survives the top-three shortlist.

Conditional on candidate coverage, the gap is even clearer

The true key appears in the 243-key pool in:

136 of 146 trials

Restrict the ranking comparison to those 136 cases.

Chi-squared places the true key first in:

103 / 136
75.7%

Tetragram scoring places it first in:

136 / 136
100.0%

under this benchmark.

That does not mean tetragram scoring is universally perfect.

The training and held-out data come from non-overlapping sections of the same literary work, so the language domain is closely matched.

The result demonstrates what sequence information can add when the language model fits the plaintext well.

A cross-domain test can be harder.

Why the difference is largest at short lengths

At 50 ciphertext letters, period 5 gives each chi-squared column only:

10 observations

A ten-letter sample is a weak estimate of a 26-letter frequency distribution.

The correct shift may rank:

1st
2nd
3rd

without being the column winner.

Chi-squared treats each column independently.

If three positions are slightly ambiguous, the locally best choices can combine into a globally poor plaintext.

Tetragram scoring sees the opposite structure.

Once the five positions are recombined, a 50-letter candidate contains:

47 overlapping tetragrams

Those tetragrams cross key-position boundaries.

A wrong letter in one key position disrupts local sequences around many recurring positions.

The full plaintext therefore contains information that no isolated column can see.

A 50-letter example where chi-squared ranks the true key 49th

One held-out block makes the distinction especially clear.

Plaintext:

EFOUNDHERSELFINALONGLOWHALLWHICHWASLITUPBYAROWOFLA

Encrypted with:

ORBIT

it becomes:

SWPCGRYFZLSCGQGOCPVZZFXPTZCXPBQYXILZZUCIPPBZHKFGTT

Each key column contains only ten letters.

The top three shifts in each column

The true key survives because every correct letter is somewhere in the top three.

But only positions 1, 4, and 5 have the true shift ranked first.

The independent chi-squared winner is therefore:

OYTIT

not:

ORBIT

What chi-squared’s best candidate decrypts to

Using OYTIT gives:

EYWUNDAMRSEENINAEWNGLHEHALEEHICAEASLBBUPBRIROWHNLA

That string contains some plausible fragments.

It is not pure noise.

Its summed chi-squared score is:

128.2515

The true ORBIT key has a worse chi-squared sum:

158.9095

and ranks only:

49th

among the 243 candidates.

From the perspective of five independent monogram tests, OYTIT is preferable.

Tetragram scoring reverses the ranking

Now decrypt the same 243 keys into full 50-letter plaintexts and score their local sequences.

The true key ORBIT produces:

EFOUNDHERSELFINALONGLOWHALLWHICHWASLITUPBYAROWOFLA

with tetragram score:

-11.1721 per tetragram

It ranks:

1st

The strongest n-gram competitors begin:

The sequence model recognizes something the column model cannot:

EFOUNDHERSELFINALONGLOWHALLWHICH...

contains coherent English transitions across the boundaries between Vigenère columns.

That information becomes visible only after the candidate key is assembled.

The two scorers are using different evidence

Chi-squared asks:

Does this individual column, after one Caesar shift, have roughly the expected single-letter distribution?

Tetragrams ask:

After all five shifts are combined, does the reconstructed sequence contain plausible four-letter patterns?

The distinction can be summarized as:

This is why the two methods complement one another rather than being strict substitutes.

Why not run tetragram scoring directly on each Vigenère column?

Because adjacent symbols in a Vigenère column were not adjacent in the plaintext.

For period 5, one column contains positions:

1, 6, 11, 16, ...

A tetragram extracted from that column would correspond to:

plaintext positions 1, 6, 11, 16

not:

1, 2, 3, 4

English tetragram statistics describe consecutive language sequences.

They do not describe every fifth character.

So the sensible division of labor is:

monogram statistics:
generate plausible shifts for each column

n-gram statistics:
rank the full keys after columns are recombined

The candidate shortlist still controls the ceiling

N-gram scoring cannot recover the true key if one of its letters was discarded.

In this benchmark, the true key is absent from the top-three pool in:

10 / 146 trials
6.8%

Specifically:

50 letters:
7 misses

75 letters:
2 misses

100 letters:
1 miss

150+ letters:
0 misses

Those ten trials are failures for the n-gram pipeline even though its ranking stage is strong.

This is why “n-grams recovered 93.2%” should not be interpreted as a pure n-gram success rate.

It is the success rate of:

chi-squared shortlist
+
tetragram reranking

The two stages depend on each other.

Why use three shifts per position?

Keeping more shifts increases the chance that the true key survives.

It also expands the full-key pool exponentially.

For period 5:

Moving from:

top 2 → top 3

adds:

12 recoverable trials

while increasing the pool from:

32 → 243

Moving from:

top 3 → top 5

adds only:

4 more covered trials

while increasing the pool to:

3,125

The top-three choice is therefore a benchmark design tradeoff, not a universal recommendation.

For a different key period, ciphertext length, or compute budget, another shortlist width may make more sense.

The advantage disappears as columns become statistically stable

At 200 ciphertext letters, every column contains:

40 letters

Both methods recover all:

12 / 12

held-out blocks.

The same is true at 300 and 500 letters.

At that point chi-squared already identifies every key position correctly.

There is little left for sequence scoring to rescue.

This is an important result.

The experiment does not say:

tetragrams are always better

It says:

tetragram reranking adds the most value when the column-level
frequency evidence is ambiguous.

When monogram estimates are already stable, the cheaper method can be sufficient.

That agrees with the broader sample-size behavior measured in the site’s ciphertext-length benchmark.

Computational cost is different

For period 5, chi-squared candidate generation needs:

5 columns × 26 shifts = 130 column tests

The full n-gram stage then evaluates:

243 candidate plaintexts

for every trial.

That is still trivial on modern hardware for short classical ciphertexts.

But candidate growth is exponential in the number of retained shifts and the key period.

For example:

3 candidates per position
period 5  → 3^5  = 243 keys
period 8  → 3^8  = 6,561 keys
period 12 → 3^12 = 531,441 keys

At longer periods, exhaustive recombination can become wasteful.

A practical cracker may use:

• beam search;
• hill climbing;
• branch-and-bound;
• staged candidate expansion;
• stronger pruning.

The scoring principle remains the same even when every combination is not enumerated.

Why this experiment is favorable to the n-gram model

The training and held-out segments come from different positions in the same literary work.

There is no exact training/test overlap.

But they share:

• author;
• genre;
• period;
• vocabulary style;
• punctuation-normalization conventions.

That is a well-matched language domain.

A tetragram model trained on nineteenth-century fiction may perform less cleanly on:

• software documentation;
• military abbreviations;
• scientific prose;
• names and codes;
• another language.

Chi-squared can also suffer from domain mismatch, but monogram distributions are less specific than tetragram distributions.

So the benchmark should be read as a controlled demonstration of the value of sequence information under a matched English model—not as a universal performance guarantee.

A larger n-gram corpus would change the absolute scores

The training segment contains only:

4,000 letters

That is intentionally compact and reproducible.

A production tetragram model would normally benefit from much more representative data.

With a larger corpus:

• more real tetragrams receive direct counts;
• unseen-sequence penalties become less dominant;
• domain coverage can improve;
• smoothing sensitivity can decrease.

The absolute score values would change.

The ranking may also change on difficult candidates.

That is why n-gram results are meaningful only together with the documented:

corpus
normalization
n
smoothing
log convention

Article #8 explains those modeling choices in detail rather than hiding them behind one “English score.”

Chi-squared remains valuable even when n-grams win the final ranking

It would be a mistake to read the benchmark as a reason to discard chi-squared.

Without the column scorer, the unrestricted five-letter key space is:

26^5 = 11,881,376

candidate keys.

Chi-squared reduces that to:

243

in the top-three pipeline.

That reduction is enormous.

The n-gram stage then supplies the information chi-squared lacks:

letter order across column boundaries

The strongest practical pipeline is therefore not:

chi-squared OR n-grams

It is often:

chi-squared
→ shortlist plausible column shifts
→ combine them
→ n-gram score reconstructed plaintext
→ verify the best key

The methods solve different parts of the search problem.

What this benchmark actually establishes

Under this exact setup:

source corpus:
6,498 verified normalized letters

training:
first 4,000 letters

held-out evaluation:
last 2,498 letters

cipher:
standard Vigenère

known period:
5

key:
ORBIT

tested lengths:
50, 75, 100, 150, 200, 300, 500

candidate generation:
top 3 chi-squared shifts per position

candidate pool:
243 keys per ciphertext

chi-squared ranking:
sum of five column χ² scores

n-gram ranking:
smoothed tetragram log score of full plaintext

the measured exact-key results are:

chi-squared:
103 / 146
70.5%

tetragram reranking:
136 / 146
93.2%

and, when the true key is present in the pool:

chi-squared:
103 / 136
75.7%

tetragram:
136 / 136
100.0%

Those figures are reproducible from the supplied corpus, script, and trial file.

They should not be generalized beyond the stated benchmark without additional testing.

The practical conclusion

Chi-squared and n-gram scoring should not be treated as competing versions of the same statistic.

Chi-squared is excellent at shrinking each Vigenère column from 26 possible shifts to a small shortlist.

N-gram scoring becomes powerful after those column choices are recombined into candidate plaintexts because it can evaluate the language sequence that crosses between key positions.

The controlled test shows exactly where that helps.

At 50 letters, chi-squared often identifies several plausible shifts but chooses the wrong combination.

The tetragram model can use full-text context to repair that ambiguity.

By 200 letters, the individual columns contain enough evidence that chi-squared already solves every tested sample, and the extra ranking stage adds no recovery benefit.

So the useful division of labor is:

use chi-squared to generate plausible key letters; use n-gram scoring to decide which combination produces the strongest complete plaintext when the column evidence is still ambiguous.

---

Written by Marcus Hale

Editorially reviewed by VigenereDecoder.com editorial team