Alice is learning about the shift cipher. She chooses a random three-letter word (so all three-letter words in the dictionary have the same probability) and encrypts it using a shift cipher with a randomly chosen key (that is, each possible shift has probability 1/26). Eve intercepts the ciphertext mxp.

1. Compute $P(M=cat\mid C=mxp)$. (Hint: Can mxp shift to cat?)

2. Use your result from part (a) to show that the shift cipher does not have perfect secrecy (this is also true because there are fewer keys than ciphertexts; see the proposition at the end of the first section).

Alice is learning more advanced techniques for the shift cipher. She now chooses a random five-letter word (so all five-letter words in the dictionary have the same probability) and encrypts it using a shift cipher with a randomly chosen key (that is, each possible shift has probability 1/26). Eve intercepts the ciphertext evire. Show that

(Hint: Look at Exercise 1 in Chapter 2.)

Suppose a message $m$ is chosen randomly from the set of all five-letter English words and is encrypted using an affine cipher mod 26, where the key is chosen randomly from the 312 possible keys. The ciphertext is $HHGZC$. Compute the conditional probability $\text{Prob}(m=HELLO\mid c=HHGZC)$. Use the result of this computation to determine whether of not affine ciphers have perfect secrecy.

Alice is learning about the Vigenère cipher. She chooses a random six-letter word (so all six-letter words in the dictionary have the same probability) and encrypts it using a Vigenère cipher with a randomly chosen key of length 3 (that is, each possible key has probability $1/{26}^3$). Eve intercepts the ciphertext eblkfg.

1. Compute the conditional probability $P(M=attack\mid C=eblkfg)$.

2. Use your result from part (a) to show that the Vigenère cipher does not have perfect secrecy.

Alice and Bob play the following game (this is the CI Game of Section 4.5). Alice chooses two two-letter words $m_0$ and $m_1$ and gives them to Bob. Bob randomly chooses $b=0$ or 1. He encrypts $m_b$ using a shift cipher (with a randomly chosen shift) to get a ciphertext $c$, which he gives to Alice. Alice then guesses whether $m_0$ or $m_1$ was encrypted.

1. Alice chooses $m_0=HI$ and $m_1=NO$. What is the probability that Alice guesses correctly?

2. Give a choice of $m_0$ and $m_1$ that Alice can make so that she is guaranteed to be able to guess correctly.

Bob has a weak pseudorandom generator that produces $N$ different $M$-bit keys, each with probability $1/N$. Alice and Bob play Game R. Alice makes a list of the $N$ possible pseudorandom keys. If the number $r$ that Bob gives to her is on this list, she guesses that the number is chosen pseudorandomly. If it is not on the list, she guess that it is random.

1. Show that

   $$P(r\text{ is on the list}\mid r\text{ is random})={\displaystyle \frac{N}{2^M}}$$

   and

   $$P(r\text{ is on the list}\mid r\text{ is pseudorandom})=1.$$

2. Show that

   $$\begin{array}{rl}& P(r\text{ is random}\bigcap r\text{ is on the list})={\displaystyle \frac{1}{2}}\left({\displaystyle \frac{N}{2^M}}\right)\\ & P(r\text{ is random}\bigcap r\text{ is not on the list})={\displaystyle \frac{1}{2}}\left(1-{\displaystyle \frac{N}{2^M}}\right)\\ & P(r\text{ is pseudorandom}\bigcap r\text{ is on the list})={\displaystyle \frac{1}{2}}\\ & P(r\text{ is pseudorandom}\bigcap r\text{ is not on the list})=0.\end{array}$$

3. Show that Alice wins with probability

   $${\displaystyle \frac{1}{2}}\left(1-{\displaystyle \frac{N}{2^M}}\right)+{\displaystyle \frac{1}{2}}\text{.}$$

