ecdh-x25519-tls13.ipynb

Kernel: SageMath 10.0

Connect: ECDH (X25519) in TLS 1.3

Module 06 | Real-World Connections

The elliptic curve Diffie-Hellman you learned in Notebook 06f is the default key exchange in every modern HTTPS connection.

Introduction

When you visit https:// anything, your browser performs a TLS 1.3 handshake with the server. The most common key exchange in TLS 1.3 is X25519: elliptic curve Diffie-Hellman on Curve25519.

This notebook traces how the abstract concepts from Module 06 --- scalar multiplication, the ECDLP, curve choice --- become the concrete key exchange that secures the internet.

We will:

1. Understand the Montgomery form of Curve25519

2. See why $x$-coordinate-only arithmetic (the Montgomery ladder) is elegant and secure

3. Simulate an ECDH key exchange on a small Montgomery curve

4. Understand why X25519 was chosen over NIST curves

Curve25519: A Montgomery Curve

Curve25519 is defined by the Montgomery form:

$$E: By^2 = x^3 + Ax^2 + x$$

with $A = 486662$, $B = 1$, over $\mathbb{F}_p$ where $p = 2^{255} - 19$.

This is a different representation from the short Weierstrass form $y^2 = x^3 + ax + b$ we used in Module 06, but it is still an elliptic curve with the same group structure. The Montgomery form enables a special trick: $x$-coordinate-only scalar multiplication.

# === Curve25519 parameters ===
p25519 = 2^255 - 19
print(f"p = 2^255 - 19 = {p25519}")
print(f"p is prime? {is_prime(p25519)}")
print(f"p has {p25519.nbits()} bits")
print(f"\nMontgomery parameters: A = 486662, B = 1")
print(f"Equation: y^2 = x^3 + 486662*x^2 + x  over F_p")

# The base point has x-coordinate 9
print(f"\nBase point x-coordinate: u = 9")
print(f"(X25519 only uses the x-coordinate!)")

# Group order
n25519 = 2^252 + 27742317777372353535851937790883648493
print(f"\nGroup order: n = {n25519}")
print(f"n has {n25519.nbits()} bits")
print(f"n is prime? {is_prime(n25519)}")
print(f"Cofactor: h = 8 (the full curve has order 8n)")

The X25519 Function: $x$-Coordinate Only

The key innovation of X25519 is that the entire Diffie-Hellman computation uses only $x$-coordinates. The $y$-coordinate is never computed.

For Montgomery curves, there is a formula for the $x$-coordinate of $P + Q$ that depends only on $x_P$, $x_Q$, and $x_{P-Q}$. This is called the Montgomery ladder, and it has a beautiful property: every step performs the same operations regardless of the scalar bit, making it naturally constant-time.

Let's demonstrate on a small Montgomery curve.

# === A small Montgomery curve for demonstration ===
# By^2 = x^3 + Ax^2 + x with A=3, B=1 over F_1009
p_small = 1009
A_mont = 3
F_small = GF(p_small)

# Convert to Weierstrass form for SageMath:
# y^2 = x^3 + Ax^2 + x  (Montgomery with B=1)
# Substitute x -> X - A/3 to get short Weierstrass y^2 = X^3 + aX + b
a_weier = F_small(1 - A_mont^2 / 3)
b_weier = F_small(A_mont * (2 * A_mont^2 / 9 - 1) / 3)

E_small = EllipticCurve(F_small, [Integer(a_weier), Integer(b_weier)])
order = E_small.cardinality()
print(f"Small Montgomery curve: y^2 = x^3 + {A_mont}x^2 + x  over F_{p_small}")
print(f"Weierstrass form: y^2 = x^3 + {Integer(a_weier)}x + {Integer(b_weier)}")
print(f"Curve order: {order} = {factor(order)}")

# Find a base point (convert back to Montgomery x-coordinate)
G_weier = E_small.gens()[0]
# Montgomery x = Weierstrass X + A/3
x_mont_base = Integer(F_small(G_weier[0]) + F_small(A_mont) / 3)
print(f"\nBase point (Weierstrass): {G_weier}")
print(f"Base point Montgomery x-coordinate: {x_mont_base}")
print(f"Order of base point: {G_weier.order()}")

