# Uses needed to break a substitution cipher (alphabet of 5 symbols, normalized entropy of the source of 2)

I'm studying for an information theory exam, maybe some of you can help me here with an exercise about cryptography.

I'm trying to understand how to calculate the minimum needed uses to break a substitution cipher.

The exercise, is a multiple choice one, and goes like: having and alphabet of 5 symbols, having a full substitution cipher for this alphabet and knowing that the normalized entropy of the source is 2 we can assure that such encryption scheme in unbreakable for: 1. less than 22 uses; 2. more than 15 uses; 3. just one use; 4. always.

From the classes presentation slides I get that given the function $f$,

$$f(n) = H(Z) - n\log_2(L_Y)(1-H(X)/(N\log_2L_Y))$$

The cipher is unbreakable when $f(n)=0$ and that happens when

$$n \geq \frac{H(Z)}{\log_2 L_Y - H_{\text{norm}}(X)}$$

I think $H(Z)$ is somewhat the entropy of the cipher that on the presentation slides appears as the factorial of the length of the cipher, in this case $5!$. I think $L_Y$ is the length of the alphabet, which is $5$. Assuming this WolframAlpha gives me $n\ge$~372,75. Maybe I'm messing this up and wrongly assuming these values.

More generally, is this how I can calculate the minimum needed uses to break a substitution cipher? Am I assuming the correct values for $H(Z)$, and $L_Y$?

Greatly appreciated.

-

If you have $N$ characters in front of you then you have $(\log_2 5)N$ bits of information, but the entropy of the source is $\log_2 120 + 2N$. Therefore the system is unbreakable when $$N \leq \frac{\log_2 120}{\log_2 5 - 2} \approx 21.5.$$
Ok. Thanks. :) I get it but care to explain one more thing? Why the entropy of the source is $log_2 120 + 2N$ instead of $(log_2 5)N$? How can I get that entropy only knowing the normalized one? – pedrosanta Jul 10 '11 at 23:05
The $\log_2 120$ corresponds to the permutation. The $2N$ part follows from the definition of "normalized entropy", which is, by the way, a somewhat non-standard concept (I've never heard it before). – Yuval Filmus Jul 11 '11 at 13:11