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= mq +1 where q is prime and m is very small (so 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 q is established. Suppose an active attacker Mallory intercepts g (mod p) from Alice and g (mod p) from Bob. She sends (g)! (mod p) to Bob and (9) (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 g (mod p), which results in the shared key gae (mod p) between Mallory and Alice and the shared key gbe (mod p) between Mallory and Bob. 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= mq +1 where q is prime and m is very small (so 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 q is established. Suppose an active attacker Mallory intercepts g (mod p) from Alice and g (mod p) from Bob. She sends (g)! (mod p) to Bob and (9) (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 g (mod p), which results in the shared key gae (mod p) between Mallory and Alice and the shared key gbe (mod p) between Mallory and Bob