Mutual Index of Coincidence for Vigenère Key Recovery

Once the Vigenère key period is known, the ciphertext stops behaving like one complicated polyalphabetic stream.

It can be split into columns.

Each column was encrypted by one fixed Caesar shift.

The usual next step is to compare each column directly with expected English frequencies. Mutual Index of Coincidence offers another route: compare the columns with one another and ask how far one distribution must be shifted before it lines up with another.

That distinction is important.

Ordinary Index of Coincidence can help answer:

Is this candidate period plausible?

Mutual Index of Coincidence can help answer:

If the period is already known, what is the shift difference between two key positions?

That lets us recover the relative shape of the key before we know any absolute key letter.

In the controlled example below, the period is known to be 5. Mutual IC correctly recovers the relative shifts:

0, 3, 13, 20, 5

Those five relationships reduce the unknown key from:

26^5 = 11,881,376

possible five-letter keys to only:

26

possible absolute anchors.

A final English-frequency comparison selects the anchor O and reconstructs:

ORBIT

If you already have a key and simply want to encrypt or decrypt text, use the Vigenère Cipher Decoder and Encoder. This article is about recovering key relationships from ciphertext after the period has been established.

Mutual IC is not ordinary IC with a different name

The ordinary Index of Coincidence works inside one string.

If a column has letter counts:

f₀, f₁, ... f₂₅

and length N, its IC is:

IC = Σ fᵢ(fᵢ - 1) / N(N - 1)

That estimates the probability that two letters drawn from the same sample are equal.

Mutual Index of Coincidence compares two different samples.

Let column A have counts:

F_A(0), F_A(1), ... F_A(25)

and column B have counts:

F_B(0), F_B(1), ... F_B(25)

with lengths n_A and n_B.

For candidate relative shift g, define:

MIC_g(A,B)
=
Σ F_A(x) F_B(x+g mod 26)
--------------------------
          n_A n_B

Equivalently, using normalized frequency vectors:

MIC_g(A,B) = Σ p_A(x) p_B(x+g mod 26)

The two forms are mathematically identical.

The goal is to try:

g = 0, 1, 2, ... 25

and look for the shift that makes the two frequency distributions line up best.

University cryptography notes describe the same use of Mutual Index of Coincidence: once the Vigenère period is known, it can be used to recover relative shifts between key positions, after which only an absolute offset remains to be determined.

Why relative shifts appear

Suppose two ciphertext columns were encrypted with key shifts:

k_A
k_B

For standard additive Vigenère:

C = P + K mod 26

the ciphertext distribution in column A is approximately the plaintext-language distribution shifted by k_A.

Column B is approximately the same underlying language distribution shifted by k_B.

If we compare:

A[x]

with:

B[x + g]

the two distributions align when:

g = k_B - k_A mod 26

That is the quantity MIC recovers.

It does not immediately tell us either absolute key letter.

If the method says:

g = 3

between two columns, it tells us:

second key shift = first key shift + 3 mod 26

Both could be:

A and D
B and E
C and F
...
O and R
...

The relative relationship is known; the absolute starting point is not.

That is why MIC can collapse a large key space without finishing the entire recovery by itself.

Controlled example: 500 letters and key ORBIT

To make every calculation reproducible, this example uses exactly 500 normalized letters from the previously verified benchmark corpus.

Plaintext:

ALICEWASBEGINNINGTOGETVERYTIREDOFSITTINGBYHERSISTERONTHEBANKANDOFHAVINGNOTHINGTODOONCEORTWICESHEHADPEEPEDINTOTHEBOOKHERSISTERWASREADINGBUTITHADNOPICTURESORCONVERSATIONSINITANDWHATISTHEUSEOFABOOKTHOUGHTALICEWITHOUTPICTURESORCONVERSATIONSSOSHEWASCONSIDERINGINHEROWNMINDASWELLASSHECOULDFORTHEHOTDAYMADEHERFEELVERYSLEEPYANDSTUPIDWHETHERTHEPLEASUREOFMAKINGADAISYCHAINWOULDBEWORTHTHETROUBLEOFGETTINGUPANDPICKINGTHEDAISIESWHENSUDDENLYAWHITERABBITWITHPINKEYESRANCLOSEBYHERTHEREWASNOTHINGSOVERYREMARKABLEINTHA

