N-Gram Scoring for Vigenère Cryptanalysis: Ranking Candidate Plaintexts

A Vigenère cracker often reaches a stage where the hard question is no longer:

Can I produce a decryption?

It is:

Which of several plausible decryptions looks most like real language?

That is a ranking problem.

A candidate key can be almost correct and still produce text with many recognizable fragments. A different candidate may have ordinary-looking letter frequencies but impossible local sequences. Human readers can often tell the difference quickly, but a program needs a numerical scoring rule.

N-gram scoring provides one.

Instead of judging letters independently, an n-gram model scores short consecutive sequences such as:

TH
HE
ING
TION
THER

A candidate plaintext containing many sequences that are common in the target language receives a better score than one dominated by unlikely combinations.

This article builds that idea from first principles and then tests it on a controlled Vigenère example. The worked scorer uses tetragrams, a verified training corpus, explicit add-0.01 smoothing, and natural-log probabilities. The correct key is tested against every possible one-letter mutation of the five-letter key ORBIT.

The result is clean:

correct key: ORBIT
score per tetragram: -11.9427

best of 125 one-letter wrong keys: ORBRT
score per tetragram: -12.9459

The correct plaintext ranks first.

If you already know a key and only need to transform text, use the Vigenère Cipher Decoder and Encoder. N-gram scoring becomes useful when cryptanalysis has produced multiple candidate keys or plaintexts that need to be ranked.

What an n-gram is

An n-gram is a consecutive sequence of n symbols.

For normalized text:

THERAIN

the bigrams are:

TH
HE
ER
RA
AI
IN

The trigrams are:

THE
HER
ERA
RAI
AIN

The tetragrams are:

THER
HERA
ERAI
RAIN

The sequences overlap.

That matters because every new character participates in several local contexts.

A single letter tells us very little about whether a string is English.

A sequence such as:

TION

contains much more information.

So does a sequence such as:

QZXJ

for the opposite reason.

N-gram scoring converts those local language patterns into a numerical fitness measure.

Why sequence information helps after Vigenère decryption

Once a Vigenère key hypothesis is applied, the result is a complete candidate plaintext.

At that point, the order of letters matters again.

Consider two normalized strings with broadly similar individual-letter frequencies:

THEMORNINGTRAINMOVED

and:

THEDORNIEGTRAZNMOVV

The second string contains many ordinary letters. It even preserves visible fragments such as:

THE
MOV

But its local sequences deteriorate quickly.

An n-gram model can penalize:

DORN
RNIE
TRAZ
AZNM

without requiring a dictionary lookup or spaces.

That is exactly the kind of distinction needed when Vigenère search produces near-correct keys.

The model needs a training corpus

An n-gram scorer cannot know which sequences are common until frequencies have been learned from reference text.

For this controlled example, the training data is the same previously verified 6,498-letter Alice’s Adventures in Wonderland corpus derived from Project Gutenberg eBook #11.

The normalized training corpus has:

length: 6,498 letters
SHA-256:
3070aad2cd74ac31a8a6a39c2ecc780392bbe9291904b599d41a352585b0957e

For tetragrams, a string of 6,498 letters contains:

6,498 - 4 + 1 = 6,495

overlapping training observations.

This compact corpus contains:

3,738 distinct tetragrams

out of the theoretical A–Z tetragram space:

26^4 = 456,976

That sparsity is deliberate for the worked example because it makes the need for smoothing impossible to ignore.

It is not a recommendation to train a production English scorer on only 6,498 letters.

A stronger practical model should normally use a much larger, representative corpus. The small model here is chosen because the entire experiment can be reproduced exactly and the evaluation text is separate from the training text.

Training and evaluation text must stay separate

The candidate plaintext used below was written specifically for this experiment.

It is not copied from the training corpus.

After A–Z normalization, it contains:

367 letters

Plaintext:

