1. Consider a variant of the Vigen`ere cipher where instead of a word or short phrase, the key instead consists of a book or some other English-language text that is much longer than the message to be encrypted. Using this cipher, the key is never repeated, so our standard methods for retrieving the key length will fail. Now assume that Bob is a sleeper agent and Alice is his handler. Alice, using this cipher, has sent Bob a ciphertext that reads zsfgsjvtpsnzycrvc The plaintext is known to contain the day of the week that Bob is supposed to receive the dead drop, followed by the day of the week he is supposed to flee the country. Determine which plaintext Alice sent to Bob, and explain how you reached your answer. Note. Each ciphertext character ci is equal to mi + ki (mod 26), where mi is the i-th character of the plaintext message and ki is the i-th character of the key. In particular, the alphabet is indexed from 0, so ‘a’ corresponds to 0, ‘b’ corresponds to 1, and so on. 2. a. Assume an attacker knows that a user’s password is either abcd or bedg. Say the user encrypts his password using the shift cipher, and the attacker sees the resulting ciphertext. Show how the attacker can determine the user’s password, or explain why this is not possible. b. Repeat part (a) for the Vigen`ere cipher using period 2, using period 3, and using period 4. 3. Prove that if an encryption scheme Π = (Gen,Enc,Dec) is perfectly secret then it is perfectly indistinguishable. 4. For each of the following encryption schemes, state whether the scheme is perfectly secret. Justify your answer in each case. a. The message space M is f0; : : : ; 4g. Algorithm Gen chooses a uniform key k from the key space f0; : : : ; 5g. Enck(m) = [k + m mod 5]. b. The message space M is f0; 1g2n. Gen chooses an uniform key k from f0; 1gn. Enck(x) = hx1:::n ⊕ k; xn+1:::2n ⊕ ki, where ⊕ denotes the bitwise XOR. 1
