2. (3 points) Yet Another One Time Pad Consider the following variant of the one-time pad. Let the key space K, message space M, and ciphertext space C be {0,1,...,25}n. The one-time pad is defined as follows: Setup chooses a uniformly random key K K. Enc(K,M) takes as input a key K Kand a message M M. Let K[i] and M[i] denote the ith component of the key and message respectively. The encryption algorithm computes C[i] = (M[i] + K[i]) mod 26 for all 0 i < n. It outputs C = (C[0],C[1],...,C[n 1]). Dec(K,C) takes as input a key K K and a ciphertext C C. It computes M[i] = (C[i] K[i]) mod 26 and outputs M = (M[0],M[1],...,M[n 1]).

(a) For any c C,m M, compute Pr[Enc(K, M) = c|M = m], where the probability is over the choice of K.

(b) Let C = Enc(K,M) and C = Enc(K,M). Express M in terms of M, C, and C only (not involving K).