Cryptanalysis reference
Notes on the attacks that public-key parameters are sized against. Each page says what the attack needs, what it costs, what the largest computation on record used, and when the attack stops applying. Every page cites the original papers, and those are the thing to read if you need precision.
How the pages are organised
Most published attacks don't break deployed systems. They improve an exponent, or need a structural coincidence that sensible parameters avoid, or assume an oracle nobody has. So the question each page tries to answer is what the attack would cost against a particular set of parameters, and what would have to change for that cost to become affordable.
Each page covers, in order:
- The problem instance: what the attacker is given and what counts as success.
- The mechanism: the idea that makes the attack cheaper than brute force. It is usually a collision, a relation, or a map to an easier object.
- The cost: the asymptotic bound, and what the largest published computation actually used.
- The boundary: the hypothesis the attack depends on, and so the parameter choice that makes it irrelevant.
Generic group algorithms
These work in any cyclic group where you can compute the group operation and test equality. Shoup's lower bound says no generic algorithm can use fewer than about √p operations, where p is the largest prime dividing the group order, so these algorithms set the baseline every discrete-log parameter is measured against.
-
Pollard's rho
The square-root generic attack that every elliptic-curve key size is calibrated against.
-
Pohlig–Hellman
A discrete logarithm is only as hard as the largest prime factor of the group order — which makes group-order validation a security control, not a formality.
-
BSGS and kangaroos
Deterministic √n time-memory tradeoffs, and Pollard's lambda method for logarithms known to lie in a short interval.
Index calculus and descent
Index calculus collects relations over a factor base and solves a linear system. It is the reason discrete logarithms in finite fields take subexponential time. Whether anything like it works on elliptic curves has been an open question since Semaev's 2004 paper.
-
Summation polynomials
Semaev's construction turns point decomposition into polynomial system solving — and delivers a genuine speedup over extension fields while leaving prime-field curves untouched.
-
Weil descent (GHS)
Transport an elliptic curve over F2m to a higher-genus curve over a subfield, where index calculus already works.
-
The number field sieve
The L(1/3) algorithm behind every factoring and prime-field discrete-log record — and the reason RSA and finite-field Diffie–Hellman need 3072-bit parameters to match a 256-bit curve.
-
Gröbner bases
How F4/F5 behaves on the polynomial systems that index calculus generates, and why the measured degree of regularity decides feasibility.
Lattice attacks
When a secret is partly known, from a few leaked bits, a biased nonce, or a small root of a modular equation, lattice reduction can often recover the rest. Many breaks of deployed ECDSA and RSA implementations come from this family rather than from any weakness in the underlying problem.
-
Hidden number problem
A few bits of nonce bias per signature, collected over a few hundred signatures, recovers the private key outright — regardless of curve size.
-
Coppersmith's method
Finding small roots of modular polynomials, and the partial-key-exposure and small-exponent attacks on RSA that follow from it.
Isogeny attacks
Isogeny problems are the newest of these assumptions. SIKE was broken outright in 2022, after it had reached the fourth round of NIST's standardisation process, which is a good reason to read the attacks on its successors closely.
-
SIDH torsion attacks
Kani's criterion turned the auxiliary torsion images published by SIDH into a polynomial-time key recovery — breaking SIKE during NIST standardisation.
-
Kuperberg and CSIDH
Commutativity buys CSIDH its small keys and non-interactive key exchange, and costs it a subexponential quantum attack — whose concrete cost is still disputed.
-
Supersingular path problem
Delfs–Galbraith, Wesolowski's 2026 p1/3 algorithm, and what its memory cost means for SQIsign parameters.