2
$\begingroup$

I'm trying to understand why the secret keys used by Alice and Bob in Diffie-Hellman are $a,b ∈ ℤ∗p$.

Say $a$ is $p - 1$, wouldn't the transmitted $g^a$ be 1 mod $p$ by $FLT$? Now anytime a passive listener sees a 1 being transmitted would know one of the secret keys and could easily compute the message. I'm sure I'm missing something obvious but I can't figure it out.

$\endgroup$
3
$\begingroup$

The "obvious" (it really isn't that obvious) thing you are missing is: The same reasoning could be applied to literally any other private key! There is nothing special about $a=\lvert(\mathbb Z/p\mathbb Z)^\times\rvert=p-1$ (which would, by the way, more commonly be represented as $0$ modulo itself), except that checking for it is particularly easy. For instance, if an attacker suspects that your private key is $42$, they can simply compute $g^{42}\bmod p$ and compare it to the public key $g^a\bmod p$ you transmitted. Does this imply that $42$ is a weak private key?

The reason why Diffie-Hellman (and in fact, similar fallacies apply to any cryptosystem) can still be secure is that the probability of each single key occurring is negligible. An attacker can test whether your private key equals something, but it takes a certain amount of time (a bit less for $a=0$, but still). When the set of possible keys is reasonably large, the attacker can't search through a meaningful subset of in their lifetime, hence they will, with overwhelming probability, not be able to guess the correct private key.

$\endgroup$
1
$\begingroup$

While there is nothing special about most key values, the public key 1 is actually not permitted. It would result in the same shared secret 1 with every other key, because $1^x = 1$ for any private key $x$. When using public key validation, the key is checked to be in the range $[2, p-1]$. This is ensured if the private key is chosen from $[2, q-2]$.

For other "special" values, like 42, the logic from @yyyyyyy's answer applies.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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