1
$\begingroup$

I can't seem to find a simple explanation of Mutual Index of Coincidence.

I am finding explanations of Mutual Index of Coincidence not Index of Coincidence. I don't understand what the formula below means

$$\textit{MI}_c(\mathbf x, \mathbf y) = \frac{\sum_{i=0}^{25} f_i\times f'_i}{n\times m}$$

I want to write code to compute it.

$\endgroup$
3
$\begingroup$

As defined e.g. in Stinson's Cryptography: Theory and Practice (1995, 1st ed.; the earliest source for the term I could find that has even excerpts online), the mutual index of coincidence of two strings of symbols (letters, numbers, whatever) is simply the probability that two symbols chosen at random from each of the strings will be the same.

The formula you've quoted for calculating it looks somewhat garbled, though. The original(?) definition given in Stinson's book looks like this:

DEFINITION 1.8   Suppose $\mathbf x = x_1 x_2 \dots x_n$ and $\mathbf y = y_1 y_2 \dots y_{n'}$ are strings of $n$ and $n'$ alphabetic characters, respectively. The mutual index of coincidence of $\mathbf x$ and $\mathbf y$, denoted $\textit{MI}_C(\mathbf x, \mathbf y)$, is defined to be the probability that a random element of $\mathbf x$ is identical to a random element of $\mathbf y$. If we denote the frequencies of $A, B, C, \dots, Z$ in $\mathbf x$ and $\mathbf y$ by $f_0, f_1, \dots, f_{25}$ and $f'_0, f'_1, \dots, f'_{25}$, respectively, then $\textit{MI}_C(\mathbf x, \mathbf y)$ is seen to be $$\textit{MI}_C(\mathbf x, \mathbf y) = \frac{\sum_{i=0}^{25} f_i f'_i}{n n'}.$$

For example, assuming that $\textbf x = \text{"ABACA"}$ and $\textbf y = \text{"BABAA"}$, then $n = 5$, $f_0 = 3$, $f_1 = 1$ and $f_2 = 1$ (since $\textbf x$ contains five letters: three $A$'s, one $B$ and one $C$) while $n' = 5$, $f'_0 = 3$, $f'_1 = 2$ and $f'_3 = 0$ (since $\textbf y$ contains three $A$'s, two $B$'s and no $C$'s), so the mutual index of coincidence of $\textbf x$ and $\textbf y$ is $$\textit{MI}_C(\mathbf x, \mathbf y) = \frac{f_0 f'_0 + f_1 f'_1 + f_2 f'_2}{n n'} = \frac{3\times3 + 1\times2 + 1\times0}{5\times5} = \frac{11}{25} = 0.44.$$


In particular, note that the "plain" index of coincidence of a string of symbols, i.e. the probability that two symbols chosen at random from the same string are equal, is very close to the mutual index of coincidence of the string with itself. The only difference is that the single-string definition assumes that the two symbols are always chosen from different positions in the string (i.e. that we never just pick the same position twice and compare the symbol there with itself), which requires a small correction. That is to say, $$I_C(\mathbf x) = \frac{\sum_{i=0}^{25} f_i(f_i-1)}{n(n-1)} \ne \textit{MI}_C(\mathbf x, \mathbf x) = \frac{\sum_{i=0}^{25} f_i^2}{n^2},$$ but the difference between the two formulas approaches zero as the length $n$ of the string $\mathbf x$ increases (and, in practice, is small enough to get lost in random sampling noise anyway).

(Also worth noting is that there are some minor variations between authors in the definitions of both the single-string index of coincidence and the mutual version. For example, Wikipedia — which currently doesn't mention the mutual index of coincidence at all — uses a definition of $I_C$ that differs from Stinson's by being multiplied by the alphabet size $c = 26$, ostensibly to make it more comparable between texts written in alphabets of different sizes. In any case, such minor differences in definitions have no real effect on cryptanalysis.)


Anyway, what's this whole "mutual index of coincidence" good for, then? Well, for one, given two strings sampled from the same plaintext source but encrypted with possibly different shift ciphers — such as two columns from a Vigenère ciphertext, after determining the key length $\ell$ and splitting the ciphertext into rows of $\ell$ characters — we can use it to determine whether or not the strings have been encrypted with the same shift amount.

By further shifting the characters in one of the strings by successive amounts, and finding the shift that maximizes the mutual index of coincidence, we can quite reliably determine the difference between the two key letters used to encrypt those columns. In this way, once we've guessed one letter of a Vigenère key, we can statistically determine the rest of them, effectively reducing the Vigenère cipher to a simple monoalphabetic Caesar shift cipher.

$\endgroup$
  • $\begingroup$ How do i compare the two text Index of Coincidence, What do nn is multiply two string. but i dont understand how the two fs work $\endgroup$ – Wei Wen May 1 at 18:37
  • $\begingroup$ @WeiWen: I've added a simple worked example above. Perhaps that helps? $\endgroup$ – Ilmari Karonen May 2 at 8:54
  • $\begingroup$ It can be also used to determine the key length of Vigenère by looking at possible key lengths with IC. $\endgroup$ – kelalaka May 2 at 9:04
  • $\begingroup$ @kelalaka: Normally you'd use the single-string index of coincidence for that, not the mutual IoC. $\endgroup$ – Ilmari Karonen May 2 at 9:07
  • $\begingroup$ Yes, When I write IC it was the single, sorry. $\endgroup$ – kelalaka May 2 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.