Discrete logs, Diffie-Hellman and elliptic curves

Before the session

• Nothing to install. Students need a browser and https://ctfpal.com. Confirm the room can reach it once; after that it works offline.
• Read the lesson yourself first - about 15 minutes.
• Have one worked example ready to paste. The classroom link builder on the instructor page turns it into a URL that opens preloaded.

Objectives

Written as things a student can do afterwards, so they can be assessed rather than asserted.

1. Choose between brute force, baby-step giant-step and Pohlig-Hellman from the factorisation of the group order
2. Recognise a small-subgroup or invalid-curve parameter set before attempting anything
3. Recover an ECDSA private key from two signatures sharing a nonce
4. Recover a key from biased nonces using a lattice, and say how many signatures that needs
5. Explain why a signature scheme fails catastrophically on nonce reuse while encryption merely leaks

Running order (120 min)

Tools used

• 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.https://ctfpal.com/?tool=discrete-log-solver
• 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.https://ctfpal.com/?tool=ecdsa-nonce-reuse
• 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.https://ctfpal.com/?tool=biased-nonce-lattice-attack
• 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.https://ctfpal.com/?tool=knapsack-subset-sum
• 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.https://ctfpal.com/?tool=modular-arithmetic-toolkit
• 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.https://ctfpal.com/?tool=asn1-x509-parser

Reading

• Discrete logs and the ways Diffie-Hellman is set up wrong - 7 min. 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 - 8 min. 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.

Practice set

Real picoCTF challenges tagged with this module’s techniques, easiest first. Assign the first three in class and the rest as homework.

1. Shared Secrets - picoCTF 2026, easy
2. basic-mod1 - picoCTF 2022, medium
3. basic-mod2 - picoCTF 2022, medium
4. Not TRUe - picoCTF 2026, medium
5. ReadMyCert - picoCTF 2023, medium
6. MSS_ADVANCE Revenge - picoCTF 2026, hard

Checkpoint (gradeable)

Given two ECDSA signatures over different messages, detect the shared nonce, recover the private key, and verify it by signing a third message.

Deliberately a produced artefact rather than a quiz question: it is either there or it is not, which makes it fast to mark and hard to bluff. Every tool in ctfpal is deterministic, so two students who did the work correctly hand in the same value.

Where the room gets stuck

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.

• 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.

If a student wants the subject, not the answer

Chapter-level references, so a student can be pointed at twenty pages rather than at a book. Nothing here is required to complete the module.

• 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.

If you finish early

• Hand out a challenge from the cross-CTF index in this category - each one has published solutions to compare afterwards.
• Run the same input through Identify and let the class argue with the ranking. Disagreeing with a confidence score is where the technique actually lands.
• Ask a student to break their own example - construct an input that defeats the tool, and explain why.