weak-generator-attack.ipynb

Kernel: SageMath 10.0

Break: Weak Generator Attack

Module 01 | Breaking Weak Parameters

A generator that doesn't generate the full group shrinks the key space dramatically.

Why This Matters

Diffie-Hellman requires a generator $g$ of the full multiplicative group $\mathbb{Z}/p\mathbb{Z}^*$. This group has order $\phi(p) = p - 1$, so a proper generator satisfies $\text{ord}(g) = p - 1$.

But what if someone picks $g$ carelessly? If $g$ has order $d < p - 1$, then all powers $g^0, g^1, \ldots, g^{d-1}$ cycle through only $d$ distinct values.

The secret exponent $a$ now lives in $\{0, 1, \ldots, d-1\}$ instead of $\{0, 1, \ldots, p-2\}$. The attacker's brute-force search space shrinks from $p - 1$ down to $d$.

The Scenario

Alice and Bob agree on $p = 23$ and pick $g = 2$ as their generator. They don't check whether $g$ actually generates the full group.

Spoiler: $\text{ord}(2) = 11$ in $\mathbb{Z}/23\mathbb{Z}^*$, not $22$. The key space is cut in half.

# === Setup ===
p = 23
g_weak = 2   # Not a primitive root mod 23!

print(f'p = {p}, p - 1 = {p - 1}')
print(f'|Z/{p}Z*| = {p - 1}')
print(f'g = {g_weak}')
print(f'Order of g: ord({g_weak}) = {Mod(g_weak, p).multiplicative_order()}')
print()
print(f'Expected order for full group: {p - 1}')
print(f'Actual order: {Mod(g_weak, p).multiplicative_order()}')
print(f'\nProblem: g only generates HALF the group!')

# === What subgroup does g=2 actually generate? ===
ord_g = Mod(g_weak, p).multiplicative_order()
subgroup = sorted([power_mod(g_weak, i, p) for i in range(Integer(ord_g))])

print(f'Subgroup <{g_weak}> mod {p}:')
print(f'  Elements: {subgroup}')
print(f'  Size: {len(subgroup)} out of {p - 1}')
print()

# What elements are NOT reachable?
full_group = set(range(1, p))
missing = sorted(full_group - set(subgroup))
print(f'Elements NOT in <{g_weak}>: {missing}')
print(f'Missing: {len(missing)} elements')
print()
print('Any public key A = g^a mod p MUST be one of the', len(subgroup), 'subgroup elements.')
print('An attacker immediately knows the key space is half the expected size.')

The Attack

Alice picks a secret $a$ and publishes $A = g^a \bmod p$. Since $\text{ord}(g) = 11$, we know $a \bmod 11$ determines $A$ completely. So we only need to search $a \in \{0, 1, \ldots, 10\}$.

# === Alice's key ===
alice_secret = 17  # Alice thinks this is safe in {0, ..., 21}
A = power_mod(g_weak, alice_secret, p)

print(f'Alice\'s secret: a = {alice_secret}')
print(f'Alice\'s public key: A = {g_weak}^{alice_secret} mod {p} = {A}')
print()
print(f'Attacker sees: g = {g_weak}, p = {p}, A = {A}')

# === Brute force with weak generator: only 11 values to try! ===
print(f'Brute force search (only {ord_g} candidates):\n')

for a_guess in range(Integer(ord_g)):
    candidate = power_mod(g_weak, a_guess, p)
    match = '  ← FOUND!' if candidate == A else ''
    print(f'  {g_weak}^{a_guess:2d} mod {p} = {candidate:2d}{match}')
    if candidate == A:
        recovered = a_guess

print(f'\nRecovered: a ≡ {recovered} (mod {ord_g})')
print(f'Original:  a = {alice_secret}')
print(f'Check: {alice_secret} mod {ord_g} = {alice_secret % Integer(ord_g)}')
print(f'\nThe recovered exponent gives the same public key: {g_weak}^{recovered} mod {p} = {power_mod(g_weak, recovered, p)}')

Cost Comparison: Weak vs. Proper Generator

# === Compare with a proper generator ===
g_strong = primitive_root(p)
print(f'Proper generator (primitive root): g = {g_strong}')
print(f'Order of {g_strong} mod {p}: {Mod(g_strong, p).multiplicative_order()}')
print()

print('=== Brute Force Cost ===')
print(f'Weak generator   (g={g_weak}, ord={ord_g}): search {ord_g:3d} values')
print(f'Proper generator (g={g_strong}, ord={p-1}):  search {p-1:3d} values')
print(f'Speedup for attacker: {(p-1) / Integer(ord_g):.1f}x')
print()

print('In this toy example, the search space only halved.')
print('But consider a real prime p ~ 2^2048:')
print('  If ord(g) = (p-1)/1000, attacker saves a factor of 1000.')
print('  If ord(g) ~ 2^256 instead of 2^2048, the DLP becomes trivial.')
print('  The attacker\'s difficulty depends on ord(g), NOT on p!')

The Fix: Always Verify the Generator

Before using $g$ in Diffie-Hellman, check that $g$ is a primitive root modulo $p$, meaning $\text{ord}(g) = p - 1$.

Efficient test (no need to compute the full order):

• Factor $p - 1 = q_1^{e_1} \cdot q_2^{e_2} \cdots q_k^{e_k}$

• For each prime factor $q_i$, check that $g^{(p-1)/q_i} \not\equiv 1 \pmod{p}$

• If all checks pass, $g$ is a primitive root

def is_generator(g, p):
    """Check if g is a primitive root mod p (generates the full group)."""
    if not is_prime(p):
        raise ValueError('p must be prime')
    order = p - 1
    for q, _ in factor(order):
        if power_mod(g, order // q, p) == 1:
            return False
    return True

# Test our two generators
print(f'is_generator({g_weak}, {p}) = {is_generator(g_weak, p)}')
print(f'is_generator({g_strong}, {p}) = {is_generator(g_strong, p)}')
print()

# Find ALL primitive roots mod 23
prim_roots = [g for g in range(2, p) if is_generator(g, p)]
print(f'All primitive roots mod {p}: {prim_roots}')
print(f'Count: {len(prim_roots)} out of {p - 1} elements')
print(f'Expected count (Euler totient of p-1): euler_phi({p - 1}) = {euler_phi(p - 1)}')

Exercise: Explore Further

1. Other weak generators: Try $g = 3, 4, 6, 8$ mod $23$. What are their orders? Which gives the attacker the biggest advantage?

2. Subgroup structure: The subgroups of $\mathbb{Z}/23\mathbb{Z}^*$ have orders dividing $22 = 2 \times 11$. List all possible subgroup orders and find a generator for each.

3. Real-world defense: In practice, DH often uses a prime $p = 2q + 1$ (safe prime) and a generator of the order-$q$ subgroup. Why is this safe even though $g$ doesn't generate the full group?

Summary

Generator	Order	Key Space	Attacker Cost
$g = 2$ (weak)	$11$	$11$ values	$11$ trials
$g = 5$ (primitive root)	$22$	$22$ values	$22$ trials

Key takeaways:

• A generator's order determines the effective key space, not $p$.

• Using a non-primitive-root as generator shrinks the key space to $\text{ord}(g)$.

• Always verify $g$ is a primitive root, or at minimum that $\text{ord}(g)$ is large enough.

• The efficient primitive root test checks $g^{(p-1)/q} \neq 1$ for each prime factor $q$ of $p - 1$.

---

Back to Module 01: Modular Arithmetic & Groups