modfied man in the middle attack diffie hellman

Question

I have been given a problem in preparation for my cryptography final that I'm not sure how to solve. It asks me to suppose a scenario where instead of where an attacker would intercept some message from Alice ($g^a$) mod p and ($g^b$) mod p from bob, and then replacing each of these with $g^e$, the attacker would replace it with $g^q$ where $p=mq+1$, $p$ is the large prime upon which Alice and bob have agreed, $m$ is a small even number, and $q$ is another prime.

1. Why are there exactly $m$ values for $k$?
2. Why is this attack any better than the attacker simply raising $g$ to their own value ($e$)?

Answer 1

Why are there exactly $m$ values for $k$?

Well, assuming $k$ is the value of the shared secret that either Alice and Bob derive, well, that's not true; there are at most $m$ possible values, however it may be fewer. There will be exactly $m$ values if $g$ is a primitive root modulo $p$; however when we use Diffie-Hellman in practice, we generally avoid using a primitive root.

To understand why there are at most $m$ possible values, we need to look at Fermat's Little Theorem; one way of expressing it is:

$g^x \equiv g^{x \ \bmod\ p-1} (\bmod\ p)$

(This isn't the standard way of writing it; this formulation works out fairly well for this purpose).

The other thing to look at the Diffie-Hellman operation with the modified messages, where Alice computes:

$k = g^{aq} (\bmod\ p)$

And we ask ourselves "how many distinct values can $aq \bmod\ p-1$ take on?" (Hint: consider the Chinese Remainder Theorem).

You're supposed to be learning, hence I'm not giving you the full answer; I hope these hints are enough for you to fill in the missing pieces.

Why is this attack any better than the attacker simply raising $g$ to their own value $e$?

Well, in practice, it won't be any better; any secure protocol that uses Diffie-Hellman must have a story why an attacker who modifies the messages cannot gain an advantage; such protection will foil both attacks.

However, I believe the answer they're looking for starts with "if the attacker replaces both values with his own value $g^e$, then both sides will always derive different shared secrets (and hence different session keys); to continue the attack, the attacker must decrypt each sides messages, and reencrypt them with the keys shared with the other side. However, if the attacker replaces both values with $g^q$, then with probability $\ge 1/m$, [fill in details here]