The Animated Elliptic Curve

Every TLS 1.3 session starts with a key exchange made via an elliptic curve. The most popular curve is Curve25519, and the exchange involves adding a "base point" P to itself over and over again:

We're looking at the heart of TLS 1.3 key exchange, but what's going on? Let's break it down into simple parts.

Adding points on a curve

The elliptic curves we're going to use are in this form: `y^2 = x^3 + Ax + B`

Let's define point addition: a way to combine two points on an elliptic curve to yield a third point (also on the curve).

Point addition has two useful properties which we'll need later:

• commutative: adding points in any order results in the same point:
  P+Q = Q+P
  P+Q+R = R+Q+P = P+R+Q
• associative: addition of additions has the same result as adding the points individually:
  (P+Q)+R = P+(Q+R)
  P+P+P+P+P = (P+P) + (P+P+P) = 2P + 3P = 5P
  P+P+P+P+P = (P+P+P+P) + (P) = 4P + 1P = 5P

This is demonstrated in the animation below which adds points in random order: `n_1P + n_2P = n_3P`

No matter which points are added or in which order, the result is always the same point that was found by adding `P` to itself over and over again `n_3` times above.

Finite field math

Next let's put curves aside and introduce a new set of math operations, the operations of the finite field Fp.

A finite field is just a set of numbers. In this section we'll set `p` to 23 (a prime number). The finite field F23 is the list of numbers 0 through 22:

All the math operations below use only those 23 numbers as inputs as outputs. No negative numbers, no floating point, and nothing higher than 22.

Addition / Subtraction

Adding and subtracting in finite fields is pretty simple. Values of 23 and greater will wrap around to zero, and values below zero will wrap around to 22:

You might also know this as "modulo 23", or as the remainder after dividing a number by 23.

Multiplication

Multiplication is also straightforward. Similar to addition, the result is taken modulo 23:

Negation

You might be used to negation as flipping a value's sign from positive to negative (or vice versa). Another definition would be finding the value `\text{-}n` for `n` that satisfies this equation:

In Fp, we can solve the above and negate a number by subtracting it from `p`:

Division (multiplicative inverse)

Let's define division in Fp around the concept that any non-zero number divided by itself is 1:

Or if we expand one of the terms:

Let's use a different notation for `1//n` which is easier to fit on a line:

In our Fp multiplication it's possible for two positive integers to equal 1 when multiplied together. It turns out that for each positive integer in Fp there is one positive integer that acts as this "multiplicative inverse" solution to the equation above:

To tie it all together, when working in Fp any time we need to divide by a number `n` we will instead multiply by its multiplicative inverse `n^(\text{-}1)`, the number which satisfies the equation `n \cdot n^(\text{-}1) = 1`.

The inverse for each number in F23 is provided in this table.

Square root

Our last operation to define is square root. We'll define the square root of `n` as a number in Fp which satisfies this equation:

Only half of the non-zero members of Fp have a solution to the square root equation. They also have two solutions: much like how real numbers have a positive and negative solution for square root, members of our finite field have two square roots that are each the negation of the other.

The solutions for F23 are provided in this table.

Elliptic curves and finite fields

Now we can combine the two concepts of elliptic curves and finite field math. Let's start with an elliptic curve equation:

For our finite field let's use the prime number 61:

The tables for division and square roots in F61 are pre-computed for convenience.

What would it look like to plot the curve above, using the math of a finite field F61 on a graph? Starting with `x=0` and working through each number from 0 to 60, using the math operations we defined above:

The resulting graph looks like this:

Finally, we'll nominate one of the points on this curve to be the "base point":

The point chosen is somewhat arbitrary, but some points are better than others. This point was chosen because it can be added to itself (see below) a relatively large number of times before it comes back to itself (specifically, it repeats every 73 point additions).

Let's give a name to the combination of above definitions (the curve equation, the prime number for the finite field, and the base point). We'll call it "Curve61".

Point Addition

We can still add points on this curve, using the math of F61 and the rules of point addition: draw lines between two points, find the curve intersection, then negate the point's y-value.

This animation shows finite field math wrapping from 61 to 0, sometimes many times, before intersection with a curve point. Finding the values algebraically is relatively easy, just remember to use the rules of finite field math for these formulas:

Efficient Point Multiplication

The point at 100P is the point `P` added to itself 100 times. It can also be thought of as the point being multiplied by the number 100. You'll see this referred to as "scalar multiplication", and it's just another way to refer to repeated point addition.

We can get to arbitrarily large multiplication of `P` quickly using a "double-and-add" method:

• Repeatedly double `P` to get `\{2P, 4P, 8P, 16P, 32P, …\}`
• Add combinations of the above points to get any needed multiple of `P`

Key exchange

Now we have enough to start doing cryptographic work. We're going to do a key exchange with Curve61, much in the same way that TLS 1.3 does a key exchange with Curve25519.

Alice and Bob want to start a private conversation. To do this, they're going to agree on a number without any eavesdroppers being able to tell what the number is. With an agreed-upon number they can derive a key for one of the many fast and secure ciphers (such as AES) and encrypt their conversation.

The process looks like this:

• Alice and Bob agree to use Curve61, described in the section above
• Alice picks a random number `k_a`
• Alice computes the coordinates of `k_(a)P` and sends it to Bob as `A`
• Bob picks a random number `k_b`
• Bob computes the coordinates of `k_(b)P` and sends it to Alice as `B`
• Alice computes the coordinates of `k_(a)B`, which is `k_(a)(k_(b)P)`
• Bob computes the coordinates of `k_(b)A`, which is `k_(b)(k_(a)P)`

Because point addition on Curve61 is associative, both `k_b(k_aP)` and `k_a(k_bP)` are the same point: they're just the base point added to itself `k_a \times k_b` times. Since they're the same point, both Alice and Bob have agreed on the same number: the coordinates of `k_ak_bP`.

Enter numbers for Bob and Alice's private keys below and watch a key exchange occur:

The real curve

We've played around with a toy curve of 72 points, and you've seen what it means to add points or perform a key exchange. But how does this compare to real curves used in real cryptography such as TLS 1.3?

The most common curve used for key exchange is Curve25519. That curve has a simple equation:

Where our toy curve used F61, a field with 61 numbers in it, Curve25519 uses `\mathbb{F}_(2^255\text{-}19)`. The prime number used for that field, `2^255-19`, is a very large (77-digit) number. Other than the size, the field looks the same as the one we've been using:

Where our toy curve used a base point that can only be added to itself 73 times before repeating, Curve25519 uses a base point that can be added to itself over `2^252` times before repeating.

When peers use Curve25519 to perform key exchange, they select a random 256-bit number (though 5 of those bits are then overridden; see my X25519 site for more details). That's `2^251` possible point multiplications for an attacker to guess at, which is a very large (76-digit) number.

We can add and double points on Curve25519 in much the same way that we did on Curve61, though the formula changes due to the different curve equation (see Wikipedia for details). Using point addition we can perform a key exchange in the same way that we did with our toy curve.

For in-depth information on Curve25519, including the choice of curve equation, the choice of prime number used for Fp, and the exact details of key exchange I can recommend the author's paper and also this technical analysis. Most of these details are streamlining of the concepts listed on this page to keep the exchange mechanism secure and performant, and should not fundamentally conflict with what's explained here.