Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
I don't think it is. In any case - what is $t$? –  Stephen Harris Jun 27 '12 at 19:52
    
@StephenHarris - Ops, sorry for not specifying. $t$ is the period of the poly alphabetic cipher used for creating the crypto message. –  Matteo Jun 28 '12 at 13:04
add comment

1 Answer

up vote 2 down vote accepted

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}

share|improve this answer
    
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? –  Matteo Jun 29 '12 at 7:20
    
I forgot to say, thks for help! –  Matteo Jun 29 '12 at 7:21
    
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. –  Stephen Harris Jun 29 '12 at 11:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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