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

Sale!