Vigenère Cryptanalysis in Python: From Key-Length Detection to Key Recovery

A useful Vigenère cracker is not one formula.

It is a pipeline.

The ciphertext first has to be normalized. Plausible key periods have to be generated. Each candidate period creates a different set of Caesar-like columns. Those columns have to produce a key. Harmonic periods have to be recognized. Finally, the resulting plaintext candidates need to be ranked and verified.

This article turns those stages into one standard-library Python implementation.

The program deliberately combines techniques that have already been tested separately:

average-column Index of Coincidence
→ candidate periods

chi-squared column scoring
→ candidate key for each period

tetragram language scoring
→ rank complete plaintexts

fundamental-period reduction
→ collapse repeated harmonic keys

The controlled fixture is designed to expose an important real failure mode.

The actual key is:

COMPUTER

with fundamental period:

8

Yet average-column IC ranks:

16

above:

8

The period-16 recovery is not nonsense. It returns:

COMPUTERCOMPUTER

which generates exactly the same keystream.

The final program therefore cannot simply take the highest IC peak and stop. It has to recognize that the 16-character result reduces to the eight-character fundamental key.

If you only need to encode or decode text with a known key, use the Vigenère Cipher Decoder and Encoder. This article is about recovering an unknown repeating key from ciphertext.

What this Python cracker is trying to solve

The input is assumed to be standard repeating-key Vigenère over A–Z.

The program does not know:

the key
the key length
the plaintext

It does know or assume:

the plaintext language is English
the ciphertext is long enough for statistical analysis
the candidate period lies within a chosen search range

For this worked run:

candidate periods: 2 through 20
ciphertext length: 600 letters
training text: 4,000 letters

The program searches from the ciphertext toward the key.

This article starts from ciphertext rather than teaching encryption. The ciphertext is treated as the starting evidence, and every later step is aimed at recovering and testing an unknown key.

The exact training and test data

The source material is the same verified normalized corpus used in the earlier benchmark articles, derived from Project Gutenberg eBook #11, Alice’s Adventures in Wonderland.

The complete normalized source corpus contains:

6,498 letters

SHA-256:

3070aad2cd74ac31a8a6a39c2ecc780392bbe9291904b599d41a352585b0957e

The first:

4,000 letters

form the training text.

Training SHA-256:

bf8113be5f5dccacf2009de0fa5341a421f99fa39b9a001231eb914f0f628f13

The cracking fixture uses the next:

600 letters

as held-out plaintext.

That plaintext was not included in the language-model training segment.

Plaintext SHA-256:

5d64491586e6bfd3ed9af58e98472e81476614b057c11f2c96ad6ae109a3f779

After encryption with the ground-truth key COMPUTER, the 600-letter ciphertext is:

GKMHHHXROCYTHMXFDSXDMMENCMITHMECKQQACDIKJSIXHWEEFKMHDNWKKBFXGXXFJSMGCMWRAOEXNMYIPSPPWHVEGFAWGRIRTGMCXPLZUYQGMASNNOFTCMWXGHFXHZWYGKMHWESJGPQWCGHZVKTTHLLVVIDCYWXYGQAGHXVSWHFWYKESDWFLULRFNCZVYKXFDSETYGWYGTAJHWLVTGQAZBRRNCZVFHAYCZXLBBGYYOEACMYGDMMGIPSWNOYEMAEEIWZVZKSDVVQGIHJKJSDTQXVVFCAGMTPCTCGCXMLVJOXAVNXKJSKLYKIRNZXDWDIUCBPLBXRRNWOTBTHSGSZPFEXYGKMNXHAEQBQHCWIRPRGENAIFVVQGNKCZPUQKYKCUQCDHBXARNYQSMTHCARALHMLVOWPSFXAFPRQGCGKYQKEWYPEJGJQGNHKVVCGIUZEZPGGSXXRCAGTTWTQVWDACUEMKVZQIBKIVNSSVYWXRDZQPFEQRFSAUMHPZFUXPMLXYGFQLULRFVVUCAHRZVSJRYIXRVWZNAHPUGBWTSTRUCZURYLJZTGFIBHYXJHIPMMLRVWFBCZLKDSXDHZXFQBQDZMLV

