Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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. $$

share|improve this answer
    
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

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.