AntInLoop

Diffie–Hellman Key Exchange

Diffie–Hellman Key Exchange allows two parties to establish a shared secret over an insecure channel using modular exponentiation and the hardness of the Discrete Logarithm Problem.

Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code

Diffie–Hellman Key Exchange

Diffie–Hellman Key Exchange (1976) enables Alice and Bob to agree on a shared secret key over a completely public network—without ever transmitting the secret! Its security relies on the Discrete Logarithm Problem: computing $g^a \bmod p$ is fast ($O(\log a)$), but recovering $a$ from $(g, p, g^a \bmod p)$ is computationally infeasible for large primes $p$.

How It Works

1. Agree publicly on a large prime $p$ and primitive root (generator) $g$.

2. Alice picks private $a$ and sends $A = g^a \bmod p$.

3. Bob picks private $b$ and sends $B = g^b \bmod p$.

4. Both compute the identical shared secret:

$S = B^a \bmod p = (g^b)^a \bmod p = g^{ab} \bmod p = (g^a)^b \bmod p = A^b \bmod p$

---

Practice Problems

Easy

1. Simulate Diffie–Hellman Shared Secret Exchange

Compute Alice's and Bob's public keys and verify both derive the exact same shared secret.

Approach: Use Fast Exponentiation modPow(g, secret, p). Time: $O(\log p)$.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>

long long modPow(long long base, long long exp, long long mod) {
    long long res = 1;
    for (base %= mod; exp > 0; exp >>= 1, base = base * base % mod)
        if (exp & 1) res = res * base % mod;
    return res;
}

int main() {
    long long p = 23, g = 5;
    long long a = 6, b = 15; // private keys
    long long A = modPow(g, a, p);
    long long B = modPow(g, b, p);
    long long sAlice = modPow(B, a, p);
    long long sBob   = modPow(A, b, p);
    std::cout << "A=" << A << " B=" << B << " shared=" << sAlice << " match=" << (sAlice == sBob) << "\n";
    return 0;
}

</details>

---

Related Algorithms