X25519 and Curve25519

X25519 and Curve25519

Introduction

Two people who have never met need a shared secret key. Diffie-Hellman key exchange lets them agree on one over a public channel. X25519 is the elliptic-curve version of it that most new protocols choose first. Each side sends a 32-byte public key, each side combines the other’s public key with its own private key, and both arrive at the same 32 bytes.

The name has two parts. Curve25519 is the elliptic curve, defined over the prime field with 2^255 - 19 elements. X25519 is the function on that curve: it takes a scalar and the x-like coordinate of a point, called u, and returns the u coordinate of the scalar multiple. Only u is ever used. The sign of the point is dropped, and that choice makes the whole computation simple, fast, and free of special cases.

This guide builds X25519 from the definition in RFC 7748 and checks every part against the RFC’s own test vectors. It covers the curve, the clamping of private keys, the Montgomery ladder, and the protocol around it. The elliptic curve guide explains the general theory, and the Diffie-Hellman guide explains the key exchange in the older, integer version.

Table of Contents

• History and Standards
• The Curve
• Private Keys and Clamping
• The Montgomery Ladder
• Key Exchange with X25519
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Where It Is Used
• Limitations
• Security Status
• FAQ
• References

History and Standards

Daniel Bernstein published Curve25519 in 2006, in a paper titled “Curve25519: new Diffie-Hellman speed records” at the PKC conference. As RFC 7748 states, the procedure of X25519 is taken from that paper and is based on formulas from a 1987 paper by Montgomery, titled “Speeding the Pollard and Elliptic Curve Methods of Factorization”.

The IETF Crypto Forum Research Group standardized it in January 2016 as RFC 7748, “Elliptic Curves for Security”, by Adam Langley, Mike Hamburg, and Sean Turner. The RFC defines two curves, curve25519 and curve448, and the functions X25519 and X448 that use them. Its introduction gives the motivation. The curves lend themselves to constant-time implementation and to scalar multiplication without exceptional cases, which resists a wide range of side-channel attacks, including timing and cache attacks. It also notes that there is concern in the community about how the curves of NIST were generated.

The Curve

Curve25519 is a Montgomery curve, with the equation:

v^2 = u^3 + 486662*u^2 + u     over GF(p),  p = 2^255 - 19

The RFC gives the parameters in a table:

• Prime p. The prime is 2^255 - 19. The RFC recommends it for performance on a wide range of architectures, and it is congruent to 1 modulo 4.
• Coefficient A. The coefficient is 486662.
• Base point: u = 9, with a fixed v value that X25519 never needs.
• Order of the base point: 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed, which is 2^252 + 27742317777372353535851937790883648493.
• Cofactor. The cofactor is 8, so the whole curve has 8 times as many points as the subgroup of the base point.

The coefficient is not arbitrary. Appendix A of the RFC describes the procedure. The constant (A - 2) / 4 appears in the point formulas, so a small value is better, and for this curve it is 121665. The RFC picks the smallest A above 2 for which A - 2 is divisible by four and for which the curve has cofactor 8 while its twist has cofactor 4. The RFC explains the reason for that order. With the twist’s cofactor as the smaller one, algorithms that take the cofactor into account do not have to check for points on the twist.

I confirmed these facts by computation. The prime p and the order l are both prime, p is 1 modulo 4, and (A - 2) / 4 is 121665. With the group order 8 * l, the twist has order 4 times a prime, as the RFC says. Curve25519 is also birationally equivalent to the twisted Edwards curve edwards25519, which the signature scheme EdDSA uses. The RFC gives the maps between the two forms.

Private Keys and Clamping

A private key is 32 random bytes. Before use, the bytes are clamped, which means that a few bits are forced to fixed values:

1. Clear the three lowest bits of the first byte.
2. Clear the highest bit of the last byte.
3. Set the second highest bit of the last byte.
4. Read the 32 bytes as a little-endian integer.

The result is a number of the form 2^254 plus 8 times a value from 0 to 2^251 - 1. Each step has a purpose.

