THE GARDEN

Diffie-Hellman (Textbook Construction)

Updated 13 Sep 2026

• •

  What it is

  • •

    Diffie-Hellman key exchange lets two parties agree on a shared secret over a public channel, using the presumed difficulty of the discrete logarithm problem. Working in the multiplicative group of a finite field $\mathbb{F}_p^\times$ (integers mod a prime $p$, excluding 0), both parties agree on a public prime $p$ and a generator $g$ (a primitive element, whose powers $g, g^2, g^3, \dots$ eventually produce every nonzero element of $\mathbb{F}_p$). Each party picks a private integer ($a$ for Alice, $b$ for Bob), computes and shares a public value ($A=g^a \bmod p$, $B=g^b \bmod p$), and each combines their own private value with the other's public value to arrive at the same shared secret: $A^b \equiv g^{ab} \equiv B^a \pmod p$ — computable by either party, but (assumed) infeasible for an eavesdropper who only sees $g, p, A, B$. The raw shared secret integer is typically not used directly as an encryption key; instead it's hashed (e.g. SHA-1) and truncated to derive a symmetric key (for AES, etc.).

• •

  When to apply

  • •

    The starting point for reasoning about any Diffie-Hellman challenge — every attack in this domain (weak parameter choices, MITM parameter substitution, small/weak groups) is a deviation from this baseline that breaks one of its security assumptions.

• •

  Symbols and assumptions

  • •

    $p$ is prime; $g$ generates a subgroup of order $n$. Private exponents are $a,b$; public values are $A=g^a\bmod p$ and $B=g^b\bmod p$. Group elements reduce modulo $p$, while equivalent exponents differ by $n$.

• •

  Math — step by step

  • •
    1. Alice receives $B$ and computes $B^a=(g^b)^a=g^{ab}$. Bob receives $A$ and computes $A^b=(g^a)^b=g^{ab}$. Equality follows from multiplication of the exponents.
  • •
    2. A passive observer knows $p,g,A,B$ but not $a,b$. Recovering a private exponent solves a DLP; weak group order, bad public values, or an unauthenticated exchange can defeat the intended security.
  • •
    3. Convert the shared group element to bytes according to the protocol and derive a key with its specified KDF. The mathematical shared value is not automatically an AES key.
• •

  Worked example

  • •

    Use $p=23,g=2$, whose order is 11. Alice chooses $a=3$, so $A=8$. Bob chooses $b=7$, so $B=128\bmod23=13$.

  • •

    Alice: $13^2\equiv8$ and $13^3\equiv8\cdot13\equiv12$. Bob: $8^2\equiv18$, $8^4\equiv2$, then $8^7\equiv2\cdot18\cdot8\equiv12$.

  • •

    Check the common exponent: $ab=21\equiv10\pmod{11}$ and $2^{10}\bmod23=12$.

• •

  Python

  • •

    A = pow(g, a, p)                         # public value
    shared_secret = pow(B, a, p)             # == pow(A, b, p), computed by the other party
    import hashlib
    key = hashlib.sha1(str(shared_secret).encode()).digest()[:16]   # derive an AES key
    

• •

  SageMath

  • •

    Finding a generator by brute force is fine for small p, but Sage can construct the field with a primitive generator directly:

  • •

    k = GF(p, modulus='primitive')
    g = k.gen()
    

• •

  Related

  • •

    Extended Euclidean Algorithm

  • •

    Fermat's Little Theorem

• •

  Cards

  • •

    What mathematical assumption does Diffie-Hellman's security rest on?

    • •

      The discrete logarithm problem is hard in the chosen group — recovering a from g and A=g^a mod p is assumed computationally infeasible for well-chosen parameters.

  • •

    Why is a "safe prime" (p=2q+1 for prime q) a common parameter choice?

    • •

      It keeps p-1's factorization simple ({2,q}), protecting against Pohlig-Hellman-style attacks that exploit a smooth (many small prime factors) p-1.

◌ Explore connections in Graph view