Is Diffie-Hellman mathematically the same as RSA?

Question

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?

Answer 1

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.)

Answer 2

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).

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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$)

Answer 7

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