• Clearing the three low bits makes the scalar a multiple of 8, which is the cofactor. A multiple of 8 sends every point whose order divides 8 to the point at infinity, so the small-order part of a public key cannot influence the result in a way that depends on the low bits of the key.
• Clearing the top bit and setting the next one gives every scalar the same length. The ladder always runs for exactly 255 bits, and its first bit is always 1.

For Alice’s key in the RFC example, 77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a, the first byte 77 becomes 70, and the last byte 2a becomes 6a. The clamped key is 70076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c6a.

The public key u coordinate is read in the same spirit. The 32 bytes are read as a little-endian number after the highest bit is cleared. The RFC says implementations must mask that bit, and that they must accept values from p up to 2^255 - 1 and treat them as if they were reduced modulo p.

The Montgomery Ladder

Computing k * P for a 255-bit k takes many point operations. The ladder does it in a fixed pattern. It keeps two points, R0 and R1, that always differ by the input point P. For each bit of k, from the highest to the lowest, one of the points is doubled and the two are added. Which role each point plays depends on the bit. The same sequence of field operations runs for every bit and every key.

X25519 works with projective u coordinates, so that no division is needed inside the loop. A point is a pair (x, z) that stands for u = x / z. The pair (1, 0) stands for the point at infinity. The RFC gives one ladder step. With x1 as the input u coordinate, it reads:

A  = x2 + z2        B  = x2 - z2
AA = A^2            BB = B^2
E  = AA - BB
C  = x3 + z3        D  = x3 - z3
DA = D * A          CB = C * B
x3 = (DA + CB)^2    z3 = x1 * (DA - CB)^2
x2 = AA * BB        z2 = E * (AA + a24 * E)

The pair (x2, z2) is doubled, the pair (x3, z3) receives the sum, and a24 is 121665. One step takes 10 multiplications in the field, counting squarings. Before each step, the two pairs are swapped when the key bit changes. The RFC says that this conditional swap, cswap, should run in constant time, and it shows how to do it with a mask of all ones or all zeros. After the last bit, one more swap puts the answer in (x2, z2).

Here is the first step for the base point u = 9, with numbers small enough to read. The first bit is 1, so the swap makes (x2, z2) = (9, 1) and (x3, z3) = (1, 0). Then A = 10, AA = 100, B = 8, BB = 64, and E = 36. The doubled point is x2 = 6400 and z2 = 157681440. The sum with the point at infinity gives x3 = 324 and z3 = 36, and 324 / 36 is 9, the input point again, as it must be. The code checked that x2 / z2 equals the u coordinate that the ordinary doubling formula gives for the point (9, v).

At the end, one division is needed. The result is x2 / z2, and the inverse of z2 is z2^(p - 2), because of Fermat’s little theorem. The answer is written as 32 little-endian bytes, with the top bit zero.

Key Exchange with X25519

The protocol of RFC 7748 is short. Alice picks 32 random bytes a. Bob picks 32 random bytes b. The base point is encoded as the byte 9 followed by 31 zero bytes.

1. Alice sends her public key K_A = X25519(a, 9) to Bob. Bob sends his public key K_B = X25519(b, 9) to Alice.
2. Alice computes the value X25519(a, K_B). Bob computes the value X25519(b, K_A).
3. Both of them get the same result, K = X25519(a, X25519(b, 9)) = X25519(b, X25519(a, 9)).

The two results are equal because scalar multiplication commutes: both are a * b times the base point. The RFC says that Alice and Bob should then derive a symmetric key with a key derivation function that includes K, K_A, and K_B. The raw value K is not meant to be used as a key directly. Its top bit, for example, is always zero.

The RFC also says that both sides may check whether K is all zero and abort if it is. The reason is that points of small order, which divide the cofactor, make the function return zero. An attacker who sends such a public key forces the secret to a known value. The RFC notes that the check can be done by OR-ing all the bytes together and testing the result, so that no timing leaks.