THEMORNINGTRAINMOVEDSLOWLYACROSSTHEVALLEYWHILETHEPASSENGERSWATCHEDLOWCLOUDSLIFTFROMTHEFIELDSATTHENEXTSTATIONAYOUNGTEACHEROPENEDAWORNNOTEBOOKANDREVIEWEDAPAGEOFCAREFULNOTESSHEHADPROMISEDHERCLASSACLEARLESSONSOEVERYEXAMPLEHADTOBESIMPLEENOUGHTOFOLLOWANDPRECISEENOUGHTOCHECKBYNOONTHERAINHADSTOPPEDSUNLIGHTREACHEDTHEWINDOWSANDTHEQUIETJOURNEYFELTMUCHSHORTERTHANANYONEEXPECTED

Key:

ORBIT

The ciphertext is:

HYFUHFEJVZHIBQGAFWMWGCPEEMRDZHGJUPXJRMTXMNIQESKIMIOJTMGUVSAPOKDPXRCPEVZFVLLZZGBYFFNBASWJMERJBBMVVOMQHJUIMWFOIRCLOOMSRDPXFFQMGSUBEHFEOWMSSPWDOEEZXJZFEXRRQIZSFGKTFVGCEBFUMLGYFPTRGSWFWJFLASIDTTGJBKESRSTXGJPVLCVWMKMVYIFDCFPTRKPJXGZNXESVOWNUYUWYCCMWPOEEXKSTJAXSEPCZVKPKASTLJRBFPVMVVSIBBYBLLHFQXXRJVVEWXIBKSRDPXRKIMPWEEWPGROLMVVRCBSKKWNFEFGYSCUUNQYTPHFKFZMVROIGMFOMXLGFKMSU

Keeping evaluation text outside the training corpus matters.

If the scorer were evaluated on passages it had already memorized as exact n-grams, the experiment could exaggerate how well it generalizes to new ciphertext.

This controlled example asks a fairer question:

Does a small tetragram model trained on one body of English rank a new English plaintext above nearby wrong decryptions?

From counts to probabilities

Let c(g) be the number of times tetragram g appears in the training corpus.

A simple unsmoothed maximum-likelihood probability would be:

P(g) = c(g) / T

where:

T = 6,495

is the total number of training tetragrams.

That immediately creates a problem.

Most possible tetragrams never appear in this small corpus.

For an unseen tetragram:

c(g) = 0

so:

P(g) = 0

If candidate likelihoods are multiplied, one unseen tetragram would force the entire candidate probability to zero.

That is too brittle.

Smoothing prevents unseen n-grams from becoming impossible

The worked scorer uses simple additive smoothing with:

α = 0.01

For every possible tetragram:

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

In this model:

T = 6,495
α = 0.01
26^4 = 456,976

So even a tetragram absent from the training corpus receives a small nonzero probability.

This is not the only smoothing method.

It is used here because its behavior is explicit and easy to reproduce.

The important rule is broader:

a scorer must define what happens to unseen n-grams.

Otherwise results can depend on accidental implementation details such as missing dictionary entries or arbitrary floor values.

Why scores are added in log space

Suppose a candidate plaintext contains tetragrams:

g₁, g₂, g₃, ... gₘ

A simple n-gram model assigns a sequence score proportional to:

P(g₁) × P(g₂) × P(g₃) × ... × P(gₘ)

These probabilities are small.

Multiplying hundreds of them quickly produces numbers so tiny that ordinary floating-point arithmetic becomes inconvenient.

Take logarithms instead:

Score
=
Σ ln P(gᵢ)

Multiplication becomes addition.

The ranking does not change because logarithm is monotonic:

higher probability
↔
less-negative log score

So in this article:

-11.94 per tetragram

is better than:

-12.95 per tetragram

Less negative is better.

Why normalize by the number of n-grams

A 100-letter candidate has fewer tetragrams than a 500-letter candidate.

Its raw summed log score therefore contains fewer negative terms.

Raw scores should not be compared casually across different text lengths.

For a text of length L using tetragrams:

number of tetragrams = L - 3

The normalized score used here is:

score per tetragram
=
total log score
-----------------
     L - 3

