Breaking Diffie-Hellman with Baby-Step Giant-Step

Breaking Diffie-Hellman with Baby-Step Giant-Step

Introduction

Diffie-Hellman publishes A = g^a mod p and keeps a secret. Recovering a from A, g, and p is the discrete logarithm problem. The base guide calls that infeasible for a large prime. That word is doing real work. For a small prime, the discrete log is easy. This post builds baby-step giant-step, the classic algorithm for exactly that problem. It turns “search all of p” into “search roughly √p” instead. That’s exactly why real Diffie-Hellman needs primes with hundreds of digits, not dozens.

Table of Contents

• Why √p Beats p
• The Attack: Meet in the Middle
• A Worked Example
• Python Implementation
• Interactive Visualizer
• Baby-Step Giant-Step vs. Brute Force
• Limitations of This Attack
• FAQ
• References

Why √p Beats p

A naive attack on A = g^a mod p just tries every a, one at a time, until one works. That’s brute force: up to p - 1 guesses, each one a modular exponentiation. For a 2048-bit prime, that number dwarfs anything computable. Even at this post’s small demo scale, one-by-one guessing misses an obvious shortcut.

Baby-step giant-step is that shortcut. It’s a meet-in-the-middle technique. Write the unknown exponent a as a = i·m + j, for some fixed m. The two smaller unknowns, i and j, each range only over roughly √p values, not all of p. Precompute every possible j value once, and store it in a lookup table. Then search over i values, checking each against that table instead of against A directly. A search of size p becomes two searches of roughly √p, costing table memory instead. That’s a real trade, not a free lunch. It’s still a trade that works. That’s the whole reason discrete-log security gets measured in bits of p, not digits.

The Attack: Meet in the Middle

Given a prime p, a generator g, and a public value A = g^a mod p:

1. Choose m = ⌈√(p−1)⌉. This splits the exponent’s range into m “giant” blocks, each containing m “baby” steps. That specific choice of m guarantees full coverage. Every exponent from 0 to p−2 can be written as i·m + j, both under m. isqrt(p−1) + 1 stays correct even when p−1 happens to be a perfect square.
2. Build the baby-step table. Compute gʲ mod p for every j from 0 to m−1, storing each value against its j.
3. Take giant steps. Compute A · (g⁻ᵐ)ⁱ mod p for i = 0, 1, 2, and so on. After each one, check whether that value already appears in the baby-step table.
4. Recover a on a match. If giant step i lands on the same value as baby step j, then a = i·m + j. That’s the discrete logarithm, found in roughly 2√p modular multiplications instead of p.

The algebra behind step 4 is short: A = g^a, and if a = i·m + j, then A · g^(-im) = g^j. The left side is exactly what the giant steps compute. The right side is exactly what the baby steps stored. Written as one line:

A · (g⁻ᵐ)ⁱ ≡ gʲ (mod p)  ⟹  a ≡ i·m + j (mod ord(g))

A match means both sides landed on the same group element. That can only happen when the exponents agree, modulo the order of g.

This post’s search covers the full range [0, p−1). That’s only because g happens to be a primitive root in this worked example. That gives ord(g) = p − 1. Real Diffie-Hellman almost always picks g differently. It generates a smaller, prime-order subgroup instead, of order q | (p − 1). That choice makes validating public keys cheap. Baby-step giant-step still applies there, unchanged. It just runs in O(√q) instead of O(√p). That’s the smaller subgroup a legitimate exchange actually uses.

A Worked Example

Using the visualizer’s default values: p = 104729, g = 12, and public key A = 2858.

1. Compute m. ⌈√(104728)⌉ = 324. Both the baby-step table and the giant-step search will need at most 324 entries each.
2. Build the baby-step table. g⁰ mod p = 1, g¹ mod p = 12, g² mod p = 144, and so on through g³²³ mod p, each stored against its exponent j.
3. Take giant steps. Starting from A = 2858, repeatedly multiply by g⁻³²⁴ mod p. Most early giant steps land on values absent from the table.
4. Find the match. The giant step at i = 19 lands on 40763. The baby-step table already has that value, at j = 265 (g²⁶⁵ mod p = 40763 too).
5. Recover a. a = i·m + j = 19 × 324 + 265 = 6421.

Twenty giant steps, one table of 324 baby steps, and the private exponent falls out: a = 6421. A brute-force search over the full range would average roughly 50,000 guesses.

Knowing a lets the attacker go further still, using only what’s already public. Bob’s public key is B = 58141; his private b = 51037 never enters the computation at all. The attacker computes s = B^a mod p = 74689, exactly the shared secret Alice and Bob agreed on.

Python Implementation

The interactive visualizer above runs this exact algorithm in JavaScript. Same baby-step table, same giant-step search. Here’s the same attack in Python.

Key Features

• Uses a dictionary for the baby-step table, giving O(1) lookups during the giant-step phase. That’s the data-structure choice that makes the time-memory trade-off pay off.
• Computes g⁻ᵐ via modular inverse, reusing the Extended Euclidean Algorithm this site’s breakers already lean on. Python 3.8+’s pow(g, -m, p) does the same job in one call. The explicit egcd still helps anyone learning how that inverse is actually computed.
• Stops at the first match, since the discrete logarithm is unique across this search’s range.

Code

# dh_bsgs_breaker.py
#
# Recovers a Diffie-Hellman private exponent a from the public value
# A = g^a mod p, using baby-step giant-step. Writes a = i*m + j and
# searches i and j separately, each over roughly sqrt(p) values, instead
# of searching all of p directly. A classic time-memory trade-off.

import math


def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y


def mod_inverse(a, m):
    g, x, _ = egcd(a % m, m)
    if g != 1:
        return None
    return x % m