Interactive Visualizer

The visualizer above runs this exact function. The first variant computes a public key, which is X25519 of your private key and the base point 9. The second variant computes a shared secret from your private key and another party’s public key. The defaults are Alice’s private key and Bob’s public key from RFC 7748, so the first run gives the RFC’s shared secret.

The log shows the clamping, the decoding of u, and the start of the ladder. It lists the first six and the last six of the 255 bit steps with the value of x2, and it says how many steps it skips in between. It then shows the division, the encoding, and for a shared secret the check for zero. Try a public key of all zeros to see the warning for a point of small order.

A Worked Example

The test vector of section 6.1 of the RFC has two parties. Alice’s private key is 77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a, and Bob’s is 5dab087e624a8a4b79e17f8b83800ee66f3bb1292618b6fd1c2f8b27ff88e0eb. Their public keys are:

Alice: 8520f0098930a754748b7ddcb43ef75a0dbf3a0d26381af4eba4a98eaa9b4e6a
Bob:   de9edb7d7b7dc1b4d35b61c2ece435373f8343c85b78674dadfc7e146f882b4f

Alice computes the value X25519(a, K_B), and Bob computes the value X25519(b, K_A). Both of them get the shared secret:

4a5d9d5ba4ce2de1728e3bf480350f25e07e21c947d19e3376f09b3c1e161742

The RFC’s test of section 5.2 starts with k = u = 9 and repeats the step k, u = X25519(k, u), k. After one round the value is 422c8e7a6227d7bca1350b3e2bb7279f7897b87bb6854b783c60e80311ae3079. After a thousand rounds it is 684cf59ba83309552800ef566f2f4d3c1c3887c49360e3875f2eb94d99532c51. The RFC also lists a value for a million rounds, which I did not run.

Python Implementation

This is a complete X25519, following the structure of RFC 7748. The function x25519 clamps the scalar, runs the ladder, and returns 32 bytes.

# x25519.py
# X25519 (RFC 7748): Diffie-Hellman on Curve25519, using only the u coordinate.
# The curve is the Montgomery curve v^2 = u^3 + 486662*u^2 + u over GF(2^255 - 19).
# Teaching code. It is not constant time. Real code must not branch on secret bits.

P = 2 ** 255 - 19
A24 = 121665  # (486662 - 2) / 4
BASE_POINT = bytes([9]) + bytes(31)  # u = 9, as 32 little-endian bytes


def decode_scalar(k):
    """Clear the 3 lowest bits and the top bit, set bit 254, then read as little-endian."""
    k = bytearray(k)
    k[0] &= 248
    k[31] &= 127
    k[31] |= 64
    return int.from_bytes(k, "little")


def decode_u(u):
    """Read as little-endian after clearing the top bit. A value of p or more is reduced later."""
    u = bytearray(u)
    u[31] &= 127
    return int.from_bytes(u, "little")


def x25519(k, u):
    """Multiply the point with u-coordinate u by the scalar k. Both are 32 bytes."""
    k = decode_scalar(k)
    x1 = decode_u(u)
    x2, z2 = 1, 0   # the point at infinity
    x3, z3 = x1, 1  # the input point
    swap = 0
    for t in range(254, -1, -1):
        bit = (k >> t) & 1
        swap ^= bit
        if swap:
            x2, x3 = x3, x2
            z2, z3 = z3, z2
        swap = bit
        # one step of the Montgomery ladder: a doubling of (x2, z2) and an addition into (x3, z3)
        a = (x2 + z2) % P
        aa = a * a % P
        b = (x2 - z2) % P
        bb = b * b % P
        e = (aa - bb) % P
        c = (x3 + z3) % P
        d = (x3 - z3) % P
        da = d * a % P
        cb = c * b % P
        x3 = (da + cb) ** 2 % P
        z3 = x1 * (da - cb) ** 2 % P
        x2 = aa * bb % P
        z2 = e * (aa + A24 * e) % P
    if swap:
        x2, x3 = x3, x2
        z2, z3 = z3, z2
    # the result is x2 / z2 in the field, found with the inverse z2^(p-2)
    return (x2 * pow(z2, P - 2, P) % P).to_bytes(32, "little")