For candidates of identical length, raw score and normalized score produce the same ranking.

The normalization becomes important when candidate texts have different lengths or when benchmark results are compared across samples.

Absolute values still depend on:

training corpus
n
smoothing
alphabet
normalization

A score of -12 under one model should not be treated as equivalent to -12 under another.

Controlled test: all 125 one-letter mutations of ORBIT

The true key is:

ORBIT

There are five key positions.

At each position, the correct letter can be replaced by any of the other 25 letters.

So the complete set of one-letter wrong keys contains:

5 × 25 = 125

candidates.

Examples include:

ARBIT
ORBJT
ORBIU
PRBIT
ORBST

Every candidate:

1. decrypts the same ciphertext;
2. produces a 367-letter candidate plaintext;
3. receives a tetragram log score under the exact same model.

This is a deliberately difficult local test.

Every wrong key is only one letter away from the truth.

Because the five-letter key repeats, changing one key letter corrupts approximately one fifth of the plaintext positions rather than destroying every character.

The candidates can therefore retain many readable fragments.

Result: the correct key ranks first

The correct plaintext contains:

364 tetragrams

Its score is:

total log score: -4347.1469
score per tetragram: -11.9427

Among all 125 one-letter mutations, the strongest wrong candidate is:

ORBRT

with:

total log score: -4712.3188
score per tetragram: -12.9459

The median wrong candidate scores:

-13.2154 per tetragram

The worst one-letter mutation is:

QRBIT

at:

-13.4888 per tetragram

Summary:

The correct key beats every one-letter mutation.

The gap from the correct score to the best wrong score is:

1.0032

log-score units per tetragram.

That is a strong separation in this experiment.

It should not be converted into a universal confidence threshold.

The ten strongest wrong keys

The nearest competitors are:

The ordering is not simply:

one wrong letter = one fixed penalty

Changing different key positions disrupts different recurring plaintext positions.

Those positions participate in different tetragrams.

So some one-letter mutations damage the language pattern more severely than others.

This is exactly why sequence scoring is useful: it evaluates the consequence of the key error in its textual context.

What the best wrong candidate looks like

The first 120 letters under the correct key are:

THEMORNINGTRAINMOVEDSLOWLYACROSSTHEVALLEYWHILETHEPASSENGERSWATCHEDLOWCLOUDSLIFTFROMTHEFIELDSATTHENEXTSTATIONAYOUNGTEACHE

Under the strongest one-letter wrong key, ORBRT, they become:

THEDORNIEGTRAZNMOVVDSLONLYACIOSSTYEVALCEYWHZLETHVPASSVNGERJWATCYEDLONCLOUUSLIFKFROMKHEFIVLDSAKTHENVXTSTRTIONRYOUNXTEACYE

The wrong plaintext is not uniformly random.

It preserves many correct characters because four of the five key positions remain correct.

A human can still glimpse pieces such as:

THE
TRAIN
MOVE
FIELD

depending on where the corrupted positions fall.

But its local sequence structure is much worse.

That is what the tetragram score captures.

Smoothing is doing real work in this example

The small training corpus does not contain most tetragrams found in the new plaintext.

For the correct 367-letter candidate:

total tetragrams: 364
seen in training corpus: 133
unseen in training corpus: 231

For the best wrong candidate:

total tetragrams: 364
seen in training corpus: 68
unseen in training corpus: 296

So even the correct English plaintext contains:

231

tetragrams the model never observed during training.

Without smoothing, those legitimate unseen sequences would make a product-based candidate likelihood collapse to zero.

With smoothing, unseen grams are penalized rather than declared impossible.

The correct text still wins because it contains substantially more sequences that the model recognizes and assigns stronger probabilities.

A score is a ranking signal, not a calibrated probability of correctness

Suppose candidate A scores:

-11.9

per tetragram and candidate B scores:

-13.0

It is reasonable to say:

A fits this language model better than B

It is not automatically valid to say:

A has a 97% chance of being the correct plaintext

