Question

Problem 4 | A modied man-in-the-middle attack on Diffie-Hellman
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^a (mod p) from Alice and g^b (mod p) from Bob.
She sends (g^a)^q (mod p) to Bob and (g^b)^q (mod p) to Alice.

(a) Show that Alice and Bob compute the same shared key K under this attack.

(b) 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) 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^a (mod p) and g^b (mod p) between Alice and Bob and replaces
them with her own number g^e (mod p), which results in the shared key g^ae (mod p) between
Mallory and Alice and the shared key g^be (mod p) between Mallory and Bob.

PLEASE SHOW CLEAR & DETAILED STEPS OF THE SOLUTIONS . THE PROOF SHOULD BE FOR GENERAL CASE, NOT AN EXAMPLE OF AN INDIVIDUAL CASE

Answer 1