1
$\begingroup$

Can Anybody tell me why the expectation value of the Index of Coincidence is the following?

For a cipher text string of length $L$, where $n$ is the number of alphabet characters, $k_r = 1/n$, and $k_p = \sum_{i=1}^n p_i^2$

$$ E(IC) = \frac{1}{t}*\frac{L - t}{L - 1}*k_p + \frac{t - 1}{t}*\frac{L}{L - 1}*k_r$$


I forgot to state that $t$ is the period of the poly alphabetic cipher used to encipher the message.

$\endgroup$
2
  • $\begingroup$ I don't think it is. In any case - what is $t$? $\endgroup$ Jun 27, 2012 at 19:52
  • $\begingroup$ @StephenHarris - Ops, sorry for not specifying. $t$ is the period of the poly alphabetic cipher used for creating the crypto message. $\endgroup$
    – Matteo
    Jun 28, 2012 at 13:04

1 Answer 1

2
$\begingroup$

Expected Index of Coincidence usually refers to a language's expected index of coincidence (1.73 for English, or 0.067 if you're not normalising).

The formula in question is usually used to determine the length of the key ($t$) given the (measured) $IC$ of received cipher-text. $IC$ is the probability that two randomly-selected letters from the cipher text are identical.

Let $X=\{ x_1,x_2,x_3,...x_L\}$ be the cipher-text. If we think the the poly-alphabetic cipher has period $t$, then we would expect each of the following:

\begin{eqnarray} & X_1 =\{x_1, x_{t+1},x_{2t+1},...\}\\ & X_2 =\{x_2, x_{t+2},x_{2t+2},...\}\\ & \vdots \\ &X_t =\{x_t, x_{2t},x_{3t},...\} \end{eqnarray}

to exhibit the same index as the plaintext ($\kappa_p$). So we can reconstruct $IC(X)$ as follows. Pick two letters at random, we want the probability that they match.

The probability that they are in the same $X_i$ is:

$$ \frac{tC(\frac{L}{t},2)}{C(L,2)} = \frac{L*(\frac{L}{t}-1)}{L(L-1)} $$

The probability they are in different $X_i$s is: $$ \frac{C(t,2)*\frac{L}{t}*\frac{L}{t}}{C(L,2)} = \frac{t(t-1)*\frac{L}{t}*\frac{L}{t}}{L(L-1)} $$

  • If they are in the same $X_i$ then they are both enciphered using the same alphabet: so the probability is $\kappa_p$
  • If they are in different $X_i$s then they are enciphered using different alphabets, so we can assume they are randomly distributed: so the probability is $\kappa_r$

So the probability of two random letters matching is approximately

\begin{eqnarray} IC(X) & \approx \frac{L*(\frac{L}{t}-1)}{L(L-1)}\kappa_p + \frac{t(t-1)*\frac{L}{t}*\frac{L}{t}}{L(L-1)}\kappa_r\\ & = \frac{(L-t)}{t(L-1)}\kappa_p + \frac{(t-1)*L}{t(L-1)}\kappa_r \end{eqnarray}

$\endgroup$
3
  • $\begingroup$ Ok, so what I found indicated as Expectation Value of the IC, actually is the calculation of the IC?I'm afraid I'm making confusion: I thought that the IC was a random variable, and E(IC) it's expectation value...am I wrong? $\endgroup$
    – Matteo
    Jun 29, 2012 at 7:20
  • $\begingroup$ I forgot to say, thks for help! $\endgroup$
    – Matteo
    Jun 29, 2012 at 7:21
  • $\begingroup$ A random variable is a map from a probability space to a space of 'outcomes'. $IC$ is a probability. The $IC_{expected}$ is the probability that two letters taken from the alphabet match and depends on the statistical characteristics of the language. You compare this with the calculated $IC$ (which is a ratio of number of matches to number of pairings). You then use the above formula to solve for $t$. This gives an estimate for the period used. $\endgroup$ Jun 29, 2012 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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