6.6 Exercises – Introduction to Cryptography with Coding Theory, 3rd Edition

6.6 Exercises

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

  2. The matrix 1111 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 2×2 matrix. The plaintext is solved. Find the encryption matrix M.

  4. Consider the following combination of Hill and Vigenère ciphers: The key consists of three 2×2 matrices, M1, M2, M3. The plaintext letters are represented as integers mod 26. The first two are encrypted by M1, the next two by M2, the 5th and 6th by M3. 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 2×2 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 M mod 26. She tries a chosen plaintext attack. She finds that the plaintext ba encrypts to HC and the plaintext zz encrypts to GT. What is the matrix M.

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

    1. The ciphertext text ELNI was encrypted by a Hill cipher with a 2×2 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 1234 is used for an encryption matrix in a Hill cipher. Find two plaintexts that encrypt to the same ciphertext.

  8. Let a, b, c, d, e, f be integers mod 26. Consider the following combination of the Hill and affine ciphers: Represent a block of plaintext as a pair (x, y) mod 26. The corresponding ciphertext (u, v) is

    xyabcd+efuv(mod 26).

    Describe how to carry out a chosen plaintext attack on this system (with the goal of finding the key a, b, c, d, e, f). 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 2×2 matrix. In fact, Alice is bored and her plaintext consists of the letter a 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 a, rather than b, c, .)

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

    She chooses two keys K and L and double encrypts by computing

    c=EK(EK(EL(m)))

    to get the ciphertext c. Suppose Eve knows Alice’s method of encryption (but not K and L) and has at least two plaintext–ciphertext pairs. Describe a method that is guaranteed to yield the correct K and L (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 250 computations.

  11. Alice and Bob are arguing about which method of multiple encryption they should use. Alice wants to choose keys K1 and K2 and triple encrypt a message m as c=EK1(EK2(EK1(m))). Bob wants to encrypt m as c=EK1(EK1(EK2(EK2(m)))). 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 EK denote DES encryption with key K and let DK denote decryption.

    1. Alice chooses two keys, K1 and K2, and encrypts using the formula c=EK1(DK2(EK1(m))). Bob chooses two keys, K1 and K2, and encrypts using the formula c=EK1(EK2(EK2(m))). 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 DK2 instead of EK2 in Alice’s version?

  13. Suppose E1 and E2 are two encryption methods. Let K1 and K2 be keys and consider the double encryption

    EK1, K2(m)=EK11(EK22(m)).
    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 xαx+β (mod 26) 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 EK denote DES encryption with key K. Suppose there is a public database Y consisting of 1010 DES keys and there is another public database Z of 1010 binary strings of length 64. Alice has five messages m1, m2, , m5. She chooses a key K from Y and a string B from Z. She encrypts each message m by computing c=EK(m)B. She uses the same K and B for each of the messages. She shows the five plaintext–ciphertext pairs (mi, ci) to Eve and challenges Eve to find K and B. Alice knows that Eve’s computer can do only 1015 calculations, and there are 1020 pairs (K, B), so Alice thinks that Eve cannot find the correct pair. However, Eve has taken a crypto course. Show how she can find the K and B 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 K1, K2, K3, K4 and encrypts four times:

    c=EK1(EK2(EK3(EK4(m)))).

    Eve finds several plaintext–ciphertext pairs (m, c) encrypted with this set of keys. Describe how she can find (with high probability) the keys K1, K2, K3, K4. (For this problem, assume that Eve can do at most 260 computations, so she cannot try all 2100 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: P=[P1, P2, ], where each Pj has 32 bits, rather than the eight bits used in CFB. Encryption proceeds as follows. An initial 64-bit X1 is chosen. Then for j=1, 2, 3, , the following is performed:

    Cj=PjL32(EK(Xj))Xj+1=R32(Xj)  Cj, 

    where L32(X) denotes the 32 leftmost bits of X, R32(X) denotes the rightmost 32 bits of X, and XY denotes the string obtained by writing X followed by Y.

    1. Find the decryption algorithm.

    2. The ciphertext consists of 32-bit blocks C1, C2, C3, C4, . Suppose that a transmission error causes C1 to be received as C˜1C1, but that C2, C3, C4,  are received correctly. This corrupted ciphertext is then decrypted to yield plaintext blocks P˜1, P˜2, . Show that P˜1P1, but that P˜i=Pi for all i4. 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 Cj, 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 X1 has 64 bits and is sent unencrypted to the receiver. (a) If X1 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 X1 ? (b) What could go wrong if the same X1 is used for two different messages? (Assume that the key K is not changed.)

  20. Suppose that in CBC mode, the final plaintext block Pn is incomplete; that is, its length M 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 Yn1=EK(Cn2Pn1).

    2. Compute Cn=LM(Yn1), where LM means we take the leftmost M bits.

    3. Compute Cn1=EK(Pn||064M)Yn1, where Pn||064M denotes Pn with enough 0s appended to give it the length of a full 64-bit block.

    4. The ciphertext is C1C2Cn1Cn. 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 C1, Cn2 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 250 keys, Bob has one with 240 keys, and Carla has one with 230 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.)