Is Diffie-Hellman mathematically the same as RSA? 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.


Bob makes an fresh RSA key pair and sends his public key to Alice.
Alice makes a random session key and sends it to Bob encrypted with Bob's public key.
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 Hiffie 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 Hiffie Hellman and RSA. Which make me wonder: Are they really the same thing?

Can we algebraically prove that the correctness of RSA implies the correctness
of Diffie-Hellman?
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.)