Elliptic Curve Diffie-Hellman

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 $E$ which has a generator $G$ and is of order $q$. All calculations are done $\bmod\ q$ if not stated otherwise.

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

Alice now sends her public key $A$ to Bob.

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

Bob sends his public key $B$ to Alice.

Alice then takes Bob’s public key $B$ and multiplies it by her private key $a$ which results in a point $x$ on the curve $E$.

Bob takes Alice’s public key $A$ and multiplies it by his private key $b$ which results in a point $x$ on the curve $E$.

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

The only values Eve can learn are the public keys $A$ and $B$ 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 $aG = A$ and $bG = B$.

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

Security Assumptions

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

Computational Diffie-Hellman

Given $G$, $aG$ and $bG$, it’s infeasible to compute $abG$.

Decisional Diffie-Hellman

Given $G$, $aG$ and $bG$ it’s infeasible to distinguish $abG$ from a random point in $E$.

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 $A$ and $B$ 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 $A$ and $B$). 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.

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.

• Wikipedia - Elliptic Curve Diffie-Hellman
• Nguyen Thoi Minh Quan - Intuitive Advanced Cryptography