Autocorrelation for Vigenère Cipher Key-Length Detection

A repeating-key Vigenère cipher leaves a periodic trace even when no repeated word is obvious.

One way to look for that trace is to compare the ciphertext with shifted copies of itself and count how often the letters line up exactly.

If a shift realigns the same key positions, the coincidence rate can rise.

That is the basic idea behind Vigenère autocorrelation.

The calculation itself is simple. The interpretation is where most mistakes happen.

A genuine period can produce strong peaks at:

p
2p
3p
4p
...

and one of those multiples can score higher than the fundamental period.

Short ciphertext can also produce isolated accidental peaks.

So the correct question is not:

Which shift has the single highest score?

It is:

Which family of shifts is consistent with one repeating period?

This article develops that distinction carefully and uses a complete verified test vector to show why it matters.

If you want to apply a decoder to your own ciphertext, use the Vigenère Cipher Decoder and Encoder. For a broader comparison of period-finding methods, see Kasiski vs IC vs Friedman vs Autocorrelation.

What “autocorrelation” means here

In ordinary statistics and signal processing, autocorrelation can refer to several related numerical correlation measures.

For classical alphabetic cryptanalysis, a simpler categorical version is useful.

For a ciphertext:

C₁ C₂ C₃ ... Cₙ

choose a shift d and compare:

C₁ with C₁₊d
C₂ with C₂₊d
C₃ with C₃₊d
...

Count how many pairs contain the same letter.

A normalized coincidence score is:

A(d) = Σ [Cᵢ = Cᵢ₊d] / (N - d)

where:

[Cᵢ = Cᵢ₊d] = 1 when the letters match
[Cᵢ = Cᵢ₊d] = 0 otherwise

and N is the ciphertext length.

This is the same basic coincidence-at-distance idea used in academic Vigenère key-length exercises.

The score is a proportion, not a raw count.

That distinction matters because a shift of 5 compares:

N - 5

pairs, while a shift of 100 compares only:

N - 100

pairs.

Comparing raw match totals would unfairly favor smaller shifts simply because they have more opportunities to match.

Why a Vigenère period creates peaks

For standard additive Vigenère:

Cᵢ = Pᵢ + Kᵢ mod 26

Suppose the key has period p.

Then:

Kᵢ = Kᵢ₊p

and also:

Kᵢ = Kᵢ₊2p
Kᵢ = Kᵢ₊3p
...

At a shift equal to the period:

d = p

the same key shift is applied on both sides of each comparison.

So:

Cᵢ = Cᵢ₊p

exactly when:

Pᵢ = Pᵢ₊p

The key no longer interferes with the equality test.

The same is true at multiples of the period.

That means the ciphertext can recover part of the coincidence structure of the underlying language at:

p, 2p, 3p, ...

For ordinary English, repeated-letter coincidence is usually higher than the uniform-random baseline.

That is why peaks can appear.

The 1/26 baseline is useful, but it is not a proof threshold

If two independent letters were drawn uniformly from A–Z, the probability that they matched would be:

1 / 26 ≈ 0.03846

That number is a useful reference.

But a real Vigenère ciphertext is not necessarily a sequence of independent uniform letters.

The plaintext has language structure.

The key can contain repeated relationships between positions.

Finite samples fluctuate.

Certain non-period shifts can also produce elevated scores by chance.

So:

A(d) > 0.03846

does not mean:

d is the key length

Autocorrelation works better by looking for a structured sequence of related peaks than by applying one universal cutoff.

A complete 420-letter worked example

The following controlled plaintext was written specifically for this example and normalized to uppercase A–Z only.

It contains exactly:

420 letters

Plaintext:

