Could someone explain why it's necessary to have the modulo operation in the Diffie-Hellman key exchange?

Let's imagine we do DH without the modulo operation ($A = g^a, B = g^b$). Would that not work, because the logarithm ($a = \log_gA$) is easy to calculate? And why does the modulo operation have to be done with a prime?

I know it's a basic question, sorry. I understand the protocol, but not the maths around what is easy to calculate and what isn't. I guess we need $A = g^a \bmod p$ instead of just plain $A = g^a$, because $\log_gA \bmod p$ is very hard to calculate... would it be easy to calculate it without the $\bmod p$?

Many thanks in advance.

  • 1
    $\begingroup$ You can't sample uniformly at random from an infinite set (among other things). $\endgroup$ – SEJPM Aug 9 '17 at 10:15
  • $\begingroup$ @SEJPM DH doesn't really require uniformly random sampling. Typically you a ~256 bit private key together with a 2048-bit safe-prime. $\endgroup$ – CodesInChaos Aug 10 '17 at 20:07

Would that not work, because the logarithm ($a=\log_gA$) is easy to calculate?

Yes, among other things.

  • We know how to efficiently calculate the logarithm over real numbers (thus this would bear no security).
  • We can't sample uniformly at random from an infinite range (all natural numbers), that means you can't randomly draw a natural number because every single one will have $0$ probability of being drawn. This makes key-generation hard (yes one could technically limit the length here).
  • We can't store, let alone transmit, such large numbers. For example assume $g=3$ and now pick a standard-size DH exponent $a$ which has 2048-bit length. $g^a$ will now have $1.5\cdot 2^{2048}$ bit length. We can't store that. We can't even count to $2^{192}$ realistically (with counting being easier than storing).

And why does the modulo operation have to be done with a prime?

There are a few reasons (why to prefer primes):

  • It gives us nice mathematical properties. $\mathbb F_p$ is a field, that is every element has a multiplicative inverse, whereas $\mathbb Z_n$ is a ring where not every element has a multiplicative inverse.
  • It prevents backdoors. If you pick a composite value, the person who knows the factors will have a significantly easier time to compute the logarithm. Picking a prime ensures there's no doubt about anybody knowing any factors if you re-use parameters.
| improve this answer | |
  • $\begingroup$ Why would you use >256 bits for the DH exponent $a$? (What standards do that?) $\endgroup$ – Squeamish Ossifrage Aug 10 '17 at 19:29
  • 1
    $\begingroup$ @SqueamishOssifrage While I prefer 256 bit exponents, some prefer to use the full range up to the order because it relies on a weaker hardness assumption (though in this case it's not helpful, since we don't operate in a finite group). See Diffie-Hellman, random number size. $\endgroup$ – CodesInChaos Aug 10 '17 at 20:48

One of the reasons we do operations modulo a prime $p$ is because it enables us to have a group structure where every element $x < p$ will have an inverse $x^\prime$ such that $xx^\prime \equiv 1 \pmod{p}$. We also have efficient algorithm to compute $x^d \pmod{p}$.

Another reason is that $x^d$ with a $d$ of a large size would be impossible to compute as the result would have many digits. For example, a big number $x \approx 2^{256}$ to the power $d \approx 2^{256}$ would be $256*2^{256}$ bits long which is impossible to store let alone compute.

Edit: took into account the comment

| improve this answer | |
  • 1
    $\begingroup$ Actually it's physically impossible to count to $2^{256}$, let alone store that many entries... $\endgroup$ – SEJPM Aug 10 '17 at 18:57

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.