# 4.6 Exercises

1. 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 . (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).

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

3. Suppose a message  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 . Compute the conditional probability . Use the result of this computation to determine whether of not affine ciphers have perfect secrecy.

4. 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 ). Eve intercepts the ciphertext eblkfg.

1. Compute the conditional probability .

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

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

1. Alice chooses  and . What is the probability that Alice guesses correctly?

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

6. Bob has a weak pseudorandom generator that produces  different -bit keys, each with probability . Alice and Bob play Game R. Alice makes a list of the  possible pseudorandom keys. If the number  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



and


2. Show that



3. Show that Alice wins with probability


4. Show that if  then Alice wins with probability . (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  large enough that making such a list is infeasible.)

7. 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  and  to Bob, who randomly chooses  and encrypts  with a one-time pad using his pseudorandom key generator. He gives the ciphertext  (where  is his pseudorandom key) to Alice. Alice computes . If  has more 1’s than 0’s, she guesses that . If not, she guesses that . 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  and  has more 1’s than 0’s.

2. Show that 

3. Show that 

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

8. 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  and a ciphertext  such that



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

9. 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  is random. Show that Alice guesses correctly with probability 3/4.

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

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

You receive the ciphertext and want to decide whether the professor sent  or . 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.)

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

13. Alice encrypts the messages  and  with the same one-time pad using only capital letters and spaces, as in Section 4.3. Eve knows this, intercepts the ciphertexts  and , and also learns that the decryption of  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  is  and the 12th group in  is . Find the missing letter.