WHENAREPEATINGVIGENEREKEYRETURNSTOTHESAMEPOSITIONTHESAMECAESARSHIFTRETURNSWITHITTHATCREATESAMEASURABLEPATTERNINTHECIPHERTEXTCOMPARETHECIPHERTEXTWITHACOPYMOVEDSEVERALPLACESTOTHERIGHTANDCOUNTHOWOFTENTHELETTERSAGREEMOSTOFFSETSMIXDIFFERENTKEYPOSITIONSBUTOFFSETSEQUALTOTHETRUEPERIODORITSMULTIPLESREALIGNTHESAMESHIFTSTHERESULTINGPEAKSAREUSEFULCLUESNOTAUTOMATICANSWERSSHORTSAMPLESCANPRODUCEACCIDENTALMATCHESANDAMULTIPLEOFTHEPER

Encrypt it with standard Vigenère using:

Key: MATRIX
Period: 6

The complete ciphertext is:

IHXEIOQPXRBFZGOZOBZEKVSBKRXKCOZSMFBEQSTDMMASBKQLZTAVAXYEVRMPMRLYQCFRXKCOZSPZBEUTMYIQORXRBBEAFVIPGRTSTBBAMKMOZIGKPBOIIYMOFEQKKLYPTIMQTEVZXEQRMVFQIIMYIZAPRDWSQDLVDBDAEGTXOELKWQTEKZOEFAGUKLGNMYWTAFMVVQTEEVBQQRLROOQEFFAQAFYJMQEMBOLFRFXIMKFKXPXLEIMZWKEBNKWCRSXKABCUTCBLFHXKZRQPXIQLPOKZBPYUEKQMXELIMXXIZEBEQSTDMPTIYKAQTEKVARXTBEOMQADJIOQULVNRXCELMPZOMRCQAMTKQZMNLNMOESAFZQEAFGTBECTEXOADNTMXOCBUMKFAEDIQOHXJIKPAFLTQUPEVWCFHXGMO

Now calculate A(d) for shifts 1 through 24.

Autocorrelation table for shifts 1–24

The four period-aligned shifts are:

6
12
18
24

Their scores are:

6  → 0.06763
12 → 0.07843
18 → 0.08458
24 → 0.08081

That is the signal we care about.

The largest peak is not the true period

The strongest score in the table is:

shift 18 → 0.08458

But the true period is:

6

A rule such as:

pick the shift with the largest autocorrelation

would therefore fail on this perfectly valid controlled example.

The reason is straightforward.

Shift 18 is:

3 × 6

so it also realigns the same positions of the six-letter repeating key.

The same is true for:

12 = 2 × 6
24 = 4 × 6

All four peaks belong to one harmonic family.

The smallest spacing that explains the family is:

6

That is the fundamental period.

Peak spacing is often more informative than peak height

Suppose the strongest peaks appear at:

12
18
24

The gaps are:

18 - 12 = 6
24 - 18 = 6

and:

gcd(12, 18, 24) = 6

That points naturally toward period 6.

This is a better interpretation than treating 12, 18, and 24 as unrelated candidate keys.

Autocorrelation is particularly useful when it reveals a regular peak spacing.

A sequence such as:

5, 10, 15, 20

suggests a five-position cycle.

A sequence such as:

7, 14, 21

suggests seven.

A sequence such as:

8, 16, 24

suggests eight.

The smallest repeated spacing is the period hypothesis to test first.

What about the elevated non-period shifts?

The table also contains values such as:

shift 5  → 0.05542
shift 10 → 0.05122
shift 22 → 0.05779

None is a multiple of 6.

Those peaks are real measurements.

They simply do not form the same coherent periodic family.

Finite English samples can create accidental alignments. Certain letter relationships can also make a non-period shift unusually favorable.

This is why an analyst should distrust a single isolated peak.

A strong Vigenère period hypothesis normally has more structure:

one plausible fundamental shift
+
support at multiples
+
compatibility with another period test
+
successful downstream key recovery

An isolated high value provides much weaker evidence.

Why shift 6 can be lower than shifts 12, 18, and 24

It may seem intuitive that the fundamental period should produce the strongest signal.

There is no mathematical requirement that it do so in a finite ciphertext.

At every aligned multiple, the equality test removes the key difference.

