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

Question

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

Answer 1

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: (gen^s₁)^s₂ = (gen^s₂)^s₁ = shared secret   (mod prime)

• Where:

  • gen is an integer whose powers generate all integer in [1, prime)   (mod prime)
  • s₁ and s₂ 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: (m^e)^d = m   (mod n)   (lets you recover the encrypted message)

• Where:

  • n = prime₁ × prime₂    (n is publicly used for encryption)
  • φ = (prime₁ - 1) × (prime₂ - 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.

Answer 2

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