I'd like to have a small sanity check first: As far as I understand, diffie-hellman is all about that fact that, given the generator ($g$), the modulo ($n$) and the remainder ($c$), it's hard to find the exponent a in:

$g^a \bmod n = c$

But the conditions for this are that n is a big prime number, and g is a root primitive. So my questions are:

  1. Does $n$ must be prime? or it's just better for security?
  2. Does $g$ must be root primitive mod $n$?

Ok now to RSA. As far as I understand, RSA stands on another notion, and that is that it's hard to find the message (m) given the cipher (c), modulo (n) and exponent (e) in:

$m^e \bmod n = c$

So my question is: Does the same restrictions regarding diffie-hellman apply to RSA? Seemingly that's not possible since:

  1. you can't impose restrictions on the message itself
  2. $n$ is a composite of two (or more) prime numbers.

Am I right here? Please correct me if not.

I suppose that my questions comes down to this: Do Diffie-Hellman and RSA rely on the same mechanism of modular arithmetic, or is it completely different?

  • 1
    $\begingroup$ DH relies on the Discrete Logarithm Problem (DLP), RSA on the RSA problem. Both use modular exponentiation. What's your question exactly? You need to study DH and RSA at least in some depth before trying to ask questions about it. Note that there are two "are"'s in your question title. $\endgroup$
    – Maarten Bodewes
    Jan 27, 2021 at 15:22
  • 1
    $\begingroup$ I removed the incorrect use of$\pmod n$ where $\bmod n$ was thought. $x\bmod n$ is the uniquely defined integer $y$ with $0\le y<n$ and $x-y$ a multiple of $n$. Whereas $x\pmod n$ is not an integer, and $y\equiv x\pmod n$ only states that $y-x$ is a multiple of $n$, without specifying a range of $y$. The difference is important in both Diffie-Hellman and RSA. $\endgroup$
    – fgrieu
    Jan 27, 2021 at 15:40
  • $\begingroup$ Related question: Is Diffie-Hellman mathematically the same as RSA?. Dupe, perhaps! $\endgroup$
    – fgrieu
    Jan 27, 2021 at 15:43
  • 1
    $\begingroup$ It's also generally misleading to think of the $m$ in RSA as a "message". It can be in some cases (OAEP-padding of a symmetric key for key exchange, though even then it's not the true "message" that eventually gets encrypted with that key) but often isn't (signatures, some random integer for RSA-KEM). Signatures are a lot more common as a use of RSA than RSA-OAEP for key exchange. $\endgroup$ Jan 27, 2021 at 15:48
  • $\begingroup$ Also, we generally don't use a primitive root as a generator for DH, but a number which generates a large prime order subgroup. $\endgroup$ Jan 28, 2021 at 3:44


Your Answer

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

Browse other questions tagged or ask your own question.