What remains is a different set of plaintext pairs.

For example, shift 6 compares:

P₁ with P₇
P₂ with P₈
...

Shift 18 compares:

P₁ with P₁₉
P₂ with P₂₀
...

Both are same-key-position comparisons, but they sample different relationships inside the plaintext.

By chance, the shift-18 plaintext pairs in this 420-letter passage contain more equal letters than the shift-6 pairs.

So:

A(18) > A(6)

even though 6 is the true period.

Autocorrelation detects periodic compatibility.

It does not promise that the fundamental period will always have the tallest finite-sample peak.

Written key length and fundamental period are not always the same

Suppose someone enters:

MATRIXMATRIX

as the key.

The written key length is:

12

but the generated keystream is:

MATRIXMATRIXMATRIXMATRIX...

Its fundamental period is still:

6

Autocorrelation responds to the repeating shift sequence.

It cannot infer that the user happened to type twelve characters rather than six.

So a good key-length analysis should ask:

What is the smallest period that generates the observed keystream?

not:

How many characters were present in the original key field?

This is the same distinction that matters when interpreting IC or Kasiski factors.

A practical autocorrelation procedure

A useful workflow is:

1. Normalize the ciphertext consistently.

2. Choose a candidate shift range.

3. For every shift d:
   compare C[i] with C[i+d]
   count exact matches
   divide by N-d

4. Rank or plot the normalized scores.

5. Look for families of elevated shifts.

6. Check whether strong peaks share a common spacing.

7. Test the smallest plausible fundamental period.

8. Confirm it with another period method.

9. Recover the key columns and verify the plaintext.

The important step is number 6.

A raw list of peak values is not yet an interpretation.

Choosing the shift range

There is no reason to test shifts larger than the key lengths you consider plausible.

If a ciphertext contains 120 letters and you test periods through 100, the largest shifts have very few comparisons.

For example:

N = 120
d = 100
N - d = 20 comparisons

A few accidental matches can move the normalized score dramatically.

This creates a noisy tail.

A practical maximum shift should reflect:

ciphertext length
expected key length
minimum comparisons you are willing to trust

For short ciphertext, conservative ranges are especially important.

Testing every possible shift simply because it is computationally cheap does not make every score statistically useful.

Why normalized rates are better than raw match counts

Consider a 300-letter ciphertext.

At shift 5:

295 comparisons

At shift 100:

200 comparisons

If both produced 15 matching pairs, their raw counts would be identical.

But their match rates would be:

15 / 295 ≈ 0.0508
15 / 200 = 0.0750

Those are different observations.

Raw match counts combine two things:

coincidence tendency
+
number of available comparisons

Normalizing by N-d separates them.

That is why the article uses:

matches / comparisons

throughout.

Why very short ciphertext is difficult

Suppose the ciphertext contains:

40 letters

and you test shift 12.

Only:

28 comparisons

remain.

Under a rough random baseline of 1/26, the expected number of matches is only a little above one.

The difference between:

1 match
3 matches
4 matches

can make the normalized score swing sharply.

That is not enough evidence for a universal decision rule.

Short samples therefore need more corroboration from methods such as:

• repeated-sequence spacing
• average-column IC
• a Friedman estimate
• successful key-column recovery

The site’s ciphertext-length benchmark shows the same broader principle from the later key-recovery stage: statistical methods become unstable when too little evidence is available per recurring key position.

Autocorrelation and IC are related, but they are not the same test

Both methods exploit coincidences.

But they organize the evidence differently.

Average-column IC asks:

If I split the ciphertext according to candidate period p, do the resulting streams recover language-like frequency concentration?

Autocorrelation asks:

If I shift the ciphertext by d, do unusually many symbols coincide?

IC groups positions into candidate columns.

Autocorrelation compares pairs separated by a fixed distance.

Because both respond to repeated key alignment, they can produce similar harmonic families.

But they are not interchangeable calculations.

When both point toward:

8, 16

or:

5, 10, 15

the agreement is more informative than either raw score alone.

