Cryptanalysis of the Vigenere cipher by the index of coincidence method

We have the cipher text (x_s)_{0 £ s < N} which is encrypted by the Vigenere method using the key (k_r)_{0 £ r < K} . Here x_s Î A, A being the alphabet used. We assume that A = Z_S, where S is the size of the alphabet. We do all arithmetic in this Z_S.

We define the subsequences X_kj = (x_kn+j)_{n = 0...} of the ciphertext. For example X_3,2 = (x₂,x₅,x₈,...)

Each sequence has a probability distribution H_kj where for each x Î A, H_kj(x) is the probability of occurence of x in X_kj.

Each probabability distribution has its index of coincidence defined as

IC(Hkj) = å x Î A  Hkj(x)2

which measures its difference from the uniform, that is random, distribution.

If k ¹ K we expect that X_kj is more or less random. So IC(H_kj) must be close to the index of coincidence of random text on A, which is 1/|A|.

If k = K, then each ciphertext letter belonging to X_kj has been encrypted using the same key letter, so IC(H_kj) must be closer to the index of coincidence of the original text. We also know that the distribution of real human languages is not random and that the index of coincidence for these is considerably larger than 1/|A|.

So, if we put a reasonable upper bound for the key length, we can calculate all the IC(H_kj) up to this upper bound, and use the maximum value we get to determine the key length.

After we find the key length we concentrate on the subsequences X_kj with k = K, the key length.

These are encrypted using different letters of the key, so probably have different distributions.

The difference between two distributions is measured using the mutual index of coincidence.

IC(Hki,Hkj) = å x Î A  Hki(x)Hkj(x)

We know that this takes its maximum value when the distributions are same. The more different the distributions are, the smaller the mutual index of coincidence.

Now suppose that the original text is U = (u_s). We have

XKi = (xKn+i) = (uKn+i+ki) XKj = (xKn+j) = (uKn+j+kj)

Let

XKi(t) = (xKn+i+t) = (uKn+i+ki+t)

That is X_Ki^(t) is the encryption of X_Ki using the shift cipher with key t. If k_i+t = k_j then the sequences X_Ki^(t) and X_Ki would be encrypted by the same shift value, namely k_i+t = k_j. Therefore they would have more or less the same distribution. In contrast, if k_i+s ¹ k_j, the distributions X_Ki^(s) and X_Ki would not be the same.

The distribution of of X_Ki^(t) can be calculated easily from the distribution of X_Ki: Every x in X_Ki corresponds to a x+t in X_Ki^(t). So we have H_Ki(x) = H_Ki^(t)(x+t) or H_Ki^(t)(x) = H_Ki(x-t).

Now we can calculate the following for all possible values of t:

IC(HKj,HKi(t)) = å x Î A  HKj(x)HKi(t)(x) = å x Î A  HKj(x)HKi(x-t)

By these considerations, the maximum of these values must occur when we have k_i+t = k_j or k_j-k_i = t. These give us several relations between the keys letters that enables us to find the key up to the first letter. Then the actual key can be easily found by trial and error.