# 6.6 Exercises

1. The ciphertext YIFZMA was encrypted by a Hill cipher with matrix . Find the plaintext.

2. The matrix  mod 26 is not suitable for the matrix in a Hill cipher. Why?

3. The ciphertext text GEZXDS was encrypted by a Hill cipher with a  matrix. The plaintext is solved. Find the encryption matrix .

4. Consider the following combination of Hill and Vigenère ciphers: The key consists of three  matrices, , , . The plaintext letters are represented as integers mod 26. The first two are encrypted by , the next two by , the 5th and 6th by . This is repeated cyclically, as in the Vigenère cipher. Explain how to do a chosen plaintext attack on this system. Assume that you know that three  matrices are being used. State explicitly what plaintexts you would use and how you would use the outputs.

5. Eve captures Bob’s Hill cipher machine, which uses a 2-by-2 matrix  mod 26. She tries a chosen plaintext attack. She finds that the plaintext  encrypts to  and the plaintext  encrypts to . What is the matrix .

6. Alice uses a Hill cipher with a  matrix  that is invertible mod 26. Describe a chosen plaintext attack that will yield the entries of the matrix . Explicitly say what plaintexts you will use.

1. The ciphertext text ELNI was encrypted by a Hill cipher with a  matrix. The plaintext is dont. Find the encryption matrix.

2. Suppose the ciphertext is ELNK and the plaintext is still dont. Find the encryption matrix. Note that the second column of the matrix is changed. This shows that the entire second column of the encryption matrix is involved in obtaining the last character of the ciphertext.

7. Suppose the matrix  is used for an encryption matrix in a Hill cipher. Find two plaintexts that encrypt to the same ciphertext.

8. Let  be integers mod 26. Consider the following combination of the Hill and affine ciphers: Represent a block of plaintext as a pair  mod 26. The corresponding ciphertext  is



Describe how to carry out a chosen plaintext attack on this system (with the goal of finding the key ). You should state explicitly what plaintexts you choose and how to recover the key.

9. Alice is sending a message to Bob using a Hill cipher with a  matrix. In fact, Alice is bored and her plaintext consists of the letter  repeated a few hundred times. Eve knows what system is being used, but not the key, and intercepts the ciphertext. State how Eve will recognize that the plaintext is one repeated letter and decide whether or not Eve can deduce the letter and/or the key. (Note: The solution very much depends on the fact that the repeated letter is , rather than .)

10. Let  denote encryption (for some cryptosystem) with key . Suppose that there are  possible keys . Alice decides to encrypt a message  as follows:

She chooses two keys  and  and double encrypts by computing



to get the ciphertext . Suppose Eve knows Alice’s method of encryption (but not  and ) and has at least two plaintext–ciphertext pairs. Describe a method that is guaranteed to yield the correct  and  (and maybe a very small additional set of incorrect pairs). Be explicit enough to say why you are using at least two plaintext–ciphertext pairs. Eve may do up to  computations.

11. Alice and Bob are arguing about which method of multiple encryption they should use. Alice wants to choose keys  and  and triple encrypt a message  as . Bob wants to encrypt  as . Which method is more secure? Describe in detail an attack on the weaker encryption method.

12. Alice and Bob are trying to implement triple encryption. Let  denote DES encryption with key  and let  denote decryption.

1. Alice chooses two keys,  and , and encrypts using the formula . Bob chooses two keys,  and , and encrypts using the formula . One of these methods is more secure than the other. Say which one is weaker and explicitly give the steps that can be used to attack the weaker system. You may assume that you know ten plaintext–ciphertext pairs.

2. What is the advantage of using  instead of  in Alice’s version?

13. Suppose  and  are two encryption methods. Let  and  be keys and consider the double encryption


1. Suppose you know a plaintext–ciphertext pair. Show how to perform a meet-in-the-middle attack on this double encryption.

