Elliptic curve Diffie-Hellman key exchange

We have already learned about elliptic curves in simple Weierstrass form over a finite field and the group structure the points of such curve form that we can use all this information to look at some cryptography built on top of this. Going from the point negation, doubling and addition over scalar multiplication and prime order curves with no problematic points to the discrete logarithm problem and back, we show how to perform a secure key exchange using our favourite doughnuts.

If you are here just to see the video: here it is.

Securely exchanging keys using elliptic curves in simple Weierstrass form can be performed using the Diffie-Hellman^[1] key exchange variant using the rational points^[2] of the elliptic curve over given finite field as the underlying group structure. The goal of the key exchange is to make sure both sides of the communication can compute a shared secret information that can be used as a key for encrypting some actual data. The Elliptic Curve Diffie-Hellman key exchange – or ECDH for short – does exactly that.

Scalar multiplication^[3] of elliptic curve points is the operation that can be used for this purpose. Scalar multiplication is commutative. That means that no matter in what order you perform it, the results are the same. Mathematically speaking:

$a\cdot(b\cdot G)=(a\cdot b)\cdot G$

Two parties wanting to communicate – the famous pair of Alice and Bob – have to agree on an elliptic curve to use and on a generator to start with. They might agree on the elliptic curve we have designed throughout this series^[4] and the point $[4,5]$ to be their generator as seen in Picture 1.

Picture 1: The elliptic curve in simple Weierstrass form $x^3=y^2-2x+15$ over $\mathrm{GF}(23)$ with the generator $G=[4,5]$.

Now to perform a secure key exchange using ECDH each of them must choose a secret number. So Alice chooses some random number $a$ to be her secret number and Bob chooses some random number $b$ to be his secret number.

With their secret numbers chosen, both Alice and Bob now multiply the generator by them and thus create their public points. These public points they can safely exchange over an untrusted communication channel.

$A=aG$

$B=bG$

You can see an example of public points calculated this way in Picture 2.

Picture 2: Public points $A=[13,22]$ and $B=[17,8]$ calculated from private numbers $a=3$ and $b=7$ using the generator $G=[4,5]$ on the elliptic curve in simple Weierstrass form $y^2=x^3-2x+15$ over $\mathrm{GF}(23)$.

With their public points exchanged, each of them now performs the same scalar multiplication, but starts with the received point instead of the generator. This way, both sides come to the same point and therefore compute their shared secret.

$K=aB$

$K=bA$

$K=abG$

$K=baG$

Depicted in Picture 3 is exactly this result where both parties end up with the same point although it is impossible although each of them is unaware of the other party’s secret key and the public points which can be seen by an attacker are useless without it.

Picture 3: Shared secret point $K=[15,5]$ computed both ways from public points $A$ and $B$.

As you can see, no matter which way you calculated the point $K$, it is the same point in both cases. You can see the whole exchange in Video 1 – but be prepared it is a bit longer this time.

Video 1: Elliptic Curve Diffie-Hellman Key Exchange on elliptic curve in simple Weierstrass form $y^2=x^3-2x+15$ over $\mathrm{GF}(23)$ where Alice and Bob establish a shared secret unknown to an attacker watching their communication.

In case you still wonder how secure this is, remember the Elliptic Curve Discrete Logarithm Problem (ECDLP)^[5]. There is no feasible way to find out the numbers $a$ and $b$ from the points $A$ and $B$ while for getting the point $K$ you need to have (at least) one of them and the other party’s public point.

I am glad you followed us so far as to get to some real cryptography. Congratulations to every reader reaching this point. Now there are more options where to follow in our series, we might either look closer at how email communication works or spend some more time in the world of elliptic curves. And as there are some quite interesting elliptic curves out there, you may we will get to more curves eventually. See you next week!

References

1. Wikipedia contributors. (2018, May 8). Diffie–Hellman key exchange. In Wikipedia, The Free Encyclopedia. Retrieved 08:02, May 16, 2018, from https://en.wikipedia.org/w/index.php?title=Diffie%E2%80%93Hellman_key_exchange&oldid=840239160 

2. https://trustica.cz/en/2018/03/01/elliptic-curves-over-finite-fields/

3. https://trustica.cz/en/2018/04/12/elliptic-curves-multiplication-by-scalar/

4. https://trustica.cz/en/2018/04/26/elliptic-curves-prime-order-curves/

5. https://trustica.cz/en/2018/05/10/elliptic-curves-discrete-logarithm-problem/