ECDH key exchange (X25519, P-256)

Deep dive

How it works

In: own scalar d (32 random bytes), peer public key bytes · Out: 32-byte secret Z, then a derived key · State: none; an ephemeral d is destroyed after use · Cost: one scalar multiplication (255 ladder steps for X25519).

1. Draw d from a CSPRNG. X25519: clamp it (clear bits 0-2 and 255, set bit 254): d is a multiple of 8 with fixed length. P-256: d in 1..n−1.
2. Send Q = d·G: X25519 the u-coordinate of G (u = 9); P-256 the point as 04 || X || Y.
3. Receive Q_peer. P-256: validate it (below). X25519: read 32 little-endian bytes, ignore bit 255, reduce mod p.
4. Z = d·Q_peer. X25519 uses the Montgomery ladder on u only: per bit, a branch-free swap, one differential add, one double. P-256: Z is the x-coordinate of the result.
5. Abort on an all-zero X25519 output or a P-256 identity point.
6. Derive: key = HKDF(Z, info = both public keys or the transcript). Never use Z as a key. SP 800-56A requires an approved key-derivation method; TLS 1.3 feeds Z "raw" into its HKDF schedule (RFC 8446 §7.4.2).
7. Destroy ephemeral d and Z (zeroization).

Validation (defensive). P-256 formulas never use the curve constant b, so a point on a different curve with the same a is processed without complaint. A victim who multiplies it by a static d leaks d modulo a small order, and enough such points recover d (invalid-curve attack; fault variant: Biehl, Meyer, Müller 2000). The defence is cheap: NIST full validation checks Q is not the identity, coordinates are in [0, p−1], and y² = x³ + ax + b (SP 800-56A §5.6.2.3.3; for cofactor 1 nothing else is needed). TLS 1.3 requires this of P-256 peers (RFC 8446 §4.2.8.2); partial validation is allowed only for ephemeral keys. X25519 needs no on-curve test: every 32-byte string is a u on the curve or its twist.

Small-order inputs. Curve25519 has cofactor 8, so a few u values force Z to zero whatever your key is. RFC 7748 §6.1: both sides MAY check for all zeros; RFC 8446 §7.4.2: TLS MUST; Noise §12.1 allows either. A public key also has several equivalent encodings, so put both keys in the KDF input.

Code

For learning; use a vetted library. X25519 from primitives: 5×51-bit limbs, u128 products, Fermat inversion, branch-free swap. Asserts check an RFC 7748 §5.2 vector and the §6.1 Alice/Bob example; it prints µs per multiplication.

// X25519 (RFC 7748), 5x51-bit limbs. For learning; use a vetted library.
type Fe = [u64; 5];
const M: u64 = (1 << 51) - 1;

