Breaking Toy ECC with Pohlig-Hellman

Breaking Toy ECC with Pohlig-Hellman

Introduction

The security of elliptic curve cryptography rests on the discrete logarithm problem. Given a base point G and a public point Q = d * G, finding the secret multiplier d is supposed to be hopeless. It usually is, but the difficulty does not come from the size of the field, or from how big the coordinates look. It comes from one number: the order of the group, and specifically its largest prime factor.

Pohlig-Hellman is the attack that proves it. When the group order factors entirely into small primes, a property called being smooth, the big discrete log splits into several tiny ones, one per prime factor, which are then stitched back together with the Chinese Remainder Theorem. This guide runs the full attack on a toy curve whose order is 13-smooth, and recovers the private key by solving discrete logs in groups no larger than 13 elements.

Table of Contents

• The Discrete Log on a Curve
• Divide and Conquer by Prime Factor
• Inside One Prime Power
• Putting It Back Together
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

The Discrete Log on a Curve

A point G on an elliptic curve generates a cyclic group of some size n, its order. The multiples G, 2G, 3G, and so on cycle through n points before returning to the start. The public key is Q = d * G for a secret d between 1 and n, and breaking the key means finding d.

The brute-force approach adds G to itself over and over until it hits Q, which takes up to n steps. Baby-step giant-step and Pollard’s rho cut that to about the square root of n. For a real curve n is a prime near 2^256, so the square root is near 2^128, and the problem is settled: it cannot be done. Pohlig-Hellman changes the picture completely, but only when n is not prime.

Divide and Conquer by Prime Factor

Suppose the order factors as n = p1^e1 * p2^e2 * ..., a product of prime powers. Pohlig-Hellman finds d modulo each prime power separately, then combines the pieces. The trick for one factor p^e is multiplication by a cofactor. Let m = n / p^e. Then the point m * G has order exactly p^e, a small cyclic group, and m * Q equals d times that point. So the discrete log of m * Q to the base m * G, computed inside the little group of size p^e, gives d modulo p^e.

Each of those small discrete logs lives in a group whose size is one prime power. The largest of them is set by the largest prime power dividing n. If every prime factor is small, every subgroup is small, and every small discrete log is easy. The size of the field never enters into it.

Inside One Prime Power

Solving the discrete log modulo p^e does not even need the whole subgroup at once. It is cracked one base-p digit at a time. Write the unknown as d = d0 + d1*p + d2*p^2 + ..., with each digit between 0 and p - 1. The lowest digit d0 is found by pushing everything up into the subgroup of order p, the smallest one, where a discrete log over just p elements reveals it. Subtracting its contribution exposes the next digit, and so on up the powers.

So the hardest step anywhere in the whole attack is a discrete log in a group of order p, the largest prime factor of n. On the toy curve here that largest factor is 13, so the worst case is a discrete log over 13 points, which a handful of additions settles. That single number, 13, is the real difficulty of the entire key.

Putting It Back Together

After the loop, the attacker holds d modulo each prime power: d modulo p1^e1, d modulo p2^e2, and so on. Those prime powers are coprime, and their product is n, so the Chinese Remainder Theorem combines them into a single value of d modulo n. That is the private key. One check, multiplying the recovered d by G and confirming it equals Q, proves the recovery.

The whole attack never searches the full group. It solves a few tiny discrete logs and does one CRT, and the private key drops out. The field has about a million elements, but the key falls in a few hundred point additions, because the order was smooth.

Interactive Visualizer

The visualizer above runs the real Pohlig-Hellman attack on the toy curve. It shows the group order factored into its prime powers, solves the discrete log inside each small subgroup, displays the partial result d modulo each prime power, and combines them with the Chinese Remainder Theorem to recover the secret d, verifying it against the public point. Every point and every step is computed by the genuine curve arithmetic, with nothing faked.

Change the secret multiplier and run it again. However large the secret looks, it falls apart the same way, because the attack is bounded by the largest prime factor of the order, not by the secret or the field. That is the entire lesson of Pohlig-Hellman in one picture.

A Worked Example

The curve is y^2 = x^3 + 643550 x + 26739 over the field of 1000003 elements. The base point G = (6, 161003) generates a group of order n = 499200, which factors as 2^9 * 3 * 5^2 * 13. The secret is d = 31337, giving the public point Q = (518055, 213334). The attacker, knowing only G and Q, solves one small discrete log per prime power:

