0
$\begingroup$

I was not able to mathematically prove that all permutation and substitution ciphers satisfy H(X)=H(Y) if we say that Y is the set of ciphertexts while X is the corresponding set of plaintexts in Shanon Entropy?

More generally, how is it possible to mathematically prove that Shannon entropy does not change when applying any bijective function to X?

$\endgroup$
1
  • 2
    $\begingroup$ Hint: the permutation just permutes the char. Just replace the for i with the permutation and claim that they are the same sum. $\endgroup$ – kelalaka Dec 24 '20 at 0:00
2
$\begingroup$

For any one to one encryption mapping, which these ciphers are assumed to be, say $E:{\cal M} \rightarrow {\cal C}$ under whatever key, we have: $$ H(Y) =-\sum_{y \in {\cal C}}p(y)\log p(y)= -\sum_{y \in {\cal C}} p(E^{-1}(y)) \log p(E^{-1}(y)) $$ which can be rewritten as $$ H(Y)=-\sum_{x \in {\cal M}} p(\sigma(x)) \log p(\sigma(x)) $$ for some permutation $\sigma$ of the messages.

Note that the decryption mapping exists since $E$ is one to one.

$\endgroup$
2
  • $\begingroup$ And yet NIST 800-90B reports entropy as min(H_original, 8 X H_bitstring) which is a choice of two values for the same data set. As does ent. Bijection matters somewhat... $\endgroup$ – Paul Uszak Dec 28 '20 at 2:51
  • $\begingroup$ My answer was about Shannon entropy as the OP asked $\endgroup$ – kodlu Dec 28 '20 at 4:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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