Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$)?
share|improve this question

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]

share|improve this answer
That second part was what I've come up with so far. But I have no idea how to show that aq mod p can actually only take on m values. Shouldn't it be able to take on a mod p values? – user979616 Nov 13 '13 at 17:29
@user979616: Again, consider the Chinese Remainder Theorem, with $p-1 = mq$; and how many distinct values can $aq \bmod m$ take on, and how many distinct vlaues can $aq \bmod q$ take on? – poncho Nov 13 '13 at 17:31
aq mod m should only be able to take on m values correct? The Chinese remainder theorem talks about solving a system of equations. I seem to be missing why its applicable here. – user979616 Nov 13 '13 at 17:36
@user979616: If $a$ and $b$ are relatively prime, and $x$ is an unknown value that is within a known set, and $x \bmod a$ can take on $c$ different values, and $x \bmod b$ can take on $d$ different values, how many values can $x \bmod ab$ take on? – poncho Nov 13 '13 at 17:44
My assumption is that it takes on the smaller of the two, since that would give me that aq mod(qm) takes on m values, which is what I require. Thanks so much for the help :). – user979616 Nov 13 '13 at 17:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.