That would require a probabilistic model over:

• candidate keys;
• plaintext priors;
• search procedure;
• model misspecification;
• competing languages or domains.

N-gram fitness is normally used as an objective function.

Higher-scoring candidates are investigated first.

The raw score difference is not, by itself, a calibrated posterior confidence.

N-gram scoring does not discover the Vigenère period

This article begins after candidate plaintexts already exist.

That boundary matters.

A period-finding method such as Kasiski, average-column IC, Friedman, or autocorrelation answers a different question:

How often does the key repeat?

An n-gram scorer answers:

Given a candidate decryption, how language-like is the resulting sequence?

The previous key-length methods comparison covers the first problem.

The Mutual Index of Coincidence guide shows another way to recover relative key shifts once the period is known.

N-gram scoring becomes especially valuable after those stages produce multiple plausible key candidates.

Where n-gram scoring fits in a key search

Suppose the period is 8 and independent column analysis produces three plausible shifts for each key position.

A naive combination gives:

3^8 = 6,561

full candidate keys.

That is small enough to enumerate.

For each candidate:

decrypt the ciphertext
calculate its n-gram score
rank by score

The best-scoring plaintexts rise to the top.

For larger candidate spaces, the same score can guide:

• beam search;
• hill climbing;
• simulated annealing;
• genetic search;
• branch-and-bound heuristics.

The search algorithm proposes candidates.

The n-gram model tells the search which direction appears more language-like.

Those are separate jobs.

Why scoring the reconstructed plaintext is different from scoring Vigenère columns

A Vigenère column contains every mth plaintext letter.

Those letters were adjacent in the column after splitting, but they were not adjacent in the original language.

If the period is 5, one column contains positions:

1, 6, 11, 16, ...

A tetragram built directly from four adjacent symbols in that column corresponds to plaintext positions:

1, 6, 11, 16

not four consecutive letters.

English tetragram statistics are therefore inappropriate for ordinary per-column Caesar recovery.

Sequence n-grams become meaningful after candidate key letters are recombined into the original plaintext order.

This is an easy implementation mistake.

Use position-independent letter statistics for isolated Vigenère columns.

Use sequence n-grams for the reconstructed candidate plaintext.

Choosing bigrams, trigrams, tetragrams, or longer models

Larger n captures more context.

But it also creates a much larger possible vocabulary.

For an A–Z alphabet:

bigrams:    26^2 = 676
trigrams:   26^3 = 17,576
tetragrams: 26^4 = 456,976
5-grams:    26^5 = 11,881,376

As n increases:

• useful context increases;
• training-data requirements increase;
• unseen n-grams become more common;
• smoothing choices matter more.

A bigram model can be robust with modest data but may accept too many poor strings.

A tetragram model is more discriminating but needs more corpus coverage.

A 5-gram model trained on only a few thousand letters would be extremely sparse.

There is no universally best n.

The model should match the amount and type of training data available.

Corpus choice can change the ranking

An English model trained mostly on nineteenth-century fiction will not assign exactly the same probabilities as one trained on:

• modern news;
• scientific prose;
• chat messages;
• source code;
• military abbreviations.

The underlying language may still be English, but local sequence frequencies differ.

A candidate plaintext containing many specialized terms can receive a worse score than expected under a mismatched corpus.

That means a low score can indicate either:

wrong decryption

or:

correct decryption evaluated under a poor language model

The distinction matters especially for short ciphertexts.

A cryptanalysis system should know what its language model was trained on.

Short candidates are harder to rank

A long candidate supplies hundreds or thousands of overlapping n-grams.

A short one may contain only a handful.

For a 12-letter text:

12 - 4 + 1 = 9 tetragrams

One unusual word can dominate most of the score.

A longer passage averages over far more local patterns.

This is why n-gram ranking should be treated cautiously on very short ciphertexts.

A high score gap on nine tetragrams does not have the same evidential stability as the same average gap across nine hundred.

Length normalization makes scores numerically comparable; it does not create missing evidence.

Spaces can help—but only if the model was trained with them

The worked model uses:

A–Z only

Spaces and punctuation are removed.

That makes it compatible with classical ciphertext where word boundaries may be unavailable.

Another model could include spaces as symbols.

Then sequences such as:

THE_
_OF_
ING_

can provide powerful word-boundary evidence.

But the alphabet, training data, and candidate normalization must agree.

A scorer trained with spaces cannot be applied correctly to text that has had spaces removed unless the model is redesigned for that representation.

Consistency matters more than one preferred formatting choice.

Common scoring mistakes

Several implementation errors can produce convincing-looking but unreliable rankings.

Using zero probability for unseen n-grams

One missing tetragram should not automatically invalidate an otherwise excellent plaintext.

Use a documented smoothing rule.

Comparing raw totals across different lengths

Longer texts naturally accumulate more negative log terms.

Normalize when length differs.

Training on the answer

If the evaluation plaintext is included in the training corpus, the model may reward exact sequences it has already seen.

Keep test material separate when evaluating scorer quality.

Scoring interleaved Vigenère columns as ordinary language

Column-adjacent characters are not plaintext-adjacent.

Reconstruct the full candidate before applying sequence n-grams.

Treating the score as a probability that the key is correct

The fitness score ranks candidates under one language model.

It is not automatically a calibrated confidence percentage.

Hiding the corpus and smoothing rule

An n-gram number is not reproducible unless the scorer documents:

training corpus
normalization
n
counts
smoothing
log base
length normalization

Without those choices, two implementations can assign different absolute scores to the same text while both being internally consistent.

A reproducible scoring workflow

For Vigenère cryptanalysis, a clean implementation can follow this sequence:

1. Normalize a representative training corpus.

2. Count all overlapping n-grams.

3. Define a smoothing rule for unseen grams.

4. Convert counts into probabilities.

5. Store log probabilities.

6. Generate a candidate Vigenère key.

7. Decrypt the complete ciphertext.

8. Reconstruct plaintext order.

9. Extract overlapping n-grams from the candidate.

10. Sum their log probabilities.

11. Normalize by the number of n-grams when lengths differ.

12. Rank candidates from highest score to lowest.

13. Verify the best candidates by actual readable plaintext
    and encryption/decryption consistency.

The score should accelerate verification, not replace it.

What this controlled example actually proves

The experiment has a deliberately narrow claim.

Under:

training corpus:
6,498 normalized letters from the verified Alice corpus

model:
tetragrams

smoothing:
add-0.01

evaluation:
367 previously unseen normalized letters

cipher:
standard repeating-key Vigenère

true key:
ORBIT

competitors:
all 125 possible keys differing from ORBIT in exactly one position

the true key ranks above every competitor.

That is a reproducible result.

It does not prove that:

• tetragrams always recover Vigenère keys;
• this small corpus is sufficient for every English ciphertext;
• a fixed score threshold separates correct from incorrect plaintext;
• n-gram scoring replaces period detection;
• the highest-scoring candidate from an unrestricted search is guaranteed correct.

Those would be much broader claims than the experiment supports.

Why n-gram scoring is useful

Classical Vigenère cryptanalysis often produces uncertainty.

A period test can leave several harmonic candidates.

Column analysis can leave multiple plausible shifts.

A search algorithm can generate hundreds or thousands of possible full keys.

At that point, eyeballing every plaintext does not scale.

N-gram scoring supplies a reproducible ranking rule based on the order of letters in the reconstructed candidate.

That is its real value.

It turns:

these keys all look possible

into:

test the candidates whose plaintext has the strongest language structure first

In the controlled example here, even the strongest one-letter wrong key leaves many readable fragments. The tetragram model still separates it clearly from the correct text.

That is the role n-gram scoring plays in Vigenère cryptanalysis:

not finding the period, not proving the key, but ranking candidate plaintexts so the most language-like decryptions rise to the top for verification.

---

Written by Marcus Hale

Editorially reviewed by VigenereDecoder.com editorial team