def public_key(private_key):
    return x25519(private_key, BASE_POINT)


if __name__ == "__main__":
    # The Diffie-Hellman example of RFC 7748, section 6.1
    alice = bytes.fromhex("77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a")
    bob = bytes.fromhex("5dab087e624a8a4b79e17f8b83800ee66f3bb1292618b6fd1c2f8b27ff88e0eb")
    alice_public = public_key(alice)
    bob_public = public_key(bob)
    print("Alice public:", alice_public.hex())
    print("Bob public:  ", bob_public.hex())
    print("Alice secret:", x25519(alice, bob_public).hex())
    print("Bob secret:  ", x25519(bob, alice_public).hex())
    # A public key of small order removes the other party's contribution: the result is all zeros
    print("point u = 0: ", x25519(alice, bytes(32)).hex())

Running it produces this output:

Alice public: 8520f0098930a754748b7ddcb43ef75a0dbf3a0d26381af4eba4a98eaa9b4e6a
Bob public:   de9edb7d7b7dc1b4d35b61c2ece435373f8343c85b78674dadfc7e146f882b4f
Alice secret: 4a5d9d5ba4ce2de1728e3bf480350f25e07e21c947d19e3376f09b3c1e161742
Bob secret:   4a5d9d5ba4ce2de1728e3bf480350f25e07e21c947d19e3376f09b3c1e161742
point u = 0:  0000000000000000000000000000000000000000000000000000000000000000

I checked this code against several independent sources before writing it up. The two vectors of section 5.2 of the RFC and the key pairs and shared secret of section 6.1 all match. So does the iterated test, after 1 and after 1,000 rounds. The test code reads all of them from the text of the RFC. A second implementation uses the group law of the curve with affine coordinates and double-and-add. It agrees with the ladder on 60 random scalars with the base point and on 60 random scalars with random points, and the base point has the order that the RFC prints. In Node.js, which uses OpenSSL, 1500 random pairs of a private key and a u value give identical 32 bytes, and the public key that OpenSSL derives for Alice equals the RFC value. OpenSSL refuses the input u = 0 and u = 1, which have small order, while this teaching code returns zeros, as the RFC describes. The top bit of u is ignored, a value u + p gives the result for u, and the seven values of small order give zeros. The visualizer code matches all 460 test vectors that this Python code produces, and I ran its page in a simulated browser.

Where It Is Used

• TLS 1.3. RFC 8446 requires every compliant application to support key exchange with secp256r1, the curve P-256 of NIST, and says that it should support key exchange with X25519. The TLS guide covers the handshake.
• SSH. RFC 8731 specifies key exchange methods that use Curve25519 and Curve448 in the Secure Shell protocol.
• The Signal protocol. The X3DH specification lets an application choose X25519 or X448 as its curve. The Signal guide covers the protocol.

Limitations

This is a faithful teaching version of the function, not a production one:

• Not constant time. The code branches on the key bits and uses Python integers, whose timing depends on their size. RFC 7748 asks for a constant-time cswap and warns that memory access patterns, jumps, and the arithmetic itself must not depend on the secret.
• No key generation. The code takes the 32 bytes as given. Real code must draw them from a secure random source.
• No derivation of a key. The shared value K is not a key. A real protocol runs it through a key derivation function together with both public keys.
• No check for zero. The code does not abort on an all-zero result. Real code should abort in that case.
• No authentication. X25519 gives a shared secret with whoever sent the public key. It does not tell you who that is. A man in the middle can run one exchange with each side. Protocols add signatures or other authentication around it.
• Equivalent public keys. The RFC notes that for each public key there are several other publicly computable ones that produce the same shared secrets. A protocol that uses a public key as an identifier and a shared secret as proof of ownership, without putting the public keys into the key derivation, can have subtle weaknesses.

