Cryptography: Theory and Practice:Classical Cryptography | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

DEFINITION 1.8 Suppose x = x₁x₂ . . . x_n′ and y = y₁y₂ . . . y_n′ are strings of n and n′ alphabetic characters, respectively. The mutual index of coincidence of x and y, denoted MI_c(x, y), is defined to be the probability that a random element of x is identical to a random element of y. If we denote the frequencies of A, B, C, . . . , Z in x and y by f₀, f₁, f₂₅ and f′₀, . . . , f′₁, . . . , f′₂₅, respectively, then MI_c(x, y) is seen to be

Now, given that we have determined the value of m, the substrings y_i are obtained by shift encryption of the plaintext. Suppose K = (k₁, k₂, . . . , k_m) is the keyword. Let us see if we can estimate MI_c(y_i, y_j). Consider a random character in y_i and a random character in y_j. The probability that both characters are A is , the probability that both are B is , etc. (Note that all subscripts are reduced modulo 26.) Hence, we estimate that

Observe that the value of this estimate depends only on the difference k_i - k_j mod 26, which we call the relative shift of y_i and y_j. Also, notice that

so a relative shift of yields the same estimate of MI_c as does a relative shift of 26 - .

We tabulate these estimates, for relative shifts ranging between 0 to 13, in Table 1.4.

**Table 1.4** Expected Mutual Indices of Coincidence
relative shift	expected value of MI_c
0	0.065
1	0.039
2	0.032
3	0.034
4	0.044
5	0.033
6	0.036
7	0.039
8	0.034
9	0.034
10	0.038
11	0.045
12	0.039
13	0.043

The important observation is that, if the relative shift is not zero, these estimates vary between 0.031 and 0.045; whereas, a relative shift of zero yields an estimate of 0.065. We can use this observation to formulate a likely guess for , the relative shift of y_i and y_j, as follows. Suppose we fix y_i, and consider the effect of encrypting y_j by e₀, e₁, e₂, . . .. Denote the resulting strings by , etc. It is easy to compute the indices , 0 ≤ g ≤ 25. This can be done using the formula

When g = , the MI_c should be close to 0.065, since the relative shift of y_i and is zero. However, for values of g ≠ , the MI_c should vary between 0.031 and 0.045.

By using this technique, we can obtain the relative shifts of any two of the substrings y_i. This leaves only 26 possible keywords, which can easily be obtained by exhaustive key search, for example.

Let us illustrate by returning to Example 1.11.

Example 1.11 (Cont.)

We have hypothesized that the keyword length is 5. We now try to compute the relative shifts. By computer, it is not difficult to compute the 260 values , where 1 ≤ i ≤ j ≤ 5, 0 ≤ g 25. These values are tabulated in Table 1.5. For each (i, j) pair, we look for values that are close to 0.065. If there is a unique such value (for a given (i, j) pair), we conjecture that

it is the value of the relative shift.

Six such values in Table 1.5 are boxed. They provide strong evidence that the relative shift of y₁ and y₂ is 9; the relative shift of y₁ and y₅ is 16; the relative shift of y₂ and y₃ is 13; the relative shift of y₂ and y₅ is 7; the relative shift of y₃ and y₅ is 20; and the relative shift of y₄ and y₅ is 11. This gives us the following equations in the five unknowns k₁, k₂, k₃, k₄, k₅:

Table of Contents