My Proof for Shannon Theorem

In this topic, I use my informal way to proof Shannon Theorem. Yes, it is informal but easy to understand the theorem. I also proof that the substitute cipher is not perfect secrecy.

Shannon Theorem:

A cipher (E, D) over (K, M, C) has perfect secrecy
=>
|K| >= |M|

The theorem is identical the below statement.

|K| <= |M|
=>
A cipher doesn't have perfect secrecy

My proof of the theorem is to give an example.

Lets

K = {0, 1}, M = C = {0, 1}^2

We define the encryption algorithm E as below.

if k = 0,

 m  c
-----
00 00
01 01
10 10
11 11

if k = 1,

 m  c
-----
00 01
01 10
10 11
11 10

We use the below formula to verify if the cipher is perfect secrecy. It it is perfect secrecy,

Pr [E (k, m) = c] = constant

I use the both pairs

(m, c) = (00, 00) or (00, 10)

to verify it.

Pr [E (k, 00) = 00] = (# of keys) / |K| = 1/2, 

Only one key, k=0, exists.

Pr [E (k, 00) = 10] = (# of keys) / |K| = 0/2 = 0,

We cannot find a key to make the equation.

Pr [E (k, m) = c] = 1/2 or 0

Obviously, it is not constant. Therefore the cipher is not perfect secrecy. We proof it. Actually, the cipher is called substitute cipher.

-Count