2
$\begingroup$

I just started learning Diffie-Hellman Key Exchange. I couldn't get the reason of making $\alpha$ and private key for Alice and Bob constrained between $2$ and the prime number generated minus $2$ (=$p-2$). Why should it be $2$ less than the prime? Is there a specific reason for this?

$\endgroup$
0

2 Answers 2

2
$\begingroup$

The reason for both is that the generated values are trivial to detect / exploit and should be avoided and your RNG is deeply flawed if you actually get those values because the chance for this lies around $2^{-2000}$ if you use an appropriate parameter set.


Now for the math:
You need to choose your secret exponent $x$ such that $1\leq x\leq p-2$, with $p$ being the prime defining the multiplicative Field $\mathbb Z_p^*$. Your generator $\alpha$ needs to be chosen such that $2\leq \alpha \leq p-2$. The source for these constraints is the famous Handbook of Applied Cryptography, 1996, Menezes et al (page 516).

The constraints for the secret exponent apply because $\alpha^0$ meaning $x=0$ is $1$ and thereby fully insecure. If you use $p-1$, Fermat's little theorem applies and you get $\alpha^{p-1}\equiv 1\pmod p$ which is also trivially insecure. You can't get any value beyond $p-1$ because you can reduce those $\bmod (p-1)$ which allows you to reduce $p-1$ to $0$, $p$ to $1$ and so on.

As for the generator, you want to have one that generates a large group (via exponentiation) and this trivially excludes $1$ and $0$ which will you only ever give the sets $\{0\}$ and $\{1\}$ respectively. So they are a really bad choice for $\alpha$. You also can't chose $\alpha=p$ because you can then reduce this every time $\alpha=0$ as all operations are carried out $\bmod p$. Now what about $\alpha=p-1$ (the last edge case)? First you need to note that $p-1\equiv -1 \pmod p$ and if you exponentiate that you'll only get $(p-1)^x \equiv (-1)^x \equiv \pm 1 \pmod p$ which is the set $\{1,p-1\}$ and thereby a really bad choice.

$\endgroup$
0
$\begingroup$

Because $a^{p-1} \equiv 1 \mod p$ and $a^{p-2} \equiv a^{-1} \mod p$.

In both cases it is easy to solve for the exponent.

$\endgroup$
4
  • $\begingroup$ @otus yes you are right, the first equation was wrong. $\endgroup$
    – user13741
    Nov 25, 2015 at 20:33
  • 1
    $\begingroup$ @otus, Actually, $p-2$ is allowed as value and not so much of a problem. And he is indeed referring to $p$ and not $q$ (= the group's order). And user13741 you didn't answer the part about why $\alpha$ should be $2\leq \alpha \leq p-2$ $\endgroup$
    – SEJPM
    Nov 25, 2015 at 20:47
  • $\begingroup$ @SEJPM, how do you know $p$ was meant, generation of the secret should really use $q$? $\endgroup$
    – otus
    Nov 26, 2015 at 9:13
  • $\begingroup$ @otus, because using $p$ is the most common notation for constraining the secret exponent and this matches perfectly with what is described in the HAC. $\endgroup$
    – SEJPM
    Nov 26, 2015 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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