Key:

ORBIT

Using:

A = 0, B = 1, ... Z = 25
Cᵢ = (Pᵢ + Kᵢ) mod 26

produces this complete 500-letter ciphertext:

OCJKXKRTJXUZOVBBXUWZSKWMKMKJZXRFGABHKJVZPPIMKGZTBXFFOBASSBVDOEEWYVRWQGUEPBAWEHBHRFPVVSFSBPWTFAASYBLISVQMWWEUWMVVCWHYYFZLWJUMKKRTZXOUJVZPLUQMVREVHDZDBNFVTWKQFODXFJBBBCETQGWKBVWKYBBBGKIMNGVPNTPFPSMVFVOAHRMQVSNJBACLUXBQKVZXGFSKHBMFZLOKJWGGJPAASNBAVCETQWSIJVZWEIMKCNOUBBUBAPSCMILGYFKHICENHFKIMACKEIRAREMASIGMXZMFZRGCFMIMROLLHLQQWKYFBASIUPXDCFILIIFWYARLQGUREIBGPDPTWEXWNZUCMPCIUPMVVUZHISMMHTXFBMWEHCIOEEXBQBJVZHYFLTWJJMLKYFVLIUEMGZPBEAWKFZTPSJBPWKIXBBBFGXGIBVVZFTMUMYFZMVVSMPOJOWMVZOOLCMFZRFVNIKYRCTXWEUPT

The period is assumed to be known:

5

So the ciphertext is split into five columns.

Each contains exactly:

500 / 5 = 100 letters

The column/key relationship is:

The analysis below proceeds as though those key letters were unknown.

Start with Column 1 versus Column 2

Use Column 1 as the reference.

For every candidate shift from 0 through 25, calculate:

MIC_g(Column 1, Column 2)

The complete score table is:

The largest value is:

g = 3
MIC = 0.0556

So the best relative-shift hypothesis is:

k₂ - k₁ ≡ 3 mod 26

The ground truth is:

R - O
= 17 - 14
= 3

The relationship is recovered correctly.

Notice that the peak is only about:

0.0556

not a perfect textbook value near the long-run English IC.

That is normal.

Each column contains only 100 letters, and its observed frequency distribution is a finite sample. MIC should be interpreted by relative separation among candidate shifts, not by demanding that one fixed threshold always be reached.

Recover the remaining columns relative to Column 1

Repeat the same process for Columns 3, 4, and 5.

The strongest MIC shifts are:

Taking Column 1 as relative zero gives:

Column 1:  0
Column 2:  3
Column 3: 13
Column 4: 20
Column 5:  5

So the unknown key must have the form:

x
x+3
x+13
x+20
x+5

all modulo 26.

That is already a major reduction.

Why the key space collapses from 26⁵ to 26

Before using MIC, an arbitrary five-letter A–Z key has:

26^5
=
11,881,376

possibilities.

After the relative shifts are known, choose any one value for the first key letter.

Every other key letter is forced.

If the first shift were:

0 = A

the candidate key would be:

A D N U F

If the first shift were:

1 = B

the candidate would be:

B E O V G

Continue this through all 26 possible anchors.

Exactly one of those anchor choices is the true key:

14 = O

which produces:

O
R = O + 3
B = O + 13 mod 26
I = O + 20 mod 26
T = O + 5

or:

ORBIT

MIC has therefore changed the problem from millions of unrelated keys into one family of only 26 candidates.

How to determine the absolute anchor

Relative shifts alone cannot tell us whether the first letter is:

A
B
C
...
O
...
Z

We still need one absolute reference.

There are several ways to obtain it:

• compare one aligned distribution with expected language frequencies;
• score the 26 resulting full plaintext candidates;
• use a known or guessed plaintext fragment;
• identify one key letter from ordinary Caesar-frequency analysis.

