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:
With those point operations, we'll be doing a key exchange that looks like this:
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|
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):
Modular arithmetic (used when calculating addition and multiplication of points above):
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.
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).
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.
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):
|0,1,2||0||Protect against small-subgroup attacks|
|254||1||Prevent a timing leak|
|255||0||Constrain 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).
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):
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):
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.