Ciphertext SHA-256:

8d319c22fcca6510fde1aa08bea801556f1731ed0f5f65d89d999ad6c1c49b29

The cracker receives the ciphertext and training text.

It does not receive the plaintext or key.

Stage 1: normalize consistently

The cryptanalytic code uses:

def normalize(text):
    return "".join(ch for ch in text.upper() if ch in ALPHABET)

That policy means:

uppercase A–Z only
spaces removed
punctuation removed
digits removed

The same normalization rule must be used for:

training data
ciphertext
scoring

A mismatch here can ruin period alignment before any statistical method gets a chance to work.

If the original cipher advanced its key over a different symbol policy, the preprocessing rule has to match that behavior.

Stage 2: rank candidate periods with average-column IC

For candidate period p, split the ciphertext into:

p

recurring columns.

Each column receives one fixed Caesar shift if p is compatible with the true repeating structure.

The program calculates ordinary IC for every column and averages the values:

def average_column_ic(ciphertext, period):
    columns = [ciphertext[offset::period] for offset in range(period)]
    return sum(index_of_coincidence(col) for col in columns) / period

The top ten scores for the 600-letter fixture are:

The true fundamental period is not the highest score.

Period 16 wins.

That is not a bug.

A multiple of the true period can also split the ciphertext without mixing incompatible key shifts.

The broader behavior of IC, Kasiski, Friedman, and autocorrelation is tested in the key-length methods comparison. The Python program needs to behave correctly even when IC produces exactly this kind of harmonic ambiguity.

Do not throw away divisors of strong periods

Suppose a strong IC peak appears at:

16

Possible explanations include:

fundamental period 16
fundamental period 8
fundamental period 4
fundamental period 2

The program therefore does not evaluate only the top raw IC values.

It takes the strongest period seeds and adds their divisors:

def divisors(period):
    return {d for d in range(2, period) if period % d == 0}

For the fixture, the strongest six raw IC candidates are:

16, 8, 12, 4, 20, 18

Their divisors add candidates such as:

2
3
5
6
8
9
10

This makes the search more resistant to the common:

multiple outranks fundamental period

problem.

It is still a heuristic.

A difficult ciphertext may require additional evidence from Kasiski or autocorrelation rather than simply widening the IC list indefinitely.

Stage 3: recover one Caesar shift per column

Once a period is being tested, every recurring column is treated as a Caesar cipher.

The training segment supplies expected English monogram frequencies.

For candidate shift s:

χ²(s)
=
Σ (Observedᵢ - Expectedᵢ)²
---------------------------
          Expectedᵢ

The smallest chi-squared score wins that column.

The code is:

def recover_key_for_period(ciphertext, period, frequencies):
    key = []

    for offset in range(period):
        column = ciphertext[offset::period]

        best_shift = min(
            range(26),
            key=lambda shift:
                chi_square_for_shift(column, shift, frequencies),
        )

        key.append(chr(A + best_shift))

    return "".join(key)

For candidate period 8, the result is:

COMPUTER

For candidate period 16:

COMPUTERCOMPUTER

Both are statistically valid descriptions of the same repeating keystream.

For wrong periods, the recovered keys look very different.

Examples include:

period 4  → VSER
period 12 → USEEVBERVOXP
period 20 → VZERUOELTTEAVXQZVIER

The key-recovery step alone does not yet tell us which candidate produces the best complete plaintext.

Why this version keeps one shift per column

The controlled chi-squared-vs-n-gram benchmark showed that on short ciphertext, retaining several chi-squared shifts per column and reranking the combinations with n-grams can recover keys that independent best-shift selection misses.

This example is intentionally different.

The ciphertext contains:

600 letters

For the true period 8, each column contains:

75 letters

That is enough for the correct Caesar shift to win every period-8 column in this controlled fixture.