d = 105 (mod 512)     # the 2^9 part
d = 2   (mod 3)
d = 12  (mod 25)      # the 5^2 part
d = 7   (mod 13)
Chinese Remainder Theorem -> d = 31337

The private key comes back exactly. The whole attack used about 800 point additions. Baby-step giant-step over the full group would need roughly 1,400, and brute force about 499,200, but the real point is sharper than any of those numbers: the hardest discrete log anywhere was over a group of 13 elements. A secure curve makes n a single large prime, so there is no small subgroup to exploit and this attack does nothing.

Python Implementation

The code is self-contained and runnable. It builds the curve, finds a generator, and runs Pohlig-Hellman: a baby-step giant-step for each small subgroup, the digit-by-digit climb through each prime power, and a CRT to finish.

# pohlig_hellman.py
#
# Pohlig-Hellman discrete log on a toy elliptic curve. ECC security is NOT about the field size; it is
# about the largest prime factor of the group order n. If n is smooth (all prime factors small), the big
# discrete log Q = d*G splits into one small discrete log per prime power of n (each in a subgroup whose
# size is that prime power), solved digit-by-digit in the order-p subgroup, then combined with the Chinese
# Remainder Theorem. This toy curve's order is 13-smooth, so the hardest step is a DLP over 13 points.
import math

P = 1000003
A = 643550
B = 26739
GROUP = 998400                      # #E = 2^10 * 3 * 5^2 * 13


def inv(a):
    return pow(a % P, P - 2, P)


def add(Pt, Qt):
    if Pt is None:
        return Qt
    if Qt is None:
        return Pt
    x1, y1 = Pt
    x2, y2 = Qt
    if x1 == x2 and (y1 + y2) % P == 0:
        return None
    if Pt == Qt:
        lam = (3 * x1 * x1 + A) * inv(2 * y1) % P
    else:
        lam = (y2 - y1) * inv(x2 - x1) % P
    x3 = (lam * lam - x1 - x2) % P
    return (x3, (lam * (x1 - x3) - y1) % P)


def mul(k, Pt):
    k %= GROUP * 4                  # any point's order divides GROUP; handles negative k too
    R = None
    while k > 0:
        if k & 1:
            R = add(R, Pt)
        Pt = add(Pt, Pt)
        k >>= 1
    return R


def factor(n):
    f = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            f[d] = f.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        f[n] = f.get(n, 0) + 1
    return f


