The Noise Framework and X25519

After this lesson your program computes X25519, the Diffie-Hellman function every Noise handshake is built from, bit-exact with RFC 7748, and knows to refuse a result that no honest peer can produce.

Noise in one page

Noise (noiseprotocol.org) is a recipe for building handshakes out of a few parts: a Diffie-Hellman function, an AEAD cipher, a hash. A handshake is a list of messages, and each message is a list of tokens:

WireGuard is Noise_IKpsk2_25519_ChaChaPoly_BLAKE2s. I: the initiator sends its static key right away. K: the responder's static key is known beforehand, from the config file. The messages are e, es, s, ss from the initiator and e, ee, se, psk back. Four DH results get mixed into the session keys, and both sides get the same four values: the initiator's es is DH(initiator ephemeral private, responder static public) and the responder reaches the same bytes from the other end. Ephemeral keys are thrown away after the handshake, which is what gives forward secrecy.

X25519

Curve25519 does its arithmetic modulo the prime p = 2^255 - 19. A public key is the x coordinate of a curve point, 32 bytes little-endian. A private key is 32 random bytes. X25519(k, u) multiplies the point with x coordinate u by the scalar k and returns the new x coordinate. The public key of a private key is X25519(priv, 9), where u = 9 is the agreed base point, and the shared secret is X25519(my_priv, their_pub), the same number for both sides.

Three preparation steps come before any maths (RFC 7748, section 5):

1. Clamp the scalar: clear the lowest 3 bits of its first byte, clear the top bit of its last byte, set the second highest bit of its last byte. This makes the scalar a multiple of 8, which defeats small-subgroup attacks, and fixes its length so the loop below runs a fixed number of times.
2. Decode u as a little-endian number and ignore the top bit of its last byte.
3. Run the Montgomery ladder: keep two points as fractions (x2 : z2) and (x3 : z3), starting at (1 : 0) and (u : 1). For each of the 255 bits of the scalar, from bit 254 down to bit 0, swap the two points if the bit differs from the previous one, then do one step:

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

After the last bit, swap once more if the final bit calls for it. The answer is x2 times the inverse of z2, where the inverse of z is z^(p-2) (Fermat), written as 32 little-endian bytes. Real implementations swap with masks and no branch so timing does not leak the key; correctness does not depend on that.

Reject the all-zero result

A handful of public keys, for example u = 0 and u = 1, have small order, so X25519 with them returns 32 zero bytes no matter what the private key is. A peer who sends one learns nothing, but also forces a known shared secret. WireGuard aborts the handshake when the output is all zeros, and RFC 7748 (section 6.1) allows exactly that check.

Check against the RFC: private key 77076d0a...2c2a with u = 9 gives the public key 8520f009...4e6a. One wrong bit anywhere gives a random-looking wrong answer, so test against published vectors.

Common mistakes

• Skipping the clamp. Your public key differs from everyone else's and no handshake ever matches.
• Big-endian bytes. Keys and the result are little-endian; a reversed read gives a plausible wrong answer.
• Not masking the top bit of u. A u with the high bit set must give the same answer as with it cleared.
• Negative remainders. After a subtraction the value can go below zero; many languages keep the sign on %. Add p, or use the language's non-negative modulo, before using it.
• Forgetting the zero check. Small-order input must print REJECT.

Your exercise

The starter reads the commands and prints the result, and gives you the field arithmetic. You write the function that clamps, decodes, runs the ladder and encodes. The most likely mistake is applying the clamp to the wrong end of the key.