Discrete logarithm solver
Solve discrete logs with baby-step giant-step, Pollard’s rho, and Pohlig-Hellman - the last of which breaks any group with smooth order.
Open in ctfpalGiven g, h, and p, find x with g^x = h mod p. Diffie-Hellman and ECDSA rest on this being hard. It is hard only when the group order has a large prime factor - and CTF challenges routinely, deliberately, choose one that does not.
Pick the algorithm by the group order
| Situation | Method | Cost |
|---|---|---|
| Order under ~2^40 | Baby-step giant-step | sqrt(n) time and memory |
| Order large, memory tight | Pollard’s rho | sqrt(n) time, constant memory |
| Order factors into small primes | Pohlig-Hellman | Effectively instant |
| Order is a large prime | Index calculus, or give up | Not a CTF path |
Pohlig-Hellman is the one to check first, and the check is cheap: factor p-1. If every factor is small, solve the discrete log independently in each prime-order subgroup - each of those is tiny - and recombine with the Chinese remainder theorem. A 2048-bit prime with a smooth p-1 is broken in milliseconds, which is precisely why safe primes (where (p-1)/2 is also prime) are required in practice.