The Animated Elliptic Curve

Visualizing Elliptic Curve Cryptography

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:

Curve25519 point addition

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:

Examples of elliptic curves

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

Repeated addition of a point P

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

• commutative: adding points in any order results in the same point:
  P+Q+R = R+Q+P = P+R+Q
• associative: addition of additions has the same result as adding the points individually:
  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

See the animation below which adds points in random order. The result is always the expected point.

Point addition is associative and commutative

Finite field math❡

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

A finite field is just a set of numbers. In this section we'll set to 23 (a prime number). The finite field 𝔽23 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 for that satisfies this equation:

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

➻ Division (multiplicative inverse)❡

In 𝔽p division is defined around the relation that any non-zero number divided by itself is 1:

Or if we expand some terms:

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

You can see that dividing by is the same as multiplying by the value .

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

To tie it all together, when working in 𝔽p any time we need to divide by a number we will instead multiply by its multiplicative inverse , the number which satisfies the equation .

The inverse for each number in 𝔽23 is provided in this table.

➻ Square root❡

Our last operation to define is taking a square root. We'll define the square root of as a number in 𝔽p which satisfies this equation:

In real numbers there are two square roots for every non-zero number (positive and negative). The same is true in 𝔽p, and each solution is the negation of the other.

Only half of the non-zero members of 𝔽p have square roots. The square roots in 𝔽23 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 𝔽61 are pre-computed for convenience.

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

Let's call the combination of the definitions above "Curve61". What would it look like to plot this curve on a graph? Starting with and working through each number from 0 to 60, using the math operations we defined above:

:		1 and 60
:		undefined
:		24 and 37
:		undefined
:		undefined
:		7 and 54
... and so on

The resulting graph looks like this:

Curve61: An elliptic curve plotted in 𝔽61

➻ Point Addition❡

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

Curve61 point addition

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 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 quickly using a "double-and-add" method:

• Repeatedly double to get
• Add combinations of the above points to get any needed multiple of

Double-and-add method for point 170P

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
• Alice computes the coordinates of and sends it to Bob as
• Bob picks a random number
• Bob computes the coordinates of and sends it to Alice as
• Alice computes the coordinates of , which is
• Bob computes the coordinates of , which is

Because point addition on Curve61 is associative, both and are the same point: they're just the base point added to itself times. Since they're the same point, both Alice and Bob have agreed on the same number: the coordinates of .

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?

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

Where our toy curve used 𝔽61, a field with 61 numbers in it, Curve25519 uses . The prime number used for that field, , 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, uses a base point that can be added to itself over 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 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 𝔽p, 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.