The controlled comparison in Kasiski vs IC vs Friedman vs Autocorrelation shows how their failure modes differ across thousands of samples.

Autocorrelation does not replace Kasiski

Kasiski starts from literal repeated ciphertext sequences and examines their spacings.

Autocorrelation does not require a repeated trigram or longer fragment.

It only needs individual letter coincidences.

That means autocorrelation can produce evidence in samples where Kasiski has no useful repeated substring.

But the reverse can also happen.

A striking repeated sequence at a meaningful spacing can make Kasiski evidence much easier to interpret than a noisy autocorrelation trace.

They answer related questions using different information.

Using one does not make the other obsolete.

Long keys weaken the visible periodic pattern

If a key period is large relative to the ciphertext length, only a few multiples may fit inside the sample.

For a 70-letter ciphertext with period 24, the aligned shifts available below the message length are only:

24
48

The second one has just:

70 - 48 = 22

comparisons.

That gives the analyst little chance to see a convincing harmonic family.

By contrast, a period-5 key in the same 70-letter ciphertext can create aligned shifts at:

5
10
15
20
25
30
...

The periodic structure is much easier to observe.

This is one reason short-key Vigenère is especially vulnerable.

A non-repeating keystream changes the expectation

The autocorrelation logic depends on recurring key positions.

If the keystream does not repeat over the observed message, there may be no stable sequence:

p, 2p, 3p...

to recover.

That does not automatically make the ciphertext secure, and it does not identify a specific alternative cipher.

It simply means that short-period repeating-key Vigenère is no longer the best explanation for the missing periodic peaks.

This is an important negative result.

Autocorrelation is useful not only when it finds a pattern, but also when the pattern expected under a short repeating key fails to appear in a sufficiently long sample.

Formatting must be normalized consistently

Spaces and punctuation can create alignment mistakes if they are present in the displayed ciphertext but did not consume key positions during encryption.

Suppose the implementation encrypted letters only and left punctuation unchanged.

If the analyst computes shifts across the raw formatted string, positions after each punctuation mark may no longer correspond to the true key cycle.

For classical A–Z analysis, the safest default is usually:

extract the encrypted alphabetic symbols
normalize case
analyze that symbol stream

The rule must match the way the key advanced during encryption.

A disagreement about preprocessing can destroy an otherwise valid periodic signal.

A small algorithm is enough to reproduce the score

The core calculation can be expressed without tying it to one programming language:

for d from 1 to max_shift:
    matches = 0
    comparisons = N - d

    for i from 0 to comparisons - 1:
        if ciphertext[i] == ciphertext[i + d]:
            matches += 1

    score[d] = matches / comparisons

That is the entire autocorrelation score used in the worked example.

The difficult part is not computing the table.

It is interpreting it responsibly.

What should count as persuasive evidence?

A strong autocorrelation case looks something like:

elevated score near p

elevated scores again near 2p and 3p

consistent spacing between those peaks

no smaller period explains the same pattern better

another period test supports the same family

key recovery succeeds when the candidate period is used

A weak case looks like:

one isolated high shift

short ciphertext

no supporting multiples

no agreement from another method

no successful downstream decryption

That distinction prevents ordinary sample noise from being promoted into a confident key-length claim.

The worked example in one line

For the verified 420-letter ciphertext above, the strongest four harmonic peaks are:

6  → 0.06763
12 → 0.07843
18 → 0.08458
24 → 0.08081

The tallest peak is:

18

but the smallest period that explains the complete family is:

6

and the known ground-truth key:

MATRIX

has exactly that fundamental period.

That is the central lesson of Vigenère autocorrelation:

look for repeating peak structure, not just the largest peak.

Once a plausible period has been identified, the next task is to split the ciphertext into that many recurring columns and recover the Caesar shift used by each one. Autocorrelation helps identify the cycle; it does not recover the complete key by itself.

---

Written by Marcus Hale

Editorially reviewed by VigenereDecoder.com editorial team