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

m0 + m1 = 1 and

m1 <> m2

Pr [K=0] = k0

Pr [K=1] = k1

k0 + k1 = 1If 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