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 a 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 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?