For this example, use the language-frequency approach.

First, shift Columns 2–5 backwards by their recovered relative offsets:

Column 1: subtract 0
Column 2: subtract 3
Column 3: subtract 13
Column 4: subtract 20
Column 5: subtract 5

After that adjustment, all five columns behave as though they had been encrypted with the same unknown Caesar shift as Column 1.

Pool the adjusted letters.

Now compare that combined distribution against the same normalized English monogram model used in the earlier ciphertext-length benchmark.

The strongest anchors are:

The best anchor is:

14 = O

Apply the relative offsets:

14 + 0  = 14 → O
14 + 3  = 17 → R
14 + 13 = 27 mod 26 = 1 → B
14 + 20 = 34 mod 26 = 8 → I
14 + 5  = 19 → T

Recovered key:

ORBIT

Decrypting the ciphertext with that key reproduces the exact 500-letter plaintext shown above.

Why MIC is valuable even though direct frequency analysis also works

Once the period is known, a straightforward Vigenère attack can solve every column independently as a Caesar cipher.

So why use Mutual IC at all?

Because MIC exposes relationships between columns.

Instead of asking five separate questions:

What absolute shift produced Column 1?
What absolute shift produced Column 2?
What absolute shift produced Column 3?
What absolute shift produced Column 4?
What absolute shift produced Column 5?

it first asks:

How is Column 2 shifted relative to Column 1?
How is Column 3 shifted relative to Column 1?
...

Those relationships can be clearer than five independent absolute estimates, especially when the language model is imperfect.

Once the relative pattern is known, all columns can be aligned and pooled before the final absolute shift is chosen.

That gives the anchor stage much more text than any individual column contains.

The site’s Vigenère frequency-analysis guide covers direct per-column analysis. MIC is best understood as a complementary recovery strategy, not a replacement for all frequency scoring.

One weak reference column can mislead the simple version

The example above compares every other column with Column 1.

That is convenient, but it creates a dependency:

if Column 1 has an unusually poor finite-sample distribution,
all four relative estimates may become harder.

A more robust version computes additional pairwise relationships.

With five columns there are:

5 × 4 / 2 = 10

distinct column pairs.

For the same 500-letter ciphertext, the strongest MIC shift for every pair is:

That redundancy gives a consistency check.

For example:

1 → 2 = 3
2 → 3 = 10

so:

1 → 3 should equal 3 + 10 = 13 mod 26

and it does.

Similarly:

1 → 4 = 20
4 → 5 = 11

implies:

1 → 5 = 20 + 11 = 31 mod 26 = 5

which also matches.

This turns the key relationships into a small consistency network rather than four isolated guesses.

Inconsistent pairwise shifts are useful diagnostic evidence

Suppose the strongest MIC estimates produced:

1 → 2 = 3
2 → 3 = 10
1 → 3 = 11

Those cannot all be correct because:

3 + 10 = 13 mod 26

not 11.

That inconsistency tells you something useful:

• one MIC peak may be a finite-sample false maximum;
• the assumed key period may be wrong;
• one column may be too short or atypical;
• the plaintext language model may not behave as expected;
• the cipher may not be standard repeating-key Vigenère.

A robust program can use all pairwise relations and search for the set of relative shifts that best satisfies the complete network.

That is stronger than silently trusting the largest score from one noisy comparison.

MIC values are sample-dependent, not pass/fail constants

For two long samples drawn from the same shifted English distribution, a correctly aligned mutual IC is often expected near the ordinary English coincidence region.

For unrelated shifts, values tend toward a lower random-like region.

But finite samples do not obey those reference values exactly.

The first pair in this example peaks at only:

0.0556

while another correct pair reaches:

0.0743

Both relative shifts are correct.

So a rule such as:

MIC above 0.06 = correct
MIC below 0.06 = wrong

would reject valid evidence.

The practical signal is usually:

one shift is meaningfully stronger than its alternatives
+
other pairwise relationships are consistent
+
the resulting key family produces good language after anchoring

