Problem 4-A modified man-in-the-middle attack on Diffie-Hellman (10 marks) Suppose Alice and Bob wish to generate a shared cryptographic key using the Diffie-Hellman protocol. As usual, they agree on a large prime p and a primitive root g of p. Suppose also that p = mg + 1 where q is prime and m is very small (10 p-1 = mq has a large prime factor, as is generally required). Since g and p are public, it is easy for anyone to deduce m and q; for example by successively trial-dividing p - 1 by m = 2,4,6,... and running a primality test such as the Fermat test on the quotient q = (p-1)/m until primality of is established. Suppose an active attacker Mallory intercepts g (mod p) from Alice and go (mod p) from Bob. She sends (94) (mod p) to Bob and (g) (mod p) to Alice. a. (2 marks) Show that Alice and Bob compute the same shared key K under this attack. b. (4 marks) Show that there are m possible values for K, and that Mallory can compute them all and hence easily guess the correct key K among them. c. (4 marks) What is the advantage of this variation of the man-in-the-middle attack over the version we discussed in class? Recall that for the attack from class, Mallory simply suppresses the messages g (mod p) and g (mod p) between Alice and Bob and replaces them with her own number 9 (mod p), which results in the shared key gas (mod p) between Mallory and Alice and the shared key (mod p) between Mallory and Bob