# === Montgomery ladder: x-coordinate-only scalar multiplication ===
def montgomery_ladder(k, x_P, A, p):
    """
    Compute x-coordinate of k*P using the Montgomery ladder.
    Only uses the x-coordinate of P.
    
    This is constant-time: every bit of k performs the same operations.
    """
    F = GF(p)
    # (x2, z2) represents x-coordinate of the "current" point (projective)
    # (x3, z3) represents x-coordinate of "current + P"
    x2, z2 = F(1), F(0)   # Point at infinity
    x3, z3 = F(x_P), F(1) # The point P
    
    A24 = F(A + 2) / F(4)  # precompute (A+2)/4
    
    bits = k.bits()  # least significant bit first
    for i in range(len(bits) - 1, -1, -1):
        bit = bits[i]
        # Constant-time conditional swap
        if bit == 1:
            x2, x3 = x3, x2
            z2, z3 = z3, z2
        
        # Montgomery ladder step (differential addition + doubling)
        A_ = x2 + z2
        AA = A_^2
        B_ = x2 - z2
        BB = B_^2
        E_ = AA - BB
        C_ = x3 + z3
        D_ = x3 - z3
        DA = D_ * A_
        CB = C_ * B_
        x3 = (DA + CB)^2
        z3 = F(x_P) * (DA - CB)^2
        x2 = AA * BB
        z2 = E_ * (AA + A24 * E_)
        
        if bit == 1:
            x2, x3 = x3, x2
            z2, z3 = z3, z2
    
    # Convert from projective to affine
    return Integer(x2 * z2^(-1)) if z2 != 0 else None

# Test: compare Montgomery ladder with SageMath's scalar multiplication
test_scalar = 42
result_sage = test_scalar * G_weier
# Convert SageMath result to Montgomery x-coordinate
x_sage = Integer(F_small(result_sage[0]) + F_small(A_mont) / 3)

result_ladder = montgomery_ladder(Integer(test_scalar), x_mont_base, A_mont, p_small)

print(f"Scalar: k = {test_scalar}")
print(f"Montgomery ladder result:  x = {result_ladder}")
print(f"SageMath (converted):     x = {x_sage}")
print(f"Match? {result_ladder == x_sage}")
print(f"\nNote: we computed k*P using ONLY the x-coordinate of P.")
print(f"No y-coordinate was ever needed!")

Toy ECDH Key Exchange (Montgomery Style)

Let's simulate a full X25519-style key exchange on our small Montgomery curve. This is exactly what happens during a TLS 1.3 handshake.

# === ECDH on our small Montgomery curve ===
n_sub = G_weier.order()  # order of the base point

# Alice generates her key pair
a_priv = randint(1, n_sub - 1)
a_pub_x = montgomery_ladder(Integer(a_priv), x_mont_base, A_mont, p_small)

# Bob generates his key pair
b_priv = randint(1, n_sub - 1)
b_pub_x = montgomery_ladder(Integer(b_priv), x_mont_base, A_mont, p_small)

print("=== TLS 1.3 Key Exchange (toy version) ===")
print(f"\nPublic parameters: curve, base point x = {x_mont_base}")
print(f"\nAlice (client):")
print(f"  Private key: a = {a_priv}")
print(f"  Public key (x-only): a*G_x = {a_pub_x}")
print(f"\nBob (server):")
print(f"  Private key: b = {b_priv}")
print(f"  Public key (x-only): b*G_x = {b_pub_x}")

# Shared secret computation (x-coordinate only!)
shared_alice = montgomery_ladder(Integer(a_priv), b_pub_x, A_mont, p_small)
shared_bob = montgomery_ladder(Integer(b_priv), a_pub_x, A_mont, p_small)

print(f"\n=== Shared Secret ===")
print(f"Alice computes a * (b*G)_x = {shared_alice}")
print(f"Bob computes   b * (a*G)_x = {shared_bob}")
print(f"Match? {shared_alice == shared_bob}")
print(f"\nThis shared secret is then fed into HKDF to derive")
print(f"the symmetric encryption keys for the TLS session.")

