dh-parameter-selection.ipynb

Kernel: SageMath 10.0

Connect: Diffie-Hellman Parameter Selection

Module 01 | Real-World Connections

Generators, orders, and safe primes --- Module 01's concepts determine whether Diffie-Hellman is secure.

Introduction

Diffie-Hellman key exchange lives in $(\mathbb{Z}/p\mathbb{Z})^*$, the multiplicative group of integers mod a prime $p$. The security depends on choosing the right $p$ and $g$ --- and Module 01 taught you exactly what "right" means.

In this notebook, we'll trace how generators, element orders, safe primes, and Lagrange's theorem directly determine whether a Diffie-Hellman instantiation is secure or broken.

Generator = DH Base

In Diffie-Hellman, both parties compute powers of a shared base $g$ modulo a prime $p$. For security, $g$ must be a generator of $(\mathbb{Z}/p\mathbb{Z})^*$ --- meaning $g$ has order $p-1$ and its powers produce every element of the group.

If $g$ is not a generator, then the powers $g^1, g^2, \ldots$ only cover a subgroup, which shrinks the space an attacker must search.

# Pick a safe prime and a generator
p = 2267  # safe prime: 2267 = 2 * 1133 + 1, 1133 is prime
q = (p - 1) // 2
print(f'Safe prime p = {p}')
print(f'q = (p-1)/2 = {q}, is_prime(q) = {is_prime(q)}')

# Find a generator
g = primitive_root(p)
print(f'Generator g = {g}')
print(f'Order of g = {Mod(g, p).multiplicative_order()} (should be {p-1})')

The Key Exchange

Diffie-Hellman lets two parties (Alice and Bob) establish a shared secret over a public channel:

1. Alice picks a secret $a$, sends $A = g^a \bmod p$.

2. Bob picks a secret $b$, sends $B = g^b \bmod p$.

3. Both compute the shared secret: $s = g^{ab} \bmod p$.

An eavesdropper sees $g$, $p$, $A$, and $B$, but computing $s$ requires solving the discrete logarithm problem (DLP).

# Alice picks secret a, computes A = g^a mod p
a = 1234  # Alice's secret
A = power_mod(g, a, p)

# Bob picks secret b, computes B = g^b mod p
b = 5678  # Bob's secret
B = power_mod(g, b, p)

# Shared secret
s_alice = power_mod(B, a, p)  # Alice computes B^a
s_bob = power_mod(A, b, p)    # Bob computes A^b
print(f'Alice sends: A = g^a = {A}')
print(f'Bob sends:   B = g^b = {B}')
print(f'Alice computes: B^a = {s_alice}')
print(f'Bob computes:   A^b = {s_bob}')
print(f'Shared secret matches: {s_alice == s_bob}')

Why Parameters Matter: The Danger of Bad Choices

Not all primes and generators are created equal. If the parameters are poorly chosen, Diffie-Hellman can be broken even without solving the general DLP.

Two key dangers (explored in the break notebooks):

1. Smooth-order groups: If $p - 1$ has only small prime factors, the Pohlig-Hellman algorithm can solve DLP efficiently by working in each small subgroup separately.

2. Weak generators: If $g$ generates a small subgroup of $(\mathbb{Z}/p\mathbb{Z})^*$, the shared secret lives in that subgroup, drastically reducing the search space.

This is why we need safe primes and full generators.

Safe Primes: Lagrange's Theorem in Action

A safe prime is a prime $p$ where $q = (p-1)/2$ is also prime.

Why does this help? By Lagrange's theorem, every subgroup order must divide the group order $|G| = p - 1 = 2q$. If $q$ is prime, the only divisors of $p - 1$ are:

$$1, \quad 2, \quad q, \quad 2q$$

So the only subgroups have order $1$ (trivial), $2$ (just $\{1, -1\}$), $q$ (half the group), or $2q = p-1$ (the full group). There are no small subgroups to exploit.