fn carry(mut a: [u64; 5]) -> Fe {
    for _ in 0..2 {
        for i in 0..4 { a[i + 1] += a[i] >> 51; a[i] &= M; }
        a[0] += 19 * (a[4] >> 51); a[4] &= M; // 2^255 = 19 (mod p)
    }
    a
}
fn add(a: &Fe, b: &Fe) -> Fe { core::array::from_fn(|i| a[i] + b[i]) }
fn sub(a: &Fe, b: &Fe) -> Fe {
    // add 16p first so no limb underflows
    carry(core::array::from_fn(|i| a[i] + 16 * (if i == 0 { M - 18 } else { M }) - b[i]))
}
fn mul(a: &Fe, b: &Fe) -> Fe {
    let mut t = [0u128; 5];
    for i in 0..5 { for j in 0..5 {
        let p = a[i] as u128 * b[j] as u128;
        if i + j < 5 { t[i + j] += p } else { t[i + j - 5] += 19 * p }
    } }
    let mut c = 0u128; let mut r = [0u64; 5];
    for i in 0..5 { t[i] += c; r[i] = t[i] as u64 & M; c = t[i] >> 51; }
    r[0] += 19 * c as u64; // c < 2^64, 19*c fits after carry below
    carry(r)
}
fn invert(z: &Fe) -> Fe { // z^(p-2); the exponent is public, so a plain loop is fine
    let mut e = [0xffu8; 32]; e[0] = 0xeb; e[31] = 0x7f;
    let mut r: Fe = [1, 0, 0, 0, 0];
    for bit in (0..255).rev() {
        r = mul(&r, &r);
        if (e[bit / 8] >> (bit % 8)) & 1 == 1 { r = mul(&r, z); }
    }
    r
}
fn cswap(s: u64, a: &mut Fe, b: &mut Fe) {
    let m = 0u64.wrapping_sub(s); // all ones or all zeros, no branch
    for i in 0..5 { let t = m & (a[i] ^ b[i]); a[i] ^= t; b[i] ^= t; }
}
fn decode(u: &[u8; 32]) -> Fe {
    let mut buf = [0u8; 40]; buf[..32].copy_from_slice(u);
    buf[31] &= 0x7f; // RFC 7748 §5: ignore the top bit
    core::array::from_fn(|i| (u64::from_le_bytes(buf[51 * i / 8..][..8].try_into().unwrap()) >> (51 * i % 8)) & M)
}
fn encode(a: &Fe) -> [u8; 32] {
    let mut h = carry(*a);
    let mut q = (h[0] + 19) >> 51; // q = 1 iff h >= p
    for i in 1..5 { q = (h[i] + q) >> 51; }
    h[0] += 19 * q;
    for i in 0..4 { h[i + 1] += h[i] >> 51; h[i] &= M; }
    h[4] &= M;
    let (mut out, mut acc, mut bits, mut n) = ([0u8; 32], 0u128, 0, 0);
    for l in h { acc |= (l as u128) << bits; bits += 51;
        while bits >= 8 && n < 32 { out[n] = acc as u8; acc >>= 8; bits -= 8; n += 1; } }
    if n < 32 { out[n] = acc as u8; }
    out
}
pub fn x25519(k: &[u8; 32], u: &[u8; 32]) -> [u8; 32] {
    let mut k = *k;
    k[0] &= 248; k[31] &= 127; k[31] |= 64; // clamp: cofactor 8, fixed top bit
    let x1 = decode(u);
    let (mut x2, mut z2, mut x3, mut z3, mut swap) = ([1, 0, 0, 0, 0], [0; 5], x1, [1, 0, 0, 0, 0], 0u64);
    for t in (0..255).rev() {
        let kt = ((k[t / 8] >> (t % 8)) & 1) as u64;
        swap ^= kt; cswap(swap, &mut x2, &mut x3); cswap(swap, &mut z2, &mut z3); swap = kt;
        let (a, b) = (add(&x2, &z2), sub(&x2, &z2));
        let (aa, bb) = (mul(&a, &a), mul(&b, &b));
        let e = sub(&aa, &bb);
        let (c, d) = (add(&x3, &z3), sub(&x3, &z3));
        let (da, cb) = (mul(&d, &a), mul(&c, &b));
        let s = add(&da, &cb); x3 = mul(&s, &s);
        let df = sub(&da, &cb); z3 = mul(&x1, &mul(&df, &df));
        x2 = mul(&aa, &bb);
        z2 = mul(&e, &add(&aa, &mul(&[121665, 0, 0, 0, 0], &e)));
    }
    cswap(swap, &mut x2, &mut x3); cswap(swap, &mut z2, &mut z3);
    encode(&mul(&x2, &invert(&z2)))
}
/// ECDH: constant-time all-zero check on the output (RFC 7748 §6.1, MAY; TLS 1.3 says MUST).
pub fn dh(sk: &[u8; 32], peer: &[u8; 32]) -> Option<[u8; 32]> {
    let k = x25519(sk, peer);
    if k.iter().fold(0, |a, b| a | b) == 0 { None } else { Some(k) }
}
fn h(s: &str) -> [u8; 32] {
    core::array::from_fn(|i| u8::from_str_radix(&s[2 * i..2 * i + 2], 16).unwrap())
}
fn main() {
    let r = x25519(&h("a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4"),
                   &h("e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c"));
    assert_eq!(r, h("c3da55379de9c6908e94ea4df28d084f32eccf03491c71f754b4075577a28552"));
    // RFC 7748 §6.1: Alice and Bob
    let mut base = [0u8; 32]; base[0] = 9;
    let (a, b) = (h("77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a"),
                  h("5dab087e624a8a4b79e17f8b83800ee66f3bb1292618b6fd1c2f8b27ff88e0eb"));
    let (qa, qb) = (x25519(&a, &base), x25519(&b, &base));
    assert_eq!(qa, h("8520f0098930a754748b7ddcb43ef75a0dbf3a0d26381af4eba4a98eaa9b4e6a"));
    assert_eq!(qb, h("de9edb7d7b7dc1b4d35b61c2ece435373f8343c85b78674dadfc7e146f882b4f"));
    let k = h("4a5d9d5ba4ce2de1728e3bf480350f25e07e21c947d19e3376f09b3c1e161742");
    assert_eq!(dh(&a, &qb), Some(k));
    assert_eq!(dh(&b, &qa), Some(k));
    assert_eq!(dh(&a, &[0u8; 32]), None); // u = 0 has order 1: output is all zeros
    let t = std::time::Instant::now();
    let mut o = base;
    for _ in 0..2000 { o = x25519(&a, &o); }
    println!("{:.1} us per x25519 ({:02x})", t.elapsed().as_secs_f64() * 1e6 / 2000.0, o[0]);
}

