4
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ You can't sample uniformly at random from an infinite set (among other things). $\endgroup$
    – SEJPM
    Aug 9, 2017 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$ Aug 10, 2017 at 20:07
  • $\begingroup$ watch this series of short videos: youtube.com/playlist?list=PLP6PHJ8SLR6AA93UEXGaDFUDc8paCCsiD $\endgroup$
    – M3RS
    Jan 10, 2021 at 17:41

2 Answers 2

7
$\begingroup$

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.
$\endgroup$
5
  • $\begingroup$ Why would you use >256 bits for the DH exponent $a$? (What standards do that?) $\endgroup$ Aug 10, 2017 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$ Aug 10, 2017 at 20:48
  • $\begingroup$ "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}$? $\endgroup$ Dec 21, 2021 at 9:42
  • 1
    $\begingroup$ @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). $\endgroup$
    – SEJPM
    Dec 21, 2021 at 15:09
  • $\begingroup$ @SEJPM: Indeed, I missed the base number. Thanks for clearing that up. $\endgroup$ Dec 22, 2021 at 9:39
2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.