Is there a way to prevent the shared secret to be a small value (eg 4) to avoid easily succeeding brute force attacks?

In $g^a \bmod p$, I understand that choosing $p$ not a multiple of $g^a$ is a first step. But other than that, are there fast ways to achieve that goal?


  • 1
    $\begingroup$ By the same reasoning, all possible shared secrets are insecure: What if an attacker simply guesses that $g^{ab}\bmod p$ lies in a certain "small" range and brute-forces that range? $\endgroup$ – yyyyyyy Jan 25 '19 at 17:04
  • $\begingroup$ You are perfectly right $\endgroup$ – Kroma Jan 28 '19 at 7:05
  • 1
    $\begingroup$ Note that excluding a certain range of values from potential secrets will reduce the entropy of the secret and hence make brute forcing easier. Values from the excluded range of values will not have to be tested. $\endgroup$ – JimmyB Jan 28 '19 at 9:02
  • $\begingroup$ @JimmyB correct! $\endgroup$ – Kroma Jan 30 '19 at 12:27
  1. $p$ is a prime number and $g^a\bmod p$ will fall between $[1, p-1]$, so $p$ will never be a multiple of $g^a \bmod p$ unless $g^a= 1\bmod p$.
  2. In Diffie Hellman, the secret exponents $a,b$ are chosen uniformly and randomly from $[1,q-1]$, where $q$ is a very large number. The probability that $Pr[g^{ab} = 4]$ or more generally $Pr[g^{ab} = x]$ for any $x$ in the group is negligible. This implies that for any integer $y=poly(n)$ where $n$ is the security parameter and $poly(\cdot)$ is any polynomial, $Pr[g^{ab} \le y]$ is negligible as well. So you don't need to worry about the key being a small value.
| improve this answer | |
  • $\begingroup$ Ok thanks! Since we cannot do anything against a very lucky attacker, it will do! $\endgroup$ – Kroma Jan 25 '19 at 12: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.