From the class:
Shannon Theorem: For a perfect encryption scheme, the number of keys is at least the size of the message space (number of messages that have a non-zero probability).
Proof:
Consider ciphertext $c$. $c$ must be a possible encryption of any plaintext $m$. But, for this we need a different key per message $m$. $m \neq m' \iff c \neq c' $. Why?
Can someone explain the logic behind the proof? I understand that the one above is a partial one but still can I have an easy to understand explanation? No need a formal one.
$c$ must be a possible encryption of any plaintext $m$.
I understand that.
But, for this we need a different key per message $m$.
Why? I can have the same key for different messages and still produce different ciphers, and those ciphers would be " a possible encryption of any plaintext m ".
$m \neq m' \iff c \neq c'$ Why?
Didn't understand that either, could have different messages but same ciphers. But if we indeed force that each message has it's own unique key then it is true, and then we showed that size of keys space > size of messages space.