QUIC X25519 TLS 1.3 TLS 1.2

Hands-on: X25519 Key Exchange

Let's exchange a secret to start a secure conversation.

Overview

Key exchange is a mechanism where two parties (Alice and Bob) can agree on the same number without an eavesdropper being able to tell what it is. X25519 is the name of one method of key exchange, by doing point operations on the Curve25519 elliptic curve:

y2 = x3 + 486662x2 + x

With those point operations, we'll be doing a key exchange that looks like this:

kb∗(ka∗P) = ka∗(kb∗P)

Let's give the above terms some better names:

ka  :   Alice's secret key - a 255-bit (~32-byte) random number
kb  :   Bob's secret key - a 255-bit (~32-byte) random number
P  :   a point on the curve, where x=9
ka∗P  :   Alice's public key
kb∗P  :   Bob's public key
ka∗kb∗P  :   The shared secret
Once Alice and Bob have a shared secret, they can use it to build encryption keys for a secure connection.

Math on the curve

This section can be skipped, it just gives a flavor of the math of elliptic curves.

A great explanation for elliptic curve math is Andrea Corbellini's Elliptic Curve Cryptography: a gentle introduction. That page describes a different curve, but the concepts still apply here. The takeaways from that site are:

Point operations (performed on points on the curve):

  • Adding two points on the curve gives a third point, based on the line between two points and its intersection with the curve.
  • Repeated additions of a point on the curve gives us scalar multiplication:
      2P=P+P
      3P=P+P+P
      6P=P+P+P+P+P+P
      ... etc.
  • Adding points on the curve is associative: adding the results of point addition will give the same result as adding the component points individually:
      P+P+P+P = 3P+P = 2P+2P = 4P
Visual demonstration of point addition
Point Addition: P+Q=R

Modular arithmetic (used when calculating addition and multiplication of points above):

  • Adding, subtracting, and multiplying numbers will "wrap around" at the prime p=2255-19.
  • Division is replaced with the multiplicative inverse: instead of dividing by x we find the number x-1 that satisfies the relationship x∗x-1 =1 in our prime field, and multiply by that.
Examples (with p=23)
Addition: 16+15 = 31mod23 = 8
Subtraction: 8-13 = -5mod23 = 18
Multiplication: 4∗7 = 28mod23 = 5
Multiplicative inverse: 7∗7-1mod23 = 1
→ 7∗10mod23=1; 7-1 = 10
Division: 4/7 → 4∗71mod23
→ 4∗10mod23 = 17

Hands on

Let's play with some actual numbers. This calculator lets us do scalar multiplication on the base point P, which is a point on the curve with coordinate x=9. These calculations only give the x coordinate of nP, the y coordinate is not needed or used.

Secret key multiplier
?

Let's perform a simple key exchange. Give Alice a secret key, such as "7", and use the calculator above to find Alice's public key. Give Bob a different secret key, such as "5", and use the calculator to find Bob's public key:

Now let's be Alice. Put Alice's secret key (ka) into the calculator below, and use it to multiply Bob's public key (kbP).

Public key multiplier

Let's switch over to Bob. Put Bob's secret key (kb) into the calculator, and use it to multiply Alice's public key (kaP). The result matches, because kakbP = kbkaP = 35P.

Since the eavesdropper can't see either of Alice or Bob's secret keys, they can't compute the same result.

Odds and ends

Q: Why can't I reproduce these results in openssl or other tools?

A: Private keys used in actual Curve25519 are modified slightly to avoid particular attacks (see section 4.7 "Clamping" in Implementing Curve25519/X25519 by Martin Kleppmann). In particular the following five bits are clamped to pre-determined values in real implementations (click the "Clamp" button to apply these bit values to your secret key):

BitsValueReason
0,1,20Protect against small-subgroup attacks
2541Prevent a timing leak
2550Constrain n < 2255

You may still find that your output does not match because X25519 keys are stored and transmitted in little-endian order while this page displays them as plain numbers. Flipping the byte order should match them up.

Q: If these are points in an x-y curve, where are the y coordinates?

A: The y coordinates for each point are not needed for X25519, and for simplicity they are not computed. Using only the x coordinate of also reduces public key length, as the y coordinate isn't part of the key.

Each valid point on the curve has two y values that satisfy sqrt(y2).

Y-coordinate calculator

Only half of x values are valid on Curve25519. Going back to our curve equation, valid means that the expression x3 + 486662x2 + x results in a number that in modular arithmetic has a square root (to satisfy the y2 side of the equation).

Q: What does Curve25519 look like?

A: Here's what the curve looks like in real numbers, (i.e. floating point numbers with standard addition and multiplication): an elliptic curve

y2 = x3 + 486662x2 + x

And here's the first points of the curve when calculated in 𝔽p (i.e. with integers 0..2255-19 using modular math):

a pattern of dots, mirrored horizontally, but otherwise seemingly without pattern

y2 = x3 + 486662x2 + x in 𝔽p

Q: Can you give me more details on elliptic curve operations?

A: I found the following useful:

The code for this project can be found on GitHub.

If you found this page useful or interesting let me know via Twitter @XargsNotBombs.