Security Status

RFC 7748 states that the security level of curve25519 is slightly under the standard 128-bit level, which it considers acceptable. It also says that large quantum computers, if they are ever built, will break both curve25519 and curve448, and that classical attacks leave curve25519 perfectly safe. For key exchange that has to resist quantum computers, see the post-quantum schemes in the Kyber guide.

The design removes several common implementation mistakes. The ladder has no special cases for the point at infinity or for equal points, every 32-byte string is accepted as a public key, and the curve and its twist both have large prime-order subgroups. The weak points are the ones in the list above. The RFC names several of them itself. Do not assume that both private keys contribute to the secret, and do not use a public key as an identifier without care.

FAQ

What is the difference between Curve25519, X25519, and Ed25519?

Curve25519 is the curve. X25519 is the Diffie-Hellman function on it, which uses only the u coordinate. Ed25519 is the signature scheme on the equivalent Edwards curve. The three share the same prime and the same underlying group, but they have different encodings and different jobs. The EdDSA guide covers the signature side.

Why does the ladder use only the u coordinate?

Because the u coordinate of k * P depends only on the u coordinate of P. The sign of the point drops out, since P and -P give results with the same u. Working with u alone makes each step cheaper and avoids the special cases of the usual addition formula.

Why must a private key be clamped?

Clamping fixes the length of the key for the ladder and makes the key a multiple of the cofactor 8. That makes the result for a point of small order independent of the low bits of the key. A library can clamp the key when it uses it. In my test, OpenSSL accepted unclamped random bytes and gave the same result as the clamped computation, so you can store the 32 random bytes unchanged.

Is it safe to accept any 32 bytes as a public key?

Yes, for the curve itself. Every 32-byte string, after masking the top bit, is a valid u coordinate, on the curve or on its twist, and both groups have a large prime-order subgroup and a small cofactor. The RFC chose the cofactors, 8 for the curve and 4 for the twist, so that implementations need not check for points on the twist. What can still go wrong is a small-order point, which gives an all-zero secret. That is why the check for zero exists.

Is X25519 better than the NIST curve P-256?

It is simpler to implement safely, because the formulas have no exceptions and the key format has no invalid values. The RFC’s introduction also mentions the community’s concern about how the NIST curves were generated. P-256 is more widely required: TLS 1.3 says a compliant application must support it, and only says that X25519 should be supported.

Does X25519 resist quantum computers?

No, it does not. The RFC says that large quantum computers would break both curve25519 and curve448. Against attackers who record traffic today to decrypt it later, one response is to combine it with a post-quantum scheme, as in the Kyber guide.

References

1. Langley, Adam, Hamburg, Mike, and Turner, Sean. “Elliptic Curves for Security.” RFC 7748, Internet Research Task Force, January 2016. Available at: https://www.rfc-editor.org/rfc/rfc7748

2. Bernstein, Daniel. “Curve25519: new Diffie-Hellman speed records.” Public Key Cryptography, PKC 2006. Available at: https://cr.yp.to/ecdh/curve25519-20060209.pdf

3. Rescorla, Eric. “The Transport Layer Security (TLS) Protocol Version 1.3.” RFC 8446, August 2018. Available at: https://www.rfc-editor.org/rfc/rfc8446

4. Adamantiadis, Aris, Josefsson, Simon, and Baushke, Mark. “Secure Shell (SSH) Key Exchange Method Using Curve25519 and Curve448.” RFC 8731, February 2020. Available at: https://www.rfc-editor.org/rfc/rfc8731

5. Marlinspike, Moxie, and Perrin, Trevor. “The X3DH Key Agreement Protocol.” Signal, Revision 1, November 2016. Available at: https://signal.org/docs/specifications/x3dh/

6. Josefsson, Simon, and Liusvaara, Ilari. “Edwards-Curve Digital Signature Algorithm (EdDSA).” RFC 8032, January 2017. Available at: https://www.rfc-editor.org/rfc/rfc8032