Homework 1 Introduction to Cryptography


5/5 - (4 votes)

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
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.

PlaceholderHomework 1 Introduction to Cryptography
Open chat
Need help?
Can we help?