Why X25519 Over NIST Curves?

TLS 1.3 supports both NIST P-256 and X25519, but X25519 is the overwhelmingly preferred choice. Here is why:

Property	X25519 (Curve25519)	P-256 (NIST)
Constant-time	By design (Montgomery ladder)	Requires careful implementation
Twist-secure	Yes (twist cofactor = 4)	No (twist is vulnerable)
Input validation	Minimal (any 32 bytes is valid)	Must check point on curve
Side-channel resistance	Built into the design	Implementation-dependent
Speed	Very fast (special prime $2^{255}-19$)	Moderate
Specification clarity	Complete, single document	Complex, multiple standards
Trust	Transparent design by Bernstein	"Nothing up my sleeve" concerns

The key advantage: X25519 is hard to implement wrong. The Montgomery ladder is naturally constant-time, twist security means input validation is minimal, and the function accepts any 32-byte string as a valid private key (after clamping).

# === Key clamping: how X25519 processes private keys ===
def clamp_key(key_bytes):
    """X25519 key clamping (RFC 7748).
    Takes 32 random bytes and produces a valid scalar.
    
    Three modifications:
    1. Clear the lowest 3 bits (ensures scalar is a multiple of 8 = cofactor)
    2. Clear the highest bit (ensures scalar < 2^255)
    3. Set the second-highest bit (ensures constant-time ladder runs all 255 steps)
    """
    k = list(key_bytes)
    k[0] &= 248    # clear lowest 3 bits: k is multiple of 8
    k[31] &= 127   # clear highest bit: k < 2^255
    k[31] |= 64    # set bit 254: ensures uniform timing
    return bytes(k)

# Demonstrate clamping
import os
raw_key = os.urandom(32)
clamped = clamp_key(raw_key)

raw_int = int.from_bytes(raw_key, 'little')
clamped_int = int.from_bytes(clamped, 'little')

print(f"Raw key (first byte):     {raw_key[0]:08b}")
print(f"Clamped key (first byte): {clamped[0]:08b}")
print(f"  Lowest 3 bits cleared: ensures scalar is multiple of cofactor 8")
print(f"\nRaw key (last byte):      {raw_key[31]:08b}")
print(f"Clamped key (last byte):  {clamped[31]:08b}")
print(f"  Bit 255 cleared, bit 254 set: ensures uniform ladder execution")
print(f"\nClamped scalar mod 8 = {clamped_int % 8} (always 0)")
print(f"This kills any small-subgroup component (cofactor = 8).")

Concept Map: Module 06 Concepts in TLS 1.3

Module 06 Concept	TLS 1.3 Application
Scalar multiplication $kP$	X25519 function: compute shared secret
ECDLP hardness	Security of the key exchange
Curve choice (Montgomery form)	Enables $x$-only arithmetic, constant-time
Group order and cofactor	Key clamping clears cofactor bits
Twist security (Break notebook)	Curve25519 is twist-secure by design
Point validation	X25519 needs minimal validation (twist-secure)

Summary

Concept	Key idea
Curve25519	A Montgomery curve $y^2 = x^3 + 486662x^2 + x$ over $\mathbb{F}_{2^{255}-19}$, designed for speed and safety.
X25519 (x-only DH)	Scalar multiplication uses only x-coordinates via the Montgomery ladder, so the y-coordinate is never computed.
Constant-time by design	The Montgomery ladder performs the same operations for every scalar bit, providing natural side-channel resistance.
Twist security	Curve25519 is twist-secure, so implementations do not need to validate whether points are on the curve or the twist.
Key clamping	The scalar is forced to be a multiple of the cofactor (8), killing small-subgroup attacks.
Fast arithmetic	The prime $p = 2^{255} - 19$ enables especially efficient modular reduction.

Module 06 gave you the foundations: scalar multiplication, ECDLP hardness, curve group structure. X25519 is those foundations engineered into a protocol that is fast, secure, and hard to misimplement.

---

Back to Module 06: Elliptic Curves