def bsgs(g, A, p):
    m = math.isqrt(p - 1) + 1
    table = {}
    e = 1
    for j in range(m):
        if e not in table:  # first (smallest) j wins on any collision
            table[e] = j
        e = (e * g) % p

    g_inv_m = mod_inverse(pow(g, m, p), p)
    gamma = A
    for i in range(m):
        if gamma in table:
            return i * m + table[gamma]
        gamma = (gamma * g_inv_m) % p
    return None


if __name__ == '__main__':
    p, g, A = 104729, 12, 2858

    a = bsgs(g, A, p)
    print(f"Recovered private exponent a = {a}")
    assert pow(g, a, p) == A

    B = 58141
    shared_secret = pow(B, a, p)
    print(f"Derived shared secret: {shared_secret}")

Running this against the same values as the visualizer produces:

Recovered private exponent a = 6421
Derived shared secret: 74689

This matches the visualizer’s own result exactly. It matches the worked example above, step for step.

For Fun: The Whole Attack in 7 Lines

Same spirit as this site’s other golfed bonus sections. Not for learning the algorithm from. This version builds the baby-step table as one dictionary comprehension. It derives the shared secret right alongside the exponent.

import math
p,g,A=104729,12,2858
m=math.isqrt(p-1)+1; T={pow(g,j,p):j for j in range(m-1,-1,-1)}; c=pow(g,-m,p); G=A; a=None
for i in range(m):
    if G in T: a=i*m+T[G]; break
    G=G*c%p
print(f"Recovered private exponent a = {a}"); assert pow(g,a,p)==A
print(f"Derived shared secret: {pow(58141,a,p)}")

Verified to produce the identical Recovered private exponent a = 6421 and Derived shared secret: 74689. The dictionary comprehension counts j downward, starting at m−1 and ending at zero. On a collision, that leaves the smallest j behind. That matches what a hand-written loop would do. It also leans on Python 3.8+’s pow(g, -m, p) for the modular inverse. That replaces the readable version’s egcd and mod_inverse with one built-in call.

Interactive Visualizer

Try it above. Enter any prime, generator, and public key. Watch the baby-step table fill. Then watch the giant steps search for a match against it. Add Bob’s public key to see the attacker derive the same shared secret Bob computes.

Baby-Step Giant-Step vs. Brute Force

The security argument for real Diffie-Hellman doesn’t rest on brute force being the only attack. It rests on √p still being astronomically large for a properly sized prime. Baby-step giant-step is a genuine, meaningful speedup for the small primes this post demonstrates. Against 2048-bit or larger primes, √p still remains far beyond any computer’s reach. That’s exactly why modern parameter sizes exist.

Limitations of This Attack

Baby-step giant-step’s speedup is real but bounded. It turns an O(p) search into an O(√p) one, not into something sub-exponential. For the small demonstration primes here, that difference is dramatic. For a real 2048-bit prime, √p is still an astronomically large number. This algorithm offers no meaningful advantage there over just assuming discrete log is hard.

It also needs O(√p) memory to store the baby-step table, not just O(√p) time. For genuinely large p, that memory alone makes the algorithm impractical, long before time would. Even with free, unlimited memory, the O(√p) group operations themselves stay infeasible at cryptographic sizes.

Faster general-purpose attacks exist for suitably structured p. The Number Field Sieve variant for discrete logarithms is one. Against primes with the right structure, it can run substantially faster than √p. That’s exactly why safe-prime and Schnorr-group parameter choices still matter for classical Diffie-Hellman. Picking a large p alone isn’t the whole story. Pollard’s rho is another option, matching this algorithm’s asymptotic speed with far less memory. That makes it the usual choice whenever memory is the tighter constraint. Both are out of scope here, since this post focuses on the meet-in-the-middle idea specifically.

Baby-step giant-step and Pollard’s rho are also both generic group algorithms. Neither depends on anything specific to modular arithmetic. The same techniques apply just as directly to elliptic-curve discrete logarithms of comparable bit length. That’s why ECC key sizes get chosen with this exact attack in mind.

FAQ

How large a prime can baby-step giant-step realistically break?

Primes up to roughly 40-50 bits are crackable on ordinary hardware. Time and memory both stay reasonable at that scale. Well beyond it, the O(√p) memory requirement becomes the practical bottleneck before time does.

Does this attack need to know the generator g in advance?

Yes. Both g and p are public domain parameters in Diffie-Hellman, always known to any observer. The only unknown this attack targets is the private exponent a.

Why does discovering a let an attacker compute the shared secret?

Because the shared secret is s = B^a mod p, exactly Bob’s own computation. With a recovered, an attacker runs the formula themselves, standing in for Alice.

Is Pollard’s rho method different from baby-step giant-step?

Yes, though both solve the same problem in the same asymptotic time. Pollard’s rho needs only constant memory. It trades a small chance of extra iterations for skipping this post’s O(√p) table.

Does a safe prime protect against this attack?

No. Safe primes (p = 2q + 1) close off small-subgroup attacks. That’s a different vulnerability, covered in the base guide. Baby-step giant-step works against the full discrete logarithm either way. Only the prime’s actual size determines how long it takes.

References

1. Shanks, D. “Class Number, a Theory of Factorization, and Genera.” Symposium in Pure Mathematics, 1971 (the original baby-step giant-step source).

2. Menezes, A., van Oorschot, P., and Vanstone, S. “Handbook of Applied Cryptography.” CRC Press, 1996 (Chapter 3, discrete logarithm algorithms).

3. Wikipedia. “Baby-step giant-step.” Available at: https://en.wikipedia.org/wiki/Baby-step_giant-step