THE GARDEN

ECDH (Elliptic Curve Diffie-Hellman) — Textbook Construction

Updated 13 Sep 2026

• •

  What it is

  • •

    The elliptic-curve analogue of ordinary Diffie-Hellman: instead of modular exponentiation in $\mathbb{F}_p^\times$, both parties use scalar multiplication of a fixed base point $G$ on an agreed elliptic curve. Alice picks a secret integer $n_A$ and publishes $Q_A=[n_A]G$; Bob does the same with $n_B$ and $Q_B=[n_B]G$; both then compute the same shared point $S=[n_A]Q_B=[n_B]Q_A=[n_An_B]G$, by associativity of scalar multiplication — exactly mirroring $g^{ab}$ in ordinary DH, just written additively. As with ordinary DH, the raw shared value (here, the $x$-coordinate of $S$) isn't used directly as a key; it's hashed (commonly SHA-1 or SHA-256) and truncated to derive a symmetric key. Security rests on the elliptic curve discrete logarithm problem (ECDLP) — recovering $n$ from $G$ and $[n]G$ — which, for a well-chosen curve, has no known algorithm faster than roughly $\sqrt q$ operations where $q$ is the order of the subgroup generated by $G$ (hence why real-world curves use a generator of large prime order).

• •

  When to apply

  • •

    The starting point for any ECC-flavored key-exchange challenge — deviations from this baseline (weak curves, bad point validation, small subgroups) are what specific ECC attacks target.

• •

  Symbols and assumptions

  • •

    $G$ is a curve point of order $n$; $a,b$ are private scalars modulo $n$. Public points are $A=aG$, $B=bG$. Coordinates are elements of the curve’s field, whose modulus need not equal $n$.

• •

  Math — step by step

  • •
    1. Alice computes $aB=a(bG)=(ab)G$. Bob computes $bA=b(aG)=(ab)G$. Associativity of the group law makes their shared points identical.
  • •
    2. Implement point operations with field arithmetic and scalar operations modulo the order of $G$. Validate received points and follow the protocol’s subgroup rules.
  • •
    3. Protocols commonly feed the shared x-coordinate, suitably encoded, into a KDF. Sharing an x-coordinate loses the sign of the point but can still suffice for deriving the same key.
• •

  Worked example

  • •

    Use the curve and $G=(5,1)$ from Elliptic Curves (Group Law Basics). Choose $a=2,b=3$. Then $A=(6,3)$ and $B=(10,6)$.

  • •

    Alice doubles $B$: $\lambda=(3\cdot10^2+2)/(2\cdot6)\equiv13\cdot12^{-1}\equiv13\cdot10\equiv11\pmod{17}$. This gives $x=121-20\equiv16$, $y=11(10-16)-6\equiv13$.

  • •

    Bob obtains $3A=6G=(16,13)$ as well. Check membership: $13^2\equiv16^3+2\cdot16+2\equiv16\pmod{17}$. Shared x-coordinate: 16.

• •

  Python

  • •

    S = nB * QA          # scalar multiplication (Sage's `*` operator on an EllipticCurve point)
    key_material = str(int(S[0])).encode()
    key = hashlib.sha1(key_material).digest()[:16]
    

• •

  SageMath

  • •

    E = EllipticCurve(GF(p), [a, b])
    QA = E(xA, yA)
    S = nB * QA
    

• •

  Related

  • •

    Elliptic Curves (Group Law Basics)

  • •

    Diffie-Hellman (Textbook Construction)

• •

  Cards

  • •

    What plays the role of g^ab in elliptic-curve Diffie-Hellman?

    • •

      The shared point S = [n_A][n_B]G = [n_B][n_A]G, computed via scalar multiplication instead of modular exponentiation.

  • •

    Why is it important that the generator point G have large prime order?

    • •

      It keeps the ECDLP hard within the subgroup actually used — a small or composite-order subgroup would make the discrete log tractable (analogous to why safe primes matter for ordinary DH).

◌ Explore connections in Graph view