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?
2 Answers
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.
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.
-
$\begingroup$ @otus yes you are right, the first equation was wrong. $\endgroup$ 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$– SEJPMNov 25, 2015 at 20:47
-
$\begingroup$ @SEJPM, how do you know $p$ was meant, generation of the secret should really use $q$? $\endgroup$– otusNov 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$– SEJPMNov 26, 2015 at 16:18