This table shows all values of g^k mod p for k = 1, 2, ..., p-1. The generator g produces all non-zero residues if it's a primitive root.
Given g, p, and A = g^a mod p, finding a is computationally hard for large p. This is the foundation of DH security.
p, g, A, B — all public values transmitted in the clear
a, b, or s = g^(ab) mod p — requires solving discrete logarithm
Man-in-the-middle attack: Mallory can intercept and substitute their own public values. DH alone provides NO authentication.
-
Each exchange uses fresh random keys. Compromising one session doesn't compromise past or future sessions.
-
If p is small, Eve can try all possible private keys to find the shared secret:
Diffie-Hellman operates in the multiplicative group of integers modulo p, denoted Z*_p = {1, 2, ..., p-1}.
For DH to be secure, g should be a primitive root (generator) of Z*_p, meaning the powers of g produce all elements of the group.
The order of Z*_p is phi(p) = p-1 (Euler's totient). If g is a primitive root, then g^(p-1) = 1 mod p (Fermat's little theorem), and no smaller power equals 1.
The key insight: exponentiation is commutative in cyclic groups.
Alice computes: B^a = (g^b)^a = g^(ba) mod p
Bob computes: A^b = (g^a)^b = g^(ab) mod p
Since ba = ab (multiplication is commutative), both arrive at the same value g^(ab) mod p.
The security relies on the Computational Diffie-Hellman assumption: given g, g^a, g^b, computing g^(ab) is hard without knowing a or b.