35
$\begingroup$

Is the Diffie-Hellman key exchange the same as RSA?

Diffie Hellman allows key exchange on a observed wire – but so can RSA.

Alice and Bob want to exchange a key – Big brother is watching everything.

  1. Bob makes a fresh RSA key pair and sends his public key to Alice.
  2. Alice makes a random session key and sends it to Bob encrypted with Bob's public key.
  3. Bob decrypts the session key with his private key.

Alice and Bob have exchanged a key despite the fact that anybody can observe all the traffic. The maths of RSA and Diffie Hellman are remarkably similar, both involving modular exponentiation.

They both work because $(A*B)^C \bmod N$ can be done in two steps, i.e. by calculating $X = A^C \bmod N$ on one side of the transaction, and $X^B \bmod N$ on the other – this trick is the basis of both Diffie Hellman and RSA. Which makes me wonder: Are they really the same thing?

Can we algebraically prove that the correctness of RSA implies the correctness of Diffie-Hellman?

$\endgroup$

7 Answers 7

31
$\begingroup$

Both RSA and Diffie-Hellman work with modular exponentiation. But they work in a different way:

In RSA, there are two exponentiations which invert each other, i.e. we have $e$ and $d$ such that $(x^e)^d \equiv x$ for all $x$. E.g. if $\square^e$ is the encryption, $\square^d$ is the corresponding decryption. To create this pair of $e$ and $d$ (or derive one from the other), we need the prime factorization of the modulus $m$ (which thus should be private).

In Diffie-Hellman, both the basis $g$ and the modulus $m$ of the exponentiation is fixed. The exponents $x$ and $y$ are randomly chosen private keys, and we use the fact that $(g^x)^y \equiv g^{x\cdot y} \equiv (g^y)^x$, where $g^x$ and $g^y$ are public, while $x$ and $y$ are (and stay) private, and $g^{x·y}$ is the shared secret.

To break RSA, we would have to get $x$ from $x^d$, $m$ and $d$ - this could be called the discrete $d$-th root problem. (The best known way to do this is to factor $m$ to get $e$ ... and if you have $e$, this also can be used to factor $m$).

To break Diffie-Hellman, we have to get $g^{x·y}$ from $g^x$, $g^y$, $m$ and $g$. The best known way to do this would be to get $x$ from $g^x$ or $y$ from $g^y$ (and $m$ and $g$), the so-called discrete logarithm problem. (Incidentially, it is not proven that this is really the best way, i.e. that there is not a faster way to do this.)

$\endgroup$
5
  • $\begingroup$ So... which is stronger? Which is more unlikely to be broken? $\endgroup$
    – Pacerier
    Dec 2, 2014 at 8:21
  • $\begingroup$ @Pacerier as far as I can see, none of them can be reduced to the other. And "likely to be broken" is difficult to estimate for me. $\endgroup$ Sep 24, 2017 at 19:59
  • $\begingroup$ DH can be attacked by Logjam. $\endgroup$
    – mike
    Feb 15, 2018 at 22:54
  • $\begingroup$ @mike DH with a too small modulus can be attacked, but this is the same for RSA with a too small modulus. $\endgroup$ Feb 16, 2018 at 18:32
  • $\begingroup$ "To break RSA, we would have to get $x$ from $x^d$, $m$ and $d$" Is it possible that $d$ should be replaced with $e$ here? Since $e$ is part of the public key used for encryption and $d$ is assumed to be private. $\endgroup$ Jan 31, 2022 at 19:30
21
$\begingroup$

Diffie-Hellman and RSA are distinct and do not use the same "trick".

In Diffie-Hellman, commutativity is used: $(g^a)^b = (g^b)^a$. Both Alice and Bob do two modular exponentiations each (Alice chooses $a$, computes $g^a$ and sends it to Bob, receives $g^b$ from Bob, and finally computes $(g^b)^a$). Security relies on the difficulty of discrete logarithm: given a prime $p$, an integer $g$, and $g^x \mod p$, it is utterly difficult to find $x$.

In RSA, there is no commutativity involved; Alice and Bob do only one modular exponentiation each; computations are not done modulo a prime $p$, but modulo a non-prime $n$. Alice chooses a random $m$, computes $m^e \mod n$ and sends it to Bob; Bob computes $(m^e)^d \mod n$ which is equal to $m$ because $d$ and $e$ have been chosen for this to work. RSA relies on the difficulty of extracting $e$-th roots: given $n$, $e$ and $m^e \mod n$, it is utterly difficult to find $m$ -- unless you know the "magic trap", i.e. $d$ (or the factorization of $n$)(if $n$ was prime, finding $m$ would be easy).

Although both algorithms involve modular exponentiations, they are quite different in how they work, what they provide, and what hard problems they rely on. Note the difference: in discrete logarithm, you have $g$ and $g^x$, and seek $x$; in $e$-th roots, you have $m^e$ and $e$, and seek $m$.

