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 Malloryintercepts g (mod p) from Alice and g (mod p) from Bob. She sends (94)9 (mod p) to Bob and (g) (mod p) to Alice. 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 gle (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 Malloryintercepts g (mod p) from Alice and g (mod p) from Bob. She sends (94)9 (mod p) to Bob and (g) (mod p) to Alice. 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 gle (mod p) between Mallory and Alice and the shared key gbe (mod p) between Mallory and Bob