2. An affine encryption given by  can be regarded as a double encryption, where one encryption is multiplying the plaintext by  and the other is a shift by . Assume that you have a plaintext and ciphertext that are long enough that  and  are unique. Show that the meet-in-the-middle attack from part (a) takes at most 38 steps (not including the comparisons between the lists). Note that this is much faster than a brute force search through all 312 keys.

14. Let  denote DES encryption with key . Suppose there is a public database  consisting of  DES keys and there is another public database  of  binary strings of length 64. Alice has five messages . She chooses a key  from  and a string  from . She encrypts each message  by computing . She uses the same  and  for each of the messages. She shows the five plaintext–ciphertext pairs  to Eve and challenges Eve to find  and . Alice knows that Eve’s computer can do only  calculations, and there are  pairs , so Alice thinks that Eve cannot find the correct pair. However, Eve has taken a crypto course. Show how she can find the  and  that Alice used. You must state explicitly what Eve does. Statements such as “Eve makes a list” are not sufficient; you must include what is on the lists and how long they are.

15. Alice wants to encrypt her messages securely, but she can afford only an encryption machine that uses a 25-bit key. To increase security, she chooses 4 keys  and encrypts four times:



Eve finds several plaintext–ciphertext pairs  encrypted with this set of keys. Describe how she can find (with high probability) the keys . (For this problem, assume that Eve can do at most  computations, so she cannot try all  combinations of keys.) (Note: If you use only one of the plaintext–ciphertext pairs in your solution, you probably have not done enough to determine the keys.)

16. Show that the decryption procedures given for the CBC and CFB modes actually perform the desired decryptions.

17. Consider the following simplified version of the CFB mode. The plaintext is broken into 32-bit pieces: , where each  has 32 bits, rather than the eight bits used in CFB. Encryption proceeds as follows. An initial 64-bit  is chosen. Then for , the following is performed:



where  denotes the 32 leftmost bits of ,  denotes the rightmost 32 bits of , and  denotes the string obtained by writing  followed by .

1. Find the decryption algorithm.

2. The ciphertext consists of 32-bit blocks . Suppose that a transmission error causes  to be received as , but that  are received correctly. This corrupted ciphertext is then decrypted to yield plaintext blocks . Show that , but that  for all . Therefore, the error affects only three blocks of the decryption.

18. The cipher block chaining (CBC) mode has the property that it recovers from errors in ciphertext blocks. Show that if an error occurs in the transmission of a block , but all the other blocks are transmitted correctly, then this affects only two blocks of the decryption. Which two blocks?

19. In CTR mode, the initial  has 64 bits and is sent unencrypted to the receiver. (a) If  is chosen randomly every time a message is encrypted, approximately how many messages must be sent in order for there to be a good chance that two messages use the same  ? (b) What could go wrong if the same  is used for two different messages? (Assume that the key  is not changed.)

20. Suppose that in CBC mode, the final plaintext block  is incomplete; that is, its length  is less than the usual block size of, say, 64 bits. Often, this last block is padded with a binary string to make it have full length. Another method that can be used is called ciphertext stealing, as follows:

1. Compute .

2. Compute , where  means we take the leftmost  bits.

3. Compute , where  denotes  with enough 0s appended to give it the length of a full 64-bit block.

4. The ciphertext is . Therefore, the ciphertext has the same length as the plaintext.

Suppose you receive a message that used this ciphertext stealing for the final blocks (the ciphertext blocks  were computed in the usual way for CBC). Show how to decrypt the ciphertext (you have the same key as the sender).

21. Suppose Alice has a block cipher with  keys, Bob has one with  keys, and Carla has one with  keys. The only known way to break single encryption with each system is by brute force, namely trying all keys. Alice uses her system with single encryption. But Bob uses his with double encryption, and Carla uses hers with triple encryption. Who has the most secure system? Who has the weakest? (Assume that double and triple encryption do not reduce to using single or double encryption, respectively. Also, assume that some plaintext-ciphertext pairs are available for Alice’s single encryption, Bob’s double encryption, and Carla’s triple encryption.)