Any asymmetric encryption algorithm (such as RSA) can be used as a key exchange algorithm, in the way you describe (to "exchange" a key, Alice selects a random blob and encrypts it with Bob's public key). SSL/TLS does that. The converse is not true: you cannot generically transform a key exchange algorithm "alone" into an asymmetric encryption algorithm (but you can use the exchanged key with a symmetric encryption algorithm like AES; there again, SSL does that when using Diffie-Hellman).

$\endgroup$
8
$\begingroup$

The mathematical problems behind DH and RSA are similar but not known to be directly related. It is still an open question if an oracle breaking DH can be used to construct another oracle that breaks RSA (or vice versa). It is mostly believed that the two problems are not reducible to each other in poly time.

However, the complexity of the fastest known DH and RSA breaking algorithms are very close. Therefore, both DH and RSA recommended key sizes are the same.

I should add that in the case of Elliptic Curve-DH, there is no better way to solve the DH problem than by generic algorithms and so the key size is much shorter.

$\endgroup$
4
$\begingroup$

DH and RSA are definitely not the same. DH is a key exchange algorithm, RSA an encryption/signing algorithm.

Now as to whether are operate in the the same way in the scenario you describe. They can indeed be used for a similar purpose. However, the operate on a fundamentally different mathematical problem. DH uses DLP (discrete logarithm), trusting on the hardness of finding x when g^x=H and g and H are known. RSA trusts on the prime factorization problem: the hardness of finding p(prime) and q(prime) when n=(p-1)(q-1) is known.

If the DL problem would be solved, making it feasible to compute x in a reasonable time, DH and ElGamal would both be broken. RSA wouldn't, if I'm not mistaken; RSA would suffer when the prime factorization problem would be solved.

For this reason, you cannot use DH to prove RSA or the other way around.

$\endgroup$
3
  • $\begingroup$ Correction: in RSA, $n=(p-1)(q-1)$ (or $lcm(p-1,q-1)$) is not known (it's easy to factor given that value). Instead, the hard problem is determining x given e and $x^e mod pq$; in constrast, one way of attacking DH is to attack the hard problem of determining e given x and $x^e mod p$ $\endgroup$
    – poncho
    Sep 27, 2011 at 16:02
  • $\begingroup$ I think I might be wrong, but I thought I've heard the claim that breaking discrete log breaks/threatens RSA as well. Maybe this should be a question. $\endgroup$ Sep 27, 2011 at 16:29
  • 1
    $\begingroup$ Well, there are two ways that claim may be correct: 1) if you can solve the DLOG problem in a composite modulus, then you can factor that modulus. If your Oracle to solve DLOG works only in a prime modulus, there's no obvious way to use that to factor; 2) a lot of approaches for attacking the DLOG problem can be used (with some changes) to attack the factorization problem (and vica versa). Now, that's not for all known approaches. $\endgroup$
    – poncho
    Sep 27, 2011 at 17:14
4
$\begingroup$

No, they are not the same.

The short answer is that Diffie-Hellman is for negotiating a secret between parties who don't already share one, while RSA uses existing key material to protect data.

It's actually quite a major difference. Both are "security" related, of course, but DH is starting from scratch while RSA is using a system that's already in place.

$\endgroup$
0
3
$\begingroup$

Diffie-Hellman rests on the assumption that discrete log (in the underlying group) is hard. Although DH was originally specified in the multiplicative group of integers modulo a prime, it has since become taken to be the corresponding algorithm in any group where discrete log is assumed to be hard.

RSA security relies on the assumption that the "RSA problem" is hard. The RSA problem is to find the plaintext given only $n$, $e$, and the ciphertext. It is easy to see that an efficient factoring algorithm breaks RSA, but the converse is unknown: ie, if we had an oracle that could efficiently break RSA, could we efficiently factor $n$?.

So these are different assumptions; in particular breaking one does not break the other in any obvious way.

Interestingly, quantum computers break BOTH algorithms via similar techniques (assuming DH is in $Z^*_p$)

$\endgroup$
1
  • 1
    $\begingroup$ Actually, DH relies on the "Diffie-Hellman problem" (given $g^x$ and $g^y$, find $g^{x·y}$, which might be easier than the discrete log problem (and is easier in some groups, I think). $\endgroup$ Jan 18, 2012 at 21:35
0
$\begingroup$

In RSA, Given e such that $\ gcd(e, (p − 1)(q − 1)) = 1 $, and$\ c $ , find$\ m$ such that $\ m^{e} = c \ (mod \ N) $

But in Diffie-Hellman, given b and g such that $\ b^{k} = g $, find k

$\endgroup$
1
  • 1
    $\begingroup$ Actually, for (computational) Diffie-Hellman, it's "given $g, g^a, g^b$, find $g^{ab}$. Now, we don't know of any faster way than solving the discrete log problem, but we also don't know of a proof that there isn't a faster way... $\endgroup$
    – poncho
    Oct 18, 2017 at 16:31

Your Answer

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