So this implementation uses one best shift per column to keep the end-to-end code readable.

For much shorter ciphertext, replace this step with the top-k candidate strategy from Chi-Squared vs N-Gram Scoring.

The architecture remains the same:

period candidates
→ key candidates
→ full-text language scoring

Only the width of the key search changes.

Stage 4: decrypt each candidate and score the full text

A candidate period plus recovered key produces a complete plaintext hypothesis.

Now sequence information becomes meaningful again.

The program uses a smoothed tetragram model trained on the same 4,000-letter segment.

For every reconstructed candidate plaintext it calculates an average natural-log score:

def tetragram_score(text, log_probabilities, floor):
    grams = len(text) - NGRAM_N + 1

    total = sum(
        log_probabilities.get(
            text[i:i + NGRAM_N],
            floor
        )
        for i in range(grams)
    )

    return total / grams

Less-negative scores are better.

The detailed modeling choices—overlapping n-grams, smoothing, log probabilities, and length normalization—are explained in N-Gram Scoring for Vigenère Cryptanalysis.

Here the scorer has a narrower job:

rank the full plaintext candidates produced by the period/key pipeline

The candidate table makes the correct result obvious

After period generation, key recovery, decryption, and tetragram scoring, the strongest results are:

Two candidates are tied far above the rest:

period 8
period 16

They are tied because they decrypt to the same plaintext.

That is exactly what should happen.

Stage 5: reduce repeated recovered keys to their fundamental period

The period-16 key is:

COMPUTERCOMPUTER

Its smallest exact repeating unit is:

COMPUTER

The program detects that with:

