Tuesday, September 6, 2016

Why must the key of the encryption be random?

When I learn the Stanford online course, Cryptography I, I ask my self the question: "Why must the key of the encryption be random?"

The encryption algorithm is written below.

C = E (M, K) 

where
C is ciphertext,
M is plaintext message,
K is a key,
E is an encryption algorithm.

We use XOR algorithm as encryption algorithm.

C = M XOR K.

The purpose is to make C an uniform random variable even though M is not, and specify:

Pr [M=0] = m0
Pr [M=1] = m1
m0 + m1 = 1 and 
m1 <> m2

Pr [K=0] = k0
Pr [K=1] = k1
k0 + k1 = 1

If K is not an uniform random variable, then

k0 <> k1

Below is the table of the equation, C = M XOR K.


M K C Probability   
0 0 0 m0 * k0
0 1 1 m0 * k1
1 0 1 m1 * k0
1 1 0 m1 * k1 


We can calculate that:

Pr [C=0] = m0 * k0 + m1 * k1 <> 1/2
Pr [C=1] = m0 * k1 + m1 * k0 <> 1/2

Thus C is not a uniform random variable.

I draw the below picture to explain why the two inequalities are right.

m0 * k0 + m1 * k1 <> 1/2
m0 * k1 + m1 * k0 <> 1/2



When I see the two areas m0 * k0 and m1 * k1, I FEEL that m0 * k0 + m1 * k1 <> 1/2.

In conclusion, if we want to build a ciphertext randomly, the key must be random.

We also make sure that XOR encryption is a randomized algorithm because if the key is a uniform random variable, the output ciphertext  is also a uniform random variable.

The next page explain why XOR encryption is a randomized algorithm.

-Count




No comments:

Post a Comment