3
$\begingroup$

I am currently learning about the Diffie-Hellman key exchange. I understand that for a $g$ of $1$, the resulting key would always end up as $1$ which would obviously not be secure.

I read that the $p\! -\! 1$ value for $g$ is not secure either, but there is no explanation as to why - which is my question. I guess it has to do with $g$ being a divisor of $p\! -\! 1$ but I am not sure.

$\endgroup$
  • 1
    $\begingroup$ Oh, this talk about the generator $g$. A generator with low order will not be secure. that is why one considers the safe primes for the modulus. $\endgroup$ – kelalaka Feb 26 at 19:18
  • $\begingroup$ Note: I rolled back to an earlier revision because revision 7 had little to do with the initial question, and was overly general. $\endgroup$ – fgrieu Mar 3 at 17:51
8
$\begingroup$

If $g=p-1$ then $g\equiv -1\pmod p$ that is $g$ is effectively the same as $-1$ which has the obvious drawback that $g^x$ can only ever be $+1$ or $p-1$ which is easily brute-forcable.


Here's a short proof sketch of the above exponentiation statement:

\begin{align} (p-1)^2\bmod p &= (p^2-2p+1)\bmod p \\ &=(p^2\bmod p)-(2p\bmod p)+(1\bmod p)\\ &= 0-0+1\\ \end{align}

So when you have $(p-1)^x\bmod p$ this is the same as $(p-1)^{2y}\cdot(p-1)^{z}\bmod p$ for $x=2y+z$ and $z\in \{0,1\}$ which is $((p-1)^2)^y\cdot (p-1)^{z}\bmod p=1^y\cdot (p-1)^{z}$ which is either $p-1$ or $1$.

$\endgroup$
  • 1
    $\begingroup$ $(p-1)^n = \sum_{k=0}^n {n \choose k}p^{n-k}(-1)^k = (-1)^n + p\sum_{k=0}^{n-1} {n \choose k}p^{n-k-1}(-1)^k$, that is, the last term of the sum (when $k = n$) is the only one that is not a multiple of $p$, as a consequence, $(p-1)^n \mod p = (-1)^n$. $\endgroup$ – Hilder Vitor Lima Pereira Feb 26 at 16:51
  • 1
    $\begingroup$ @JohnMichaels that is modular arithmetic. Normally, It is an equivalence class and each element is represented by $[0],[1],[2],\ldots,[p-1]$. For convenience, the square brackets are removed. You can freely choose any element to represent the equivalence class and using $-1$ in some situations is very helpful instead of $p-1$. to see that $-1$ has is in the same equivalence class, just add $p$ there you will see that that it is $p-1$, also $2p-1$, i.e. $-1 \equiv p-1 \equiv 2p-1 \pmod p$ $\endgroup$ – kelalaka Feb 26 at 17:58

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.