# What's the fundamental difference between Diffie-Hellman and RSA?

What is the difference in the purpose of DH and RSA? Aren't they both public-key encryption?

-
This other question seems nearly identical. – B-Con Jun 12 '12 at 16:07
@B-Con: Actually, it misses the precise point I was trying to make with this post. :) Notice the word "mathematical" in the title -- that was specifically not the real goal of my question/answer here, because I already knew that they're different mathematically (they're different algorithms, after all). :P (See my comment on my answer below.) – Mehrdad Jun 12 '12 at 16:09

The difference is subtle.
DH is used to generate a shared secret in public for later symmetric ("private-key") encryption:

### Diffie-Hellman:

• Creates a shared secret between two (or more) parties, for subsequent symmetric encryption
• Key identity: (gens1)s2 = (gens2)s1 = shared secret   (mod prime)
• Where:

• gen is an integer whose powers generate all integer in [1, prime)   (mod prime)
• s1 and s2 are the individuals' "secrets", only used to generate the symmetric key

RSA is used to come up with a public/private key pair for asymmetric ("public-key") encryption:

### RSA:

• Used to perform "true" public-key cryptography
• Key identity: (me)d = m   (mod n)   (lets you recover the encrypted message)
• Where:

• n = prime1 × prime2    (n is publicly used for encryption)
• φ = (prime1 - 1) × (prime2 - 1)   (Euler's totient function)
• e is such that 1 < e < φ, and (e, φ) are coprime    (e is publicly used for encryption)
• d × e = 1   (mod φ)    (the modular inverse d is privately used for decryption)

It just so happens that -- in practice -- RSA's results are subsequently used to generate a symmetric key.
Furthermore, it also happens that you can also modify DH to be used for public-key encryption.
But they are fundamentally different, even though both of them have "public" and "private" components.

-
Hmm, this is about the difference from the outside (i.e. the interface), i.e. the difference between key exchange and public key encryption. When asked about the fundamental difference, I would think more about the number-theoretic principles behind them (RSA: discrete root, factorization, DH/DSA/...: discrete logarithm Diffie-Hellman assumption). – Paŭlo Ebermann Jun 11 '12 at 19:26
@PaŭloEbermann: That's definitely a valid answer to the question -- but the issue was that I had a harder time coming up with the question than the answer haha, since wasn't looking for the mathematical difference so much as the nature of their difference. I was looking for someone to explain this^ concept, so when I found it out myself I just wrote a question for it so I could write the answer too. :) If you can think of a better way to phrase the question to match the answer then I'd love to know! – Mehrdad Jun 11 '12 at 20:02

Yes, they're both public key systems. The difference in the way that you're asking is that Diffie-Hellman relies on the hardness of taking logarithms (actually discrete logs, but just don't worry about that for now). RSA relies on the hardness of factoring.

Interestingly, the two problems are related. There are mathematical theorems that say that a structural problem in one means there's a structural problem in the other. But they are two distinct families of public key crypto, the logarithm family and the factoring family.

Elliptic curve crypto, by the way, is just logarithm-family crypto on a different finite field than modular arithmetic. If that just sailed over your head, I can explain later.

Jon

-
I would suppose this is related to the mathematical difference. Do you care to elaborate on the protocol differences? – d-_-b Aug 13 '13 at 6:14