def point_order(G, group_order):
    order = group_order
    for q, e in factor(group_order).items():
        for _ in range(e):
            if mul(order // q, G) is None:
                order //= q
            else:
                break
    return order


def find_generator(group_order):
    x = 1
    while x < P:
        rhs = (x * x * x + A * x + B) % P
        if pow(rhs, (P - 1) // 2, P) == 1:          # rhs is a square -> a point exists
            G = (x, pow(rhs, (P + 1) // 4, P))      # sqrt, since P % 4 == 3
            o = point_order(G, group_order)
            if o >= group_order // 2:               # take a large-order point
                return G, o
        x += 1
    raise RuntimeError("no generator")


def dlp_small(g, h, q):
    # baby-step giant-step: find x in [0, q) with x*g == h
    m = math.isqrt(q) + 1
    table = {}
    cur = None
    for j in range(m):
        table.setdefault(cur, j)
        cur = add(cur, g)
    giant = mul(-(m % q), g)
    gamma = h
    for i in range(m):
        if gamma in table:
            return (i * m + table[gamma]) % q
        gamma = add(gamma, giant)
    raise RuntimeError("dlp failed")


def crt(residues, moduli):
    M = 1
    for m in moduli:
        M *= m
    x = 0
    for r, m in zip(residues, moduli):
        Mi = M // m
        x += r * Mi * pow(Mi, -1, m)
    return x % M


def pohlig_hellman(G, Q, n):
    residues, moduli, steps = [], [], []
    for q, e in factor(n).items():
        qe = q ** e
        cofactor = n // qe
        Gq = mul(cofactor, G)                       # order q^e
        Qq = mul(cofactor, Q)                       # = d * Gq
        x = 0
        gamma = mul(q ** (e - 1), Gq)               # order q
        for k in range(e):                          # recover d mod q^e digit by digit (base q)
            hk = mul(q ** (e - 1 - k), add(Qq, mul(-x, Gq)))
            x += dlp_small(gamma, hk, q) * (q ** k)
        residues.append(x % qe)
        moduli.append(qe)
        steps.append((qe, x % qe))
    return crt(residues, moduli), steps


if __name__ == "__main__":
    G, n = find_generator(GROUP)
    print("generator G =", G, " order n =", n, "=", factor(n))
    d_secret = 31337 % n
    Q = mul(d_secret, G)
    print("secret d =", d_secret, " public Q =", Q)

    d, steps = pohlig_hellman(G, Q, n)
    for qe, r in steps:
        print(f"   d = {r} (mod {qe})")
    print("CRT -> d =", d)
    print("MATCH:", mul(d, G) == Q, " exact:", d == d_secret)

Running it prints the worked example:

generator G = (6, 161003)  order n = 499200 = {2: 9, 3: 1, 5: 2, 13: 1}
secret d = 31337  public Q = (518055, 213334)
   d = 105 (mod 512)
   d = 2 (mod 3)
   d = 12 (mod 25)
   d = 7 (mod 13)
CRT -> d = 31337
MATCH: True  exact: True

Limitations

The attack is a real break, but only against a specific weakness:

• It needs a smooth order. Pohlig-Hellman is only fast when the group order has no large prime factor. Its cost is governed by the largest prime factor of n, so a single big prime factor stops it cold, no matter how many small factors sit alongside.
• This is a toy curve. The field here has about a million elements, chosen so the arithmetic is instant and the points are small enough to read. Real curves are vastly larger, but the method is identical; only the sizes change.
• The field size is irrelevant to the attack. Enlarging the field without fixing the order does nothing. A huge field with a smooth order is just as broken, which is precisely the point this attack makes.
• Finding the order can take work. The attack assumes the group order is known and factored. On a real curve the order is found by point counting, such as Schoof’s algorithm, and then factored, before Pohlig-Hellman applies.

Security Status

• Secure curves use a prime order. Standard curves like P-256 and Curve25519 are chosen so the group order is a large prime, or a large prime times a tiny cofactor. With no small subgroups to split off, Pohlig-Hellman gains nothing, and the discrete log stays at its full square-root difficulty.
• The order is the security parameter, not the field. This is the headline lesson. An elliptic curve’s strength is the largest prime factor of its group order. A beautiful large field wrapped around a smooth order offers no security at all.
• Checking the order is part of curve selection. Anyone choosing or generating a curve must verify that its order is prime, or nearly so, precisely to rule out this attack. It is a standard, non-negotiable check, and the named curves have all passed it.

FAQ

What does it mean for the order to be smooth?

A number is smooth when all of its prime factors are small. The group order here, 499200, factors into 2, 3, 5 and 13, none larger than 13, so it is 13-smooth. Smoothness is exactly the property Pohlig-Hellman exploits, because it means every subgroup it works in is small.

Why does the field size not matter?

Pohlig-Hellman works inside subgroups whose sizes are the prime power factors of the group order, never the field. A larger field changes the coordinates but not the order’s factorization. If the order stays smooth, the attack stays fast, however large the field grows.

How is each small discrete log solved?

In a subgroup of prime order p, the discrete log is found with baby-step giant-step, which takes about the square root of p steps. For prime powers, the solution is built one base-p digit at a time, each digit needing only a discrete log in the order-p subgroup.

Does this break real elliptic curve cryptography?

No. Real curves are specifically chosen so the group order is a large prime, which leaves no small subgroups for Pohlig-Hellman to use. The attack only works on curves with smooth or partly smooth orders, which secure curve selection rules out.

What is the Chinese Remainder Theorem doing here?

It reassembles the answer. The attack learns d modulo each prime power separately. Since those prime powers are coprime and multiply to the full order, the Chinese Remainder Theorem combines the pieces into the unique value of d modulo the order, which is the key.

References

1. Pohlig, Stephen, and Martin Hellman. “An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance,” IEEE Transactions on Information Theory, 1978.

2. Hankerson, Darrel, Alfred Menezes, and Scott Vanstone. “Guide to Elliptic Curve Cryptography,” 2004.

3. The elliptic curve cryptography guide on this site: /blog/ecc_guide/