4. Show that if $N/2^M=1-ϵ$ then Alice wins with probability ${\displaystyle \frac{1}{2}}+{\displaystyle \frac{1}{2}}ϵ$. (This shows that if the pseudorandom generator misses a fraction of the possible keys, then Alice has an advantage in the game, provided that she can make a list of all possible outputs of the generator. Therefore, it is necessary to make $N$ large enough that making such a list is infeasible.)

Suppose Alice knows that Bob’s pseudorandom key generator has a slight bias and that with probability 51% it produces a key with more 1’s than 0’s. Alice and Bob play the CI Game. Alice chooses messages $m_0=000\cdots 0$ and $m_1=111\cdots 1$ to Bob, who randomly chooses $b\in \{0\text{,}1\}$ and encrypts $m_b$ with a one-time pad using his pseudorandom key generator. He gives the ciphertext $c=m_b\oplus r$ (where $r$ is his pseudorandom key) to Alice. Alice computes $s=c\oplus m_0$. If $s$ has more 1’s than 0’s, she guesses that $b=0$. If not, she guesses that $b=1$. For simplicity in the following, we assume that the message lengths are odd (so there cannot be the same number of 1’s and 0’s).

1. Show that exactly one of $m_0\oplus r$ and $m_1\oplus r$ has more 1’s than 0’s.

2. Show that $P(s\text{ has more 1's}\mid b=0)=.51$

3. Show that $P(s\text{ has fewer 1's}\mid b=1)=.51$

4. Show that Alice has a probability .51 of winning.

In the one-time pad, suppose that some plaintexts are more likely than others. Show that the key and the ciphertext are not independent. That is, show that there is a key $k$ and a ciphertext $c$ such that

(Hint: The right-hand side of this equation is independent of $k$ and $c$. What about the left-hand side?)

Alice and Bob are playing the R Game. Suppose Alice knows that Bob’s pseudorandom number generator always has a 1 at the beginning of its output. If Alice sees this initial 1, she guesses that the output is from the pseudorandom generator. And if this 1 is not present, Alice knows that $r$ is random. Show that Alice guesses correctly with probability 3/4.

Suppose Bob uses a pseudorandom number generator to produce a one-time pad, but the generator has a slight bias, so each bit it produces has probability 51% of being 1 and only 49% of being 0. What strategy can Alice use so that she expects to win the CI Game more than half the time?

At the end of the semester, the professor randomly chooses and sends one of two possible messages:

To add to the excitement, the professor encrypts the message using one of the following methods:

1. Shift cipher

2. Vigenère cipher with key length 3

3. One-time pad.

You receive the ciphertext and want to decide whether the professor sent $m_0$ or $m_1$. For each method (a), (b), (c), explain how to decide which message was sent or explain why it is impossible to decide. You may assume that you know which method is being used. (For the Vigenère, do not do frequency analysis; the message is too short.)

On Groundhog Day, the groundhog randomly chooses and sends one of two possible messages:

To add to the mystery, the groundhog encrypts the message using one of the following methods: shift cipher, Vigenère cipher with key length 4 (using four distinct shifts), one-time pad. For each of the following ciphertexts, determine which encryption methods could have produced that ciphertext, and for each of these possible encryption methods, decrypt the message or explain why it is impossible to decrypt.

1. ABCDEFGHIJKLMNOPQRST

2. UKZOQTGYGGMUQHYKPVGT

3. UQUMPHDVTJYIUJQQCSFL.

Alice encrypts the messages $M_1$ and $M_2$ with the same one-time pad using only capital letters and spaces, as in Section 4.3. Eve knows this, intercepts the ciphertexts $C_1$ and $C_2$, and also learns that the decryption of $M_1$ is THE LETTER * ON THE MAP GIVES THE LOCATION OF THE TREASURE. Unfortunately for Eve, she cannot read the missing letter *. However, the 12th group of seven bits in $C_1$ is $1001101$ and the 12th group in $C_2$ is $0110101$. Find the missing letter.