Finding length of a key for a given vigenere cipher using Index of Coincidence

Question

I'm developing an algorithm that takes in a vigenere cipher and produces the key length automatically. However, I'm having trouble understanding how to detect the key length when there are multiple large index of coincidences.

For example, given this cipher:

vptnvffuntshtarptymjwzirappljmhhqvsubwlzzygvtyitarptyiougxiuydtgzhhvvmum
shwkzgstfmekvmpkswdgbilvjljmglmjfqwioiivknulvvfemioiemojtywdsajtwmtcgluy
sdsumfbieugmvalvxkjduetukatymvkqzhvqvgvptytjwwldyeevquhlulwpkt

My algorithm produces the following indexes of coincidences for each possible key length:

KL IoC
 1 0.04494435235614492    -->  4%
 2 0.0457833618884447     -->  5%
 3 0.04358853643122834    -->  4%
 4 0.04749622926093514    -->  5%
 5 0.039361207897793266   -->  4%
 6 0.04714370596723538    -->  5%
 7 0.09099225897255454    -->  9%
 8 0.04618589743589745    -->  5%
 9 0.04078047556308426    -->  4%
10 0.03611528822055138    -->  7%
11 0.04916033399005535    -->  5%
12 0.05126633986928104    -->  5%
13 0.04468864468864469    -->  4%
14 0.09884877027734174    -->  10%
15 0.033455433455433455   -->  3%
16 0.03962703962703963    -->  4%
17 0.04305498423145482    -->  4%
18 0.04747474747474748    -->  5%
19 0.030303030303030304   -->  3%
20 0.03222222222222222    -->  3%
21 0.082010582010582      -->  8%
22 0.0436868686868687     -->  4%
23 0.03260869565217391    -->  3%
24 0.05158730158730159    -->  5%
25 0.03666666666666666    -->  4%
26 0.04441391941391941    -->  4%
27 0.03791887125220458    -->  4%
28 0.1058673469387755     -->  11%

The correct key length for this cipher is indeed "7", but why is it not 14, 21, or 28? Their IoC is higher after all? What can I do within my algorithm to make it produce 7 as the key length rather than 14, 21, or 28 (or vice versa)?

Answer 1

The index of coincidence is significantly higher for

• The correct keylength
• All its multiples

Even if that is not the correct key, you will have a behavior like that. Assuming you have a high index at length $7$, then by the nature of the algorithm you will have a high index at $14, 21, 28, \dots$, regardless if that is the correct key or not.

So the best stragety would be, just to start with the lowest value and if it doesn't work out move to the next outlier (which is most likely your first value doubled). Things like calculatin the GCD of all the outliers, etc. is not wrong but unnecessary, if you can just iterate through and have a really high chance of success on your first (or first few) tries.

One more thing: This kind of analysis is only faulty for short texts (with being impossible to break if the keylength is as long as the message, and the key is chosen uniformly random and only used once), and for longer texts the law of large numbers (in particular, see the variance of the central limit theorem ) will cause all the other values to be really, really close to what you would exepct from a uniform distribution over the alphabet.

Answer 2

As the other answers note, any multiple of the correct key length will also yield an IoC close to that of the actual key length. Thus, one practical heuristic for determining the correct key length would be to sort the key lengths based on the difference $\delta$ between their IoC and the maximum IoC observed for any shorter key length. (For key length 1, it probably makes sense to define $\delta = 0$.)

For example, for your example message, you'll find the following candidate key lengths below 50 with $\delta > 0$:

  7: ioc = 269 /  2929 = 0.091840, delta = +0.044166 | ######################
 14: ioc = 142 /  1414 = 0.100424, delta = +0.008584 | ####
 28: ioc =  70 /   658 = 0.106383, delta = +0.005959 | ###
  4: ioc = 248 /  5202 = 0.047674, delta = +0.001795 | #
  2: ioc = 482 / 10506 = 0.045879, delta = +0.000887 | 

Note how the correct key length 7 has a $\delta$ over five times higher than that of the next best candidate 14.

(BTW, we seem to be calculating the IoC somewhat differently, since my numbers don't exactly match yours. I'm calculating it by examining every pair of ciphertext letters whose distance is a positive integer multiple of the candidate key length, and taking the fraction of those pairs for which the letters match.)

---

Ps. If you start considering longer candidate key lengths, you'll eventually come up with some unexpectedly high IoC and $\delta$ values simply due to statistical noise, since for higher key lengths there are fewer letter pairs to test, and thus more opportunities for a single lucky match to skew the results.

One way to avoid these spurious results is to discount the estimated IoC for longer key lengths, e.g. by taking the lower bound of an appropriately chosen confidence interval instead of the raw proportion of matching pairs.

For example, instead of calculating the IoC simply as $\hat p = \frac{m}{n}$, where $m$ is the number of matching pairs out of $m$, you can instead calculate the lower bound of the Wilson score interval for a suitable smoothing parameter $z$:

$$\hat p_{-z} = \frac1{n + z^2} \left[m + \frac12 z^2 - z\sqrt{\frac{m(n-m)}{n} + \frac14 z^2} \right].$$

For your example ciphertext, using $z = 3$ (a moderately conservative choice), I get only the following candidate key lengths with $\delta > 0$:

  7: ioc >= 0.076744, delta = +0.035886 | ##################
 14: ioc >= 0.078286, delta = +0.001543 | #

where the $\delta$ calculated from the adjusted IoC values for key length 7 is now over 20 times higher than that for the next candidate length 14. For $z = 4$ and higher, 7 is the only candidate key length with $\delta > 0$.

Answer 3

This is more a programming/data analysis question rather than cryptography one.

In this present case, a simple data analysis shows that the average of candidates key lengths (7, 14, 21 and 28) is twice the average the results ($4.5\% \rightarrow 9\%$).

You also should know that these key length candidates are multiples of the real key length.

Therefore you simply:

1. make a cut off to "select" the highest IoC,
2. use the integer factorization if possible. (Having a list of all prime numbers under a certain threshold might help.)
3. use it to find the Greatest common divisor.

Answer 4

if the key is "key", then the algorithm shows for 3, but "keykey" should also be a valid key, showing 6. This is why there are peaks at the multiples of the key lengths.