Skip to content

Elliptic Curve Diffie-Hellman

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 EE, a generator GG of such curve and a prime number pp.

Next up, Alice samples a random number aa from Zq\mathbb{Z}_q and multiplies it by GG which results in a point on the curve EE we’ll call AA. Her random number aa is her private key which needs to be kept secret while AA is her public key she can share without compromising any security guarantees.

Alice now sends her public key AA to Bob.

Bob does the same what Alice did and ends up with a private key we’ll call bb and a public key BB.

Bob sends his public key BB to Alice.

Alice then takes Bob’s public key BB and multiplies it by her private key aa which results in a point xx on the curve EE.

Bob takes Alice’s public key AA and multiplies it by his private key bb which results in a point xx on the curve EE.

As can be seen, both Alice and Bob derived the same shared secret xx.

The only values Eve can learn are the public keys AA and BB which by their very nature can be publicly shared without revealing any private information.

Elliptic Curve Diffie-Hellman

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 aG=AaG = A and bG=BbG = B.

To derive the shared secret, the observer would need to extract aa and bb to compute abGabG (Note that at the moment it’s unknown if there are other ways to compute abGwithoutextractabG without extract aandandb$ first).

Security Assumptions

There are two major security assumptions that ensure that Elliptic Curve Diffie-Hellman is secure.

Computational Diffie-Hellman

Given GG, aGaG and bGbG, it’s infeasible to compute abGabG.

Decisional Diffie-Hellman

Given GG, aGaG and bGbG it’s infeasible to distinguish abGabG from a random point in EE.

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 AA and BB 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 AA and BB). 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.

Additional Resources