Discrete logs, Diffie-Hellman and elliptic curves
The other half of public-key crypto: weak groups, small subgroups, invalid curves, and the nonce that leaks a signing key.
By the end you can
- Choose between brute force, baby-step giant-step and Pohlig-Hellman from the factorisation of the group order
- Recognise a small-subgroup or invalid-curve parameter set before attempting anything
- Recover an ECDSA private key from two signatures sharing a nonce
- Recover a key from biased nonces using a lattice, and say how many signatures that needs
- Explain why a signature scheme fails catastrophically on nonce reuse while encryption merely leaks
1. Read
Discrete logs and the ways Diffie-Hellman is set up wrong
Baby-step giant-step, Pohlig-Hellman on a smooth group order, small-subgroup confinement, and the unauthenticated key exchange that is really a man in the middle. How to tell which discrete-log attack a challenge is asking for by looking at the parameters.
Elliptic curves in CTF: nonce reuse, biased nonces, and invalid curves
ECDSA leaks its private key when a nonce repeats, when a nonce is biased by a few bits, or when the curve you were handed is not the curve the implementation thinks it is. The four failure modes, what each looks like in a transcript, and how to run them.
2. Use the tools
In the order they come up while solving. Read what each one does, or go straight to the workspace tab that runs it.
- 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 it in the workspace - 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.
Open it in the workspace - Biased nonce lattice attack (hidden number problem)
Recover an ECDSA key from many signatures whose nonces leak only a few bits, by reducing the hidden number problem to a lattice with LLL.
Open it in the workspace - Knapsack / subset-sum solver (Merkle-Hellman break)
Find which weights sum to a target - greedily for a superincreasing sequence, with LLL for a low-density one, exhaustively for a small one.
Open it in the workspace - 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.
Open it in the workspace - ASN.1 and X.509 certificate parser
Decode DER and PEM structures, walk the ASN.1 tree, and read certificate fields, extensions, and embedded public keys.
Open it in the workspace
3. Try one now
Generated in your browser and checked in your browser. No account, nothing to download, and a fresh one whenever you want another.
4. Practise on the real thing
Real picoCTF challenges that use these techniques, easiest first.
Common mistakes
The wrong turns this topic reliably produces. Written as the mistake rather than the rule, because the rule is easy to agree with and easy to walk straight past.
- Reading a large prime as a hard problem. Pohlig-Hellman cares about the factorisation of p-1, not the size of p, and a smooth order is a solved log.
- Checking that a point is on the named curve and stopping there. An invalid-curve attack supplies a point from a different curve entirely, which is why the check has to be explicit.
- Treating a partially biased nonce as safe. A few leaked bits across a few dozen signatures is a lattice problem, not a brute force.
- Doing signature arithmetic modulo the field prime instead of the group order. Both numbers are in front of you, the wrong one produces a key that looks entirely plausible, and nothing fails until verification does.
- Assuming a named curve because the parameters look familiar. A challenge that hands you a, b and p has defined its own curve, and the group order every attack depends on has to be computed rather than looked up.
Checkpoint
Given two ECDSA signatures over different messages, detect the shared nonce, recover the private key, and verify it by signing a third message.
Teaching note
Students arrive believing elliptic curves are harder than RSA. They are not harder to attack in CTF: the bugs are in the parameters and the nonces, and both are visible. Show a nonce-reuse recovery in the first twenty minutes so the topic stops feeling gated behind the mathematics.
Go deeper
The lessons above are written to get you through a challenge. These are the chapters to read when you want the subject instead - each one named so you can check it rather than take our word for it. Nothing here is affiliate-linked or sold by us.
Designing Secure Software - Loren Kohnfelder
Chapter 5, Cryptography
Walks the Diffie-Hellman exchange step by step, which makes the small-subgroup attack obvious once you see which value is unchecked.
Black Hat Go - Tom Steele, Chris Patten, and Dan Kottmann
Chapter 11, Implementing and Attacking Cryptography
Signature verification in code, where the nonce is a variable you can watch being reused.