Table of contents
Open Table of contents
What it is
Elliptic Curve Diffie-Hellman (ECDH) is a mechanism that allows two parties to agree on a shared secret by communicating over an insecure channel.
How it works
Let’s say that Alice and Bob want to derive a shared secret both can use to encrypt and decrypt the messages they send. While communicating, Alice and Bob can only send messages over an insecure channel from which Eve can intercept and read the messages as they’re sent.
As a first step, Alice and Bob need to agree on an Elliptic Curve , a generator of such curve and a prime number .
Next up, Alice samples a random number from and multiplies it by which results in a point on the curve we’ll call . Her random number is her private key which needs to be kept secret while is her public key she can share without compromising any security guarantees.
Alice now sends her public key to Bob.
Bob does the same what Alice did and ends up with a private key we’ll call and a public key .
Bob sends his public key to Alice.
Alice then takes Bob’s public key and multiplies it by her private key which results in a point on the curve .
Bob takes Alice’s public key and multiplies it by his private key which results in a point on the curve .
As can be seen, both Alice and Bob derived the same shared secret .
The only values Eve can learn are the public keys and which by their very nature can be publicly shared without revealing any private information.
Why it works
Because of the discrete logarithm, it’s impossible for an outside observer to obtain the shared secret as the observer only sees and .
To derive the shared secret, the observer would need to extract and to compute (Note that at the moment it’s unknown if there are other ways to compute ab$ first).
There are two major security assumptions that ensure that Elliptic Curve Diffie-Hellman is secure.
Given , and , it’s infeasible to compute .
Given , and it’s infeasible to distinguish from a random point in .
A note on man-in-the-middle attacks
The previous examination assumes that Eve is passively reading messages from the shared, insecure channel. But what if she intercepts the communication between Alice and Bob and swaps and with public keys she generates?
In this case Eve can establish shared secrets with Alice and Bob without them knowing.
To mitigate this problem, Alice and Bob need to authenticate their messages (their public key and ). This can be done by both of them signing their messages before sending them over the wire.
Given that digital signatures are nearly impossible to forge, there’s no way for Eve to execute the aforementioned attack.
But how does Alive or Bob get the key material to validate the signatures on their messages? This is another problem we’ll discuss in a different post.