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.
Related tools
Modular arithmetic and number theory toolkit
Modular inverse, Chinese remainder theorem, Tonelli-Shanks square roots, Jacobi symbols, and integer nth roots - arbitrary precision, in the browser.
ECDSA nonce reuse private key recovery
Recover an ECDSA private key from two signatures that reused the same nonce - the flaw that broke the PlayStation 3 and countless wallets.
RSA decryption and attack runner
Paste n, e, and c and let ctfpal choose the attack: trial division, Fermat, Pollard’s rho, Wiener, common modulus, or Hastad broadcast. Arbitrary-precision, in-browser.
Fermat factorization for close RSA primes
Factor an RSA modulus whose primes were generated too close together. Fermat’s method finds them in a handful of steps where trial division never would.