The score should be interpreted in context.

Short ciphertext makes relative recovery unstable

If a period-10 ciphertext contains only 100 letters, each column has about:

10 letters

A 26-way MIC comparison between two ten-letter columns has very little statistical evidence.

Random frequency bumps can dominate the result.

This is the same sample-size problem that appears throughout classical Vigenère cryptanalysis.

The earlier ciphertext-length benchmark showed that key recovery improves dramatically as more observations reach each recurring key position.

MIC does not escape that limitation.

It reorganizes the evidence; it does not manufacture additional data.

The period must be established before the columns mean what you think they mean

Mutual IC key recovery assumes that the ciphertext has been split using the correct fundamental period.

If the period is wrong, a “column” may mix letters encrypted under several different key shifts.

Its frequency distribution is then no longer one clean Caesar-shifted language sample.

Relative MIC peaks become weaker or misleading.

That is why period finding belongs first.

Kasiski, average-column IC, Friedman, and autocorrelation address that earlier problem. Their comparative behavior is covered in Kasiski vs IC vs Friedman vs Autocorrelation.

Only after a plausible period survives those checks does the relative-key problem become well-defined.

Multiples of the true period need care

A candidate period can be a multiple of the fundamental period.

Suppose the true period is:

5

but the ciphertext is split into:

10

columns.

Each of those ten columns can still contain one fixed key shift.

So MIC may recover a perfectly consistent ten-position relationship.

The result is not numerically “wrong.”

It is simply redundant.

Two groups of columns correspond to the same underlying five-position cycle.

After key recovery, test whether the recovered shift sequence itself has a shorter fundamental period.

For example:

ORBITORBIT

is a ten-character written sequence with fundamental period:

ORBIT

or 5.

Period reduction belongs in the final verification step.

Language matters

The mutual relationship between Vigenère columns does not require the plaintext to be English in principle.

It requires the columns to be samples from the same underlying language distribution, shifted by different key letters.

However, the final absolute anchor normally needs some language model or other external clue.

If the plaintext is French, German, Spanish, or another language, use an appropriate reference distribution.

If the plaintext is source code, identifiers, names, or highly constrained text, ordinary prose frequencies may be a poor fit.

Relative MIC may still reveal column relationships while the English anchor fails.

That distinction is useful:

relative alignment problem
≠
absolute language-identification problem

A practical Mutual IC recovery workflow

Once the period m is credible:

1. Split the ciphertext into m recurring columns.

2. Choose one column as a temporary reference.

3. For every other column:
   calculate MIC for g = 0..25.

4. Record the strongest relative shift.

5. Check extra column pairs for consistency when the sample is short
   or the peaks are ambiguous.

6. Express all key positions relative to one anchor:
   [0, r₂, r₃, ... r_m]

7. Try the 26 possible absolute anchor shifts.

8. Score the resulting plaintext or aligned pooled distribution
   using the expected language.

9. Recover the full key.

10. Reduce the key to its smallest repeating period.

11. Decrypt and verify the plaintext.

For the worked example:

period = 5

relative key =
[0, 3, 13, 20, 5]

best anchor =
14

full key =
[14, 17, 1, 8, 19]

letters =
ORBIT

The complete process is reproducible from the published plaintext, ciphertext, formula, and companion script.

What Mutual IC actually contributes

The useful idea is not simply “another frequency statistic.”

Mutual IC changes the geometry of the key-recovery problem.

Before relative alignment:

each key position appears to have 26 independent possibilities

After reliable relative alignment:

all key positions move together

Only one global Caesar offset remains.

For a period-5 key, that means:

11,881,376 theoretical keys

collapse to:

26 related candidates

before final language scoring.

That is why Mutual Index of Coincidence is valuable in classical Vigenère cryptanalysis.

It does not discover the period.

It does not guarantee the absolute key.

It does something more specific:

it recovers how the key positions are shifted relative to one another, allowing the remaining uncertainty to be reduced to a single global offset.

---

Written by Marcus Hale

Editorially reviewed by VigenereDecoder.com editorial team