Complexity and constants

• X25519: 255 ladder steps, ten field multiplications each (counted from the code), plus one inversion. Nothing is indexed by a secret, so no cache pattern leaks.
• Measured, M4 Pro, release, one multiplication: this code 49-55 µs (runs vary); x25519-dalek 2.0.1 23.9 µs; RustCrypto p256 0.13.2 ECDH 100.4 µs. Single runs.

Efficiency

Cost: one scalar multiplication per side, order of 25-100 µs on a laptop core (measured above); compute-bound, no I/O.

Levers:

• Addition-chain inversion — saves about 250 of roughly 3,000 field multiplications in this code (counted) — always.
• Tuned field arithmetic (dalek, assembly) — 2x here, 49 vs 24 µs (measured) — servers with many handshakes.
• Fresh ephemeral per session — one extra multiplication buys forward secrecy — default.

Naive → standard → state of the art:

• Affine double-and-add, one inversion per step · slow, leaks timing
• Montgomery ladder, projective, one final inversion · about 50 µs (this page)
• Hand-tuned field arithmetic · about 24 µs (x25519-dalek)

Implementation notes

• 51-bit limbs: a 51×51 product has 102 bits, a column of five products times 19 fits u128. Reduce with 2²⁵⁵ ≡ 19. Subtraction adds 16p first so limbs never underflow.
• Swap with a mask (0 - bit), not an if; see constant-time code.
• P-256: use a library that validates points on parse; never build a point from raw coordinates.
• KDF input: Z, both public keys in a fixed order (initiator first), a protocol label.

Pitfalls

• Using Z directly as an AES key or hashing it with no context.
• Assuming the library validates: some APIs accept any pair of coordinates.
• Treating the zero check as optional in TLS (MUST), or as validation for P-256.
• Static-static only: same Z every session, no forward secrecy.
• Short-circuiting the zero check; OR all bytes together.
• Reusing a key pair across protocols.

Variants and alternatives

In production

• Web: TLS 1.3 key shares (x25519, secp256r1).
• Networking: WireGuard (Noise IK on Curve25519).
• Messaging: X3DH and the double ratchet.
• Cloud: HPKE (RFC 9180) encrypts to a public key.
• IoT: Bluetooth LE Secure Connections uses P-256 ECDH (from memory); hardware keystores offer P-256 ECDH.

Implementations

Sources

• Langley, Hamburg, Turner, RFC 7748: Elliptic Curves for Security, 2016 (§5, §6.1, §7). RFC
• Barker et al., NIST SP 800-56A Rev. 3, 2018 (§5.6.2.3, §5.7.1.2, §5.8). spec
• Rescorla, RFC 8446: TLS 1.3, 2018 (§4.2.8.2, §7.4.2). RFC
• Barnes et al., RFC 9180: Hybrid Public Key Encryption, 2022. RFC
• Perrin, The Noise Protocol Framework, §12.1. spec
• Bernstein, Curve25519: New Diffie-Hellman Speed Records, PKC 2006. paper
• Biehl, Meyer, Müller, Differential Fault Attacks on Elliptic Curve Cryptosystems, CRYPTO 2000. paper
• Kwiatkowski et al., Post-quantum hybrid ECDHE-MLKEM Key Agreement for TLSv1.3, IETF Internet-Draft. draft