Dana and Reuben want to collaboratively write the solutions for the written part of the 376 final, while keeping them secret from the students. As a first step, they decide to use the Diffie-Hellman protocol with a large prime p and generator g to establish a shared key that is known only to them. Dana chooses random at {1,...,p – 1} and sends A = gº mod p to Reuben; similarly, Reuben chooses random b+ {1,...,p-1} and sends B= g mod p to Dana. Then, they each compute k = gab mod p as the shared key. However, unknown to them, a mischievous student, Malcolm, is able to eavesdrop on and also modify all their communications, including the values A, B they send to each other. (This is called a "man-in-the-middle" attack.) Specifically, Malcolm chooses an exponent ce {1,...,p-1}, and replaces both A and B with C = gº mod p. (a) After Malcolm performs the above substitutions, what is the key computed by Dana? What is the key computed by Reuben? Show how Malcolm can compute both of these keys. (b) To privately collaborate, Dana and Reuben plan to encrypt and send their work in progress to each other, using their shared key in an encryption scheme! Such a scheme involves an encryption algorithm Enc and a decryption algorithm Dec. The encryption algorithm takes a key and message, and outputs a ciphertext. The decryption algorithm takes a key and a ciphertext, outputs a message, and satisfies the following property: for all keys k and messages m, Dec(k, Encik, m = m. Describe how Malcolm can read Dana and Reuben's work on the solutions, without being detected. That is, Dana and Reuben should be under the impression that they are communicating privately with each other, with nothing appearing out of the ordinary. c) The week before the exam, Dana and Reuben wake up at 7 a. m. to double check the exam solutions they have written. It just so happens that Malcolm is a night owl and is asleep. As a result, he is not present to intercept and modify Dana and Reuben's messages. Are Dana and Reuben likely to be able to communicate? Will Malcolm be detected? Solution: Because Sanjana receives C (thinking it came from Linh) and has secret exponent a, Sanjana computes ks = C^^ = (gº)a = gạc. Because Linh receives C (thinking it came from Sanjana) and has secret exponent b, Linh computes kL = C = (gº) = gºc. Because Malcolm knows the public values A, B and his secret exponent c, Malcolm can compute both ks = Aº = (gº)° = gac and kl = B° = (gº)° = gbc. Solution: Malcolm knows the encryption and decryption algorithms Enc and Dec (by Kerckhoff's Principle), and can compute both ks and kų as described above. Whenever Sanjana encrypts a message m and sends c = Enc(ks, m) over the network, Malcolm can intercept c and compute the message Dec(ks, c) = m. Then, Malcolm can send d' = Enc(kl, m) to Linh, who will compute Dec(ku, d) = m, thus receiving the message intended for her. Symmetrically, whenever Linh encrypts a message m and sends c = Enc(kl, m), Malcolm can intercept c, compute the message Dec(kl, c) = m, and send d' = Enc(ks, m) to Sanjana. Then Sanjana will compute Dec(ks, c') = m, thus receiving the message intended for her. As long as Malcolm always performs these translation steps, any (encrypted) message sent from Sanjana or Linh will reach the other, and will appear to have been sent directly from the other part. Yet Malcolm will be able to read all of the messages.