# Compare subgroup structure: safe prime vs non-safe prime
p_safe = 2267
p_unsafe = 2269  # 2269 is prime, but (2269-1) = 2268 = 2^2 * 3^3 * 7 * 3

print(f'Safe prime p = {p_safe}')
print(f'  p-1 = {p_safe - 1} = {factor(p_safe - 1)}')
print(f'  Possible subgroup orders (divisors of p-1): {divisors(p_safe - 1)}')
print()
print(f'Non-safe prime p = {p_unsafe}')
print(f'  p-1 = {p_unsafe - 1} = {factor(p_unsafe - 1)}')
print(f'  Possible subgroup orders (divisors of p-1): {divisors(p_unsafe - 1)}')
print(f'  Many small subgroups to exploit!')

Parameter Validation

Before using DH parameters, you should validate them. Here's a checklist derived directly from Module 01 concepts:

def validate_dh_params(p, g):
    """Check DH parameters are secure"""
    checks = []
    checks.append(('p is prime', is_prime(p)))
    q = (p - 1) // 2
    checks.append(('p is safe prime (q=(p-1)/2 is prime)', is_prime(q)))
    checks.append(('g is a generator', Mod(g, p).multiplicative_order() == p - 1))
    checks.append(('g != 1', g != 1))
    checks.append(('g != p-1', g != p - 1))
    for desc, ok in checks:
        status = 'PASS' if ok else 'FAIL'
        print(f'  [{status}] {desc}')
    return all(ok for _, ok in checks)

print('=== Validating our parameters ===')
print(f'p = {p}, g = {g}')
result = validate_dh_params(p, g)
print(f'Overall: {"SECURE" if result else "INSECURE"}')

# Test with deliberately bad parameters
print('=== Validating BAD parameters ===')
print(f'p = {p}, g = 1')
validate_dh_params(p, 1)
print()
print(f'p = {p}, g = {p-1}')
validate_dh_params(p, p - 1)

Real-World Parameters: RFC 3526

In practice, DH parameters are not generated on the fly. Standardized groups from RFC 3526 are used --- these specify huge safe primes (1536-bit to 8192-bit) that have been carefully vetted.

For example, the 1536-bit MODP group uses a prime of the form:

$$p = 2^{1536} - 2^{1472} - 1 + 2^{64} \cdot (\lfloor 2^{1406} \pi \rfloor + 741804)$$

The generator is simply $g = 2$. This works because for these carefully chosen primes, $2$ is a generator of the full group $(\mathbb{Z}/p\mathbb{Z})^*$.

The takeaway: the concepts from Module 01 (generators, orders, safe primes) are exactly what standards bodies check when selecting parameters for worldwide use.

Concept Map: Module 01 $\to$ Diffie-Hellman

Module 01 Concept	DH Application
Generators	DH base $g$ must generate $(\mathbb{Z}/p\mathbb{Z})^*$
Element order	$g$ must have order $p-1$ (full group order)
Safe primes	$p = 2q+1$ prevents small-subgroup attacks
Lagrange's theorem	Constrains subgroup sizes, limits attack surface
Modular exponentiation	All DH computations ($g^a$, $g^b$, $g^{ab}$)
Discrete logarithm	Security assumption: given $g^a$, finding $a$ is hard

What's Next

Module 05 implements full Diffie-Hellman key exchange and the attacks against it --- including Pohlig-Hellman (exploiting smooth orders) and small-subgroup confinement (exploiting weak generators). You'll see firsthand why every parameter choice matters.

Summary

Concept	Key idea
DH group	$(\mathbb{Z}/p\mathbb{Z})^*$, the cyclic group we studied all module
Base $g$	Must be a generator (order $p-1$), ensuring the shared secret can be any group element
Safe primes	$p = 2q + 1$ with $q$ prime prevents small-subgroup attacks, a direct consequence of Lagrange's theorem
Parameter validation	Checks exactly the properties we learned: primality, generator status, order
Real-world standards	RFC 3526 encodes these same mathematical requirements for worldwide use

The abstract algebra from Module 01 is not background theory. It is the security engineering.