We consider the alphabet A= {0,1,2,3,4} and the space of messages consists of all 1-symbol words, so it is M ={0,1,2,3,4}. The encryption is done using the shift cipher, so it is given by the equation X = x+k (mod 5) applied to each letter of the plaintext (as discussed in class, x is the letter that we encrypt, k is the secret key, and X is the encrypted letter).
a. Suppose Eve knows that the symbols 0 and 1 have the same probability Prob(M=0)=Prob(M=1) = a, and the symbols 2,3, and 4 have the same probability Prob(M=2) = Prob(M=3) = Prob(M=4) = b, and she also knows that 0 is three times more likely than 2, so she knows that a = 3b. Find a and b. (Hint: use the fact that the sum of all probabilities is 1).
b. Calculate Prob (M= 1 | C = 4) (according to Eve's distribution). Recall that C= EK(M), that is the ciphertext is obtained by encrypting the message M (which is drawn according to Eve's distribution which you found at point a.), and the key is equally likely to be any number in the set {0,1,2,3,4}. You'll have to use the formula for conditional probability (see the notes, and the proof of Shannon's theorem).
c. Show that the given encryption system is perfectly secure for , by checking the definition given in class for perfect security - version 1 (Note: you need to consider an arbitrary distribution on because the definition must hold for all possible distributions).