# 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). Aug 9, 2017 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. Aug 10, 2017 at 20:07
– M3RS
Jan 10, 2021 at 17:41

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?) Aug 10, 2017 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. Aug 10, 2017 at 20:48
• "We can't store, let alone transmit, such large numbers". Calculating $2^{2048}$ in Python produces 2049 bits: bin(2**2048). While I agree that enumerating each value from 0 to $2^{2048}$ takes too long, I'm pretty sure we can store and transmit more than two kibibytes. Is there something I'm missing in that argument on storing numbers such as $2^{2048}$? Dec 21, 2021 at 9:42
• @MatthiasBraun you're missing an exponentiation there. If you exponentiate $g=3$ with a number of the range of $2^{2048}$ you get a number in the range of $3^{(2^{2048})}$ which is $2^{2048}$ bits long (with us currently being able to store less than $2^{80}$ bits). Dec 21, 2021 at 15:09
• @SEJPM: Indeed, I missed the base number. Thanks for clearing that up. Dec 22, 2021 at 9:39

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 algorithms 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 too 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.