# Diffie-Hellman key exchange - why is modulo operation necessary?

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$?

• You can't sample uniformly at random from an infinite set (among other things). – SEJPM Aug 9 '17 at 10:15
• @SEJPM DH doesn't really require uniformly random sampling. Typically you a ~256 bit private key together with a 2048-bit safe-prime. – 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.
• Why would you use >256 bits for the DH exponent $a$? (What standards do that?) – Squeamish Ossifrage Aug 10 '17 at 19:29
• @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. – 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

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