Recall that for the shift cipher, we have M = C = K = Z/26Z (the integers modulo 26). Encryption is given by EK(M) ≡ M +K (mod 26) (modular addition of message and key).

(i) Give a formal mathematical proof that double encryption for the shift cipher under two keys K1, K2 results again in a shift cipher. What is the key of the double encipherment?

(ii)  Give a formal mathematical proof that superencipherment (i.e. multiple encryptions) for the shift cipher results again in a shift cipher. Use induction on the number of encipherments (solutions that do not use induction will be penalized). What is the key of the multiple encipherments?