def fundamental_key(key):
    for period in range(1, len(key) + 1):
        if len(key) % period == 0:
            unit = key[:period]

            if unit * (len(key) // period) == key:
                return unit

    return key

So:

COMPUTERCOMPUTER
→ COMPUTER

This is not cosmetic cleanup.

Without period reduction, the cracker could report a mathematically redundant harmonic as though it were a distinct key.

The useful result is the smallest repeating key that generates the recovered keystream.

The exact program

The implementation below is the same code used to produce the published output.

It uses only Python’s standard library.

from pathlib import Path
from collections import Counter
import math
import string

ALPHABET = string.ascii_uppercase
A = ord("A")
NGRAM_N = 4
SMOOTHING = 0.01


def normalize(text):
    return "".join(ch for ch in text.upper() if ch in ALPHABET)


def index_of_coincidence(text):
    n = len(text)
    if n < 2:
        return 0.0
    counts = Counter(text)
    return sum(v * (v - 1) for v in counts.values()) / (n * (n - 1))


def average_column_ic(ciphertext, period):
    columns = [ciphertext[offset::period] for offset in range(period)]
    return sum(index_of_coincidence(col) for col in columns) / period


def build_monogram_model(training_text):
    counts = Counter(training_text)
    n = len(training_text)
    frequencies = {ch: counts[ch] / n for ch in ALPHABET}
    if any(p == 0 for p in frequencies.values()):
        raise ValueError("Training text must contain every A-Z letter for this chi-squared model.")
    return frequencies


def chi_square_for_shift(column, shift, frequencies):
    decoded = [(ord(ch) - A - shift) % 26 for ch in column]
    counts = Counter(decoded)
    n = len(column)
    score = 0.0
    for i, ch in enumerate(ALPHABET):
        expected = frequencies[ch] * n
        observed = counts.get(i, 0)
        score += (observed - expected) ** 2 / expected
    return score


def recover_key_for_period(ciphertext, period, frequencies):
    key = []
    for offset in range(period):
        column = ciphertext[offset::period]
        best_shift = min(
            range(26),
            key=lambda shift: chi_square_for_shift(column, shift, frequencies),
        )
        key.append(chr(A + best_shift))
    return "".join(key)


def decrypt(ciphertext, key):
    return "".join(
        chr((ord(ch) - A - (ord(key[i % len(key)]) - A)) % 26 + A)
        for i, ch in enumerate(ciphertext)
    )


def build_tetragram_model(training_text):
    counts = Counter(
        training_text[i:i + NGRAM_N]
        for i in range(len(training_text) - NGRAM_N + 1)
    )
    total = sum(counts.values())
    vocabulary = 26 ** NGRAM_N
    denominator = total + SMOOTHING * vocabulary

    log_probabilities = {
        gram: math.log((count + SMOOTHING) / denominator)
        for gram, count in counts.items()
    }
    floor = math.log(SMOOTHING / denominator)
    return log_probabilities, floor


def tetragram_score(text, log_probabilities, floor):
    grams = len(text) - NGRAM_N + 1
    if grams <= 0:
        raise ValueError("Candidate text is too short for tetragram scoring.")
    total = sum(
        log_probabilities.get(text[i:i + NGRAM_N], floor)
        for i in range(grams)
    )
    return total / grams


def fundamental_key(key):
    """Return the shortest exact repeating unit of a recovered key."""
    for period in range(1, len(key) + 1):
        if len(key) % period == 0:
            unit = key[:period]
            if unit * (len(key) // period) == key:
                return unit
    return key


def divisors(period):
    return {d for d in range(2, period) if period % d == 0}


def crack_vigenere(ciphertext, training_text, min_period=2, max_period=20, seed_count=6):
    ciphertext = normalize(ciphertext)
    training_text = normalize(training_text)

    frequencies = build_monogram_model(training_text)
    log_probs, floor = build_tetragram_model(training_text)

    ic_scores = {
        period: average_column_ic(ciphertext, period)
        for period in range(min_period, max_period + 1)
    }

    ic_order = sorted(ic_scores, key=lambda p: (-ic_scores[p], p))
    seeds = ic_order[:seed_count]

    # High IC values often occur at multiples of the true period.
    # Include divisors of the strongest periods before key recovery.
    candidate_periods = set(seeds)
    for period in seeds:
        candidate_periods.update(
            d for d in divisors(period)
            if min_period <= d <= max_period
        )

    candidates = []
    for period in sorted(candidate_periods):
        recovered_key = recover_key_for_period(ciphertext, period, frequencies)
        plaintext = decrypt(ciphertext, recovered_key)
        reduced_key = fundamental_key(recovered_key)
        language_score = tetragram_score(plaintext, log_probs, floor)
        candidates.append({
            "period": period,
            "average_ic": ic_scores[period],
            "recovered_key": recovered_key,
            "reduced_key": reduced_key,
            "language_score": language_score,
            "plaintext": plaintext,
        })

    # Higher language score is better. If two candidates decrypt identically
    # (for example period 8 and period 16 with a repeated key), prefer the
    # shorter reduced key.
    candidates.sort(
        key=lambda row: (-row["language_score"], len(row["reduced_key"]), row["period"])
    )

    return {
        "ic_order": [(p, ic_scores[p]) for p in ic_order],
        "seeds": seeds,
        "candidates": candidates,
        "best": candidates[0],
    }


if __name__ == "__main__":
    here = Path(__file__).resolve().parent
    training = (here / "vigenere-python-training-corpus.txt").read_text(encoding="ascii")
    ciphertext = (here / "vigenere-python-example-ciphertext.txt").read_text(encoding="ascii")

    result = crack_vigenere(ciphertext, training)

    print("Top average-column IC periods:")
    for period, score in result["ic_order"][:10]:
        print(f"{period:>2}  {score:.8f}")

    print()
    print("Recovered candidates:")
    for row in result["candidates"][:10]:
        print(
            f"period={row['period']:>2} "
            f"IC={row['average_ic']:.8f} "
            f"key={row['recovered_key']} "
            f"reduced={row['reduced_key']} "
            f"score={row['language_score']:.8f}"
        )

    print()
    print("Best reduced key:", result["best"]["reduced_key"])
    print("Best candidate period:", result["best"]["period"])
    print("Plaintext preview:", result["best"]["plaintext"][:120])

The only external data dependency in the reproducible run is the training text file.

For another English corpus, replace:

vigenere-python-training-corpus.txt

with your own normalized or normalizable training text.

The ciphertext can likewise be replaced with another A–Z Vigenère sample.

Exact program output

The verified fixture produces:

Top average-column IC periods:
16  0.07313399
 8  0.06972973
12  0.05006803
 4  0.05006711
20  0.04885057
18  0.04458185
14  0.04419839
 6  0.04377104
10  0.04310734
 2  0.04245262

Recovered candidates:
period= 8 IC=0.06972973 key=COMPUTER reduced=COMPUTER score=-10.76662068
period=16 IC=0.07313399 key=COMPUTERCOMPUTER reduced=COMPUTER score=-10.76662068
period= 4 IC=0.05006711 key=VSER reduced=VSER score=-13.58364342
period=10 IC=0.04310734 key=EEUKWOKLVT reduced=EEUKWOKLVT score=-13.58710164
period=20 IC=0.04885057 key=VZERUOELTTEAVXQZVIER reduced=VZERUOELTTEAVXQZVIER score=-13.58758212
period= 6 IC=0.04377104 key=UELOCP reduced=UELOCP score=-13.60140994
period=12 IC=0.05006803 key=USEEVBERVOXP reduced=USEEVBERVOXP score=-13.62033333
period= 5 IC=0.03994398 key=EELVS reduced=EELVS score=-13.62989298
period= 9 IC=0.03973373 key=SQRZHLVEZ reduced=SQRZHLVEZ score=-13.62989298
period= 3 IC=0.03996650 key=SEL reduced=SEL score=-13.63762350

Best reduced key: COMPUTER
Best candidate period: 8
Plaintext preview: EWASNOTAMOMENTTOBELOSTAWAYWENTALICELIKETHEWINDANDWASJUSTINTIMETOHEARITSAYASITTURNEDACORNEROHMYEARSANDWHISKERSHOWLATEITSG

The final result is:

Best reduced key: COMPUTER
Best candidate period: 8

The recovered plaintext begins:

EWASNOTAMOMENTTOBELOSTAWAYWENTALICELIKETHEWINDANDWASJUSTINTIMETOHEARITSAYASITTURNEDACORNEROHMYEARSANDWHISKERSHOWLATEITSGETTINGSHEWASCLOSEBEHINDITWHENSHETURNEDTH

and matches the complete 600-letter ground truth exactly.

Why the best candidate period is 8 even though period 16 had higher IC

There are two separate rankings in the pipeline.

The first is:

period plausibility

based on average-column IC.

The second is:

complete plaintext quality

after a key has actually been recovered.

Raw IC prefers:

16

But key recovery shows:

period 16 → COMPUTERCOMPUTER
period 8  → COMPUTER

Both generate the same plaintext.

Once the recovered period-16 key is reduced to its smallest repeating unit, the distinction disappears.

The program then prefers the shorter fundamental representation:

COMPUTER
period 8

This is stronger reasoning than:

choose the biggest IC number

because it checks whether the period hypothesis leads to an actual coherent key and plaintext.

Why wrong periods can still produce plausible-looking keys

At period 4 the program recovers:

VSER

That is not evidence that VSER is a meaningful word or that the method is hallucinating a key.

For every tested period, chi-squared is forced to choose the best Caesar shift available for each column.

Even a wrong period therefore produces some key.

The question is whether those shifts collectively reconstruct plausible language.

For VSER, the tetragram score is:

-13.58364342

versus:

-10.76662068

for the correct plaintext.

The full-text language model rejects the wrong period decisively in this controlled case.

That is why period detection and key recovery should not be evaluated in isolation.

The code is intentionally modular

Each function has one job:

normalize()
→ representation

index_of_coincidence()
average_column_ic()
→ period evidence

build_monogram_model()
chi_square_for_shift()
recover_key_for_period()
→ column/key recovery

decrypt()
→ reconstruct candidate plaintext

build_tetragram_model()
tetragram_score()
→ full-text ranking

fundamental_key()
→ remove harmonic redundancy

crack_vigenere()
→ orchestrate the pipeline

That separation makes testing easier.

If the output is wrong, you can ask:

Was normalization wrong?
Did period ranking fail?
Did one column recover the wrong shift?
Did the language scorer rank candidates badly?
Was a repeated key not reduced?

A single monolithic “crack” function makes those failures much harder to diagnose.

How to validate the implementation

Do not trust a cryptanalysis program merely because one example works.

At minimum, test the components separately.

Check IC against known periods

Encrypt known plaintext with controlled keys and verify that the correct period or a harmonic family receives elevated column IC.

The earlier key-length comparison provides thousands of controlled period-detection results for this purpose.

Check Caesar recovery independently

Give one column a known Caesar shift and confirm that the chi-squared routine returns it when enough text is available.

Check decryption against fixed vectors

Known-answer fixtures are better than round-trip tests alone because two complementary bugs can sometimes cancel each other.

The site’s verified Vigenère test vectors provide fixed plaintext/key/ciphertext triples for this purpose.

Check the language scorer separately

Score known English against deliberately corrupted alternatives.

The scorer should rank the intended language higher under its documented model.

Check harmonic reduction

Verify cases such as:

DOGDOG → DOG
COMPUTERCOMPUTER → COMPUTER
ABCABCABC → ABC

and make sure non-periodic keys remain unchanged.

What this cracker deliberately does not attempt

This script is a transparent baseline, not a universal Vigenère solver.

It assumes:

standard repeating-key Vigenère
A–Z alphabet
English-like plaintext
candidate periods within 2–20
enough ciphertext for one-best-shift column recovery

It does not automatically handle:

autokey Vigenère
running-key ciphers
keyed alphabets
custom alphabets
unknown languages
very short ciphertext robustly

Those cases change the model.

The point of the program is not to hide every cryptanalytic decision behind automation.

It is to make the decisions visible and testable.

How to strengthen it for harder ciphertext

The most useful upgrades follow directly from the weaknesses of the baseline.

For short samples:

retain several chi-squared shifts per column
use beam search or combination search
rerank full keys with n-grams

For uncertain periods:

combine IC with Kasiski
inspect autocorrelation peaks
evaluate divisors and multiples explicitly

For domain-specific plaintext:

train monogram and n-gram models on representative text

For longer candidate keys:

avoid exhaustive Cartesian products
use beam search or another guided search strategy

For non-English text:

replace the English language model

The architecture stays useful because each improvement changes one stage rather than requiring a completely different cracker.

Why this pipeline works on the fixture

The 600-letter ciphertext gives the true eight-position key about:

600 / 8 = 75

letters per column.

That is enough for stable monogram recovery in this particular sample.

The period structure is strong enough that both:

8
16

rise to the top of the IC ranking.

The recovered keys then expose the relationship directly:

8  → COMPUTER
16 → COMPUTERCOMPUTER

Finally, the reconstructed English plaintext scores much better than the candidates produced by incompatible periods.

The stages reinforce one another.

That is the main lesson of the implementation.

The practical Python workflow

A useful end-to-end Vigenère cracker can therefore be organized as:

ciphertext
↓
normalize
↓
rank candidate periods
↓
add divisors of strong harmonic periods
↓
recover Caesar shift for each key position
↓
assemble candidate keys
↓
decrypt complete candidate plaintexts
↓
rank them with a language model
↓
reduce repeated keys to their fundamental period
↓
verify the winning plaintext

For the controlled fixture, that pipeline starts with a 600-letter ciphertext whose highest raw IC peak is misleading and still ends at the correct fundamental key:

COMPUTER

That is what a practical cryptanalysis script should do.

It should not merely calculate statistics.

It should connect those statistics into a sequence of falsifiable decisions until a key and plaintext survive the entire pipeline.

---

Written by Marcus Hale

Editorially reviewed by VigenereDecoder.com editorial team