Problem
Prof. Volkovich and Jerry want to collaboratively write the solutions for the next homework, 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. Prof. Volkovich chooses a random a ∈ {1, . . . , p - 1} and sends A = ga mod p to Jerry; similarly, Jerry chooses random b ∈ {1, . . . , p - 1} and sends B = gb mod p to Prof. Volkovich. Then, they each compute k = ga•b 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 "Malcolm in the Middle" attack.) Specifically, Malcolm chooses an exponent c ∈ {1, . . . , p - 1}, and replaces both A and B with C = gc mod p.
• Assume that p = 13, g = 8, a = 7, b = 9, and c = 3. What is the shared key value that Prof. Volkovich and Jerry were supposed to compute originally? After Malcolm's substitution, what value does Prof. Volkovich compute? What value does Jerry compute?
• To privately collaborate, Prof. Volkovich and Jerry 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 messagesm, Dec(k, Enc(k, m)) = m.
Describe how Malcolm can read Prof. Volkovich and Jerry's work on the solutions, without being detected. That is, Prof. Volkovich and Jerry should be under the impression that they are communicating privately with each other, with nothing appearing out of the ordinary.