Elliptic Curves for CTF: The Discrete Log Is the Whole Game

Two signatures from a CTF. That's already one too many.

Here are two signatures from a challenge server. Same signer, same private key, two different messages. You don't have the private key. You're not supposed to be able to get it.

sig1:  r = 0x6c8f...a31b   s = 0x91d4...77e0
sig2:  r = 0x6c8f...a31b   s = 0x4a02...c9f5

Look at the r value on each line. Identical. In ECDSA (the Elliptic Curve Digital Signature Algorithm, the signature scheme behind Bitcoin, TLS certificates, and your phone's secure boot), a signature is the pair (r, s): the r comes from a random number chosen fresh for every signature, and the s mixes that random number with the message and the private key. The r is supposed to be different every time, with overwhelming probability. Seeing it twice is not a coincidence. It is the bug, and the bug is the whole challenge.

From those two signatures you can recover the signer's private key in four lines of arithmetic. You never define the curve. You never add two points. You never look at the Weierstrass equation that every textbook opens with. You subtract, you divide, and the secret falls out.

The first elliptic-curve challenge I ever opened, I spent an afternoon re-deriving the group addition law by hand, drawing the little chord-and-tangent pictures, before I noticed the server had handed me two signatures with the same r. I didn't need the geometry. I needed to notice. That is the entire lesson of this post.

Elliptic curve and discrete-log challenges look like the scariest crypto in the room. They are taught as a wall of abstract algebra: group law, point at infinity, projective coordinates, the discrete logarithm problem. The wall is real and it works. But almost every CTF break ignores the wall completely, because the break was never in the math. It was in one of two structural slips: the group wasn't actually hard, or the protocol leaked the secret directly. This post is a map of both, with a real picoCTF challenge to start on and the production disasters where the same two slips cost real money.

The discrete log in one minute, no group theory

Every system in this post leans on one hard problem, the discrete logarithm problem (DLP). It is easy to state. Take a group element G and multiply it by a secret integer d. Going forward is cheap:

forward:   given G and d,  compute  P = d * G       # easy
backward:  given G and P,  find     d  (P = d*G)    # hard

For elliptic curves, d * G means adding the point G to itself d times, which you do in about log(d) steps by doubling. Going backward, recovering d from the result, is the elliptic curve discrete logarithm problem (ECDLP), and on a well-chosen curve it is one of the hardest problems in applied cryptography. The entire security of the system is that one-way gap. Nothing else.

The same shape powers Diffie-Hellman (DH) key exchange, just in a different group. picoCTF 2026's Shared Secrets is the gentlest possible introduction. Two parties run DH over the integers mod a prime p, each picking a private exponent and publishing g^private mod p. An eavesdropper who wants the shared secret has to solve the discrete log: find the private exponent from the public key. That is the hard problem the challenge is built on.

Except the challenge doesn't make you solve it. One side leaked its private exponent. So you compute the shared secret with a single pow(A, b, p) and decrypt. The hard problem was never engaged, because someone left the secret lying on the floor. Hold that thought, because it is the whole pattern. The discrete log is the wall. The challenge is almost always a door someone left open next to it.

The discrete log is the part nobody breaks. The challenge is whoever set it up handing you a way around it.

So the reflex, every time you open one of these, is the same. Don't reach for the geometry. Read the parameters first. What is the group? What is its order? Were the random values actually random? Two of those questions break almost everything in this category, and they are the next two sections.

Pohlig-Hellman: when the order isn't actually hard

The hardness of the discrete log depends on the order of the group: how many elements it has before it wraps back to the start. The square-root attacks that set the difficulty cost about the square root of that order, so 256-bit security needs a group whose order is a 256-bit number with no exploitable structure. The cleanest way to lose that is to pick a group whose order factors into small primes.

That is the door Pohlig and Hellman walked through in 1978. Their paper ("An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance," IEEE Transactions on Information Theory) shows that if the group order is smooth, meaning it factors into only small primes, the discrete log shatters into one small discrete log per prime factor. You solve each tiny piece by brute force, then glue the answers back together with the CRT (Chinese Remainder Theorem, the tool that reconstructs a number from its remainders modulo coprime factors). The total cost collapses to roughly the square root of the largest prime factor, not the square root of the whole order.

Read that consequence carefully, because it is the entire attack. A 256-bit group order sounds like 2¹²⁸ work. But if that order happens to be a product of primes that all fit in 40 bits, the real cost is the square root of a 40-bit number, about 2²⁰, which is nothing. The group looks 256-bit strong and is actually trivial. The size was never the security. The factorization was.

So the diagnostic is one line. Before anything else, factor the order:

sage: E = EllipticCurve(GF(p), [a, b])
sage: n = E.order()
sage: factor(n)
# 2 * 3 * 5 * 7 * 11 * ... * (all small)  -> smooth -> Pohlig-Hellman wins
# 2 * (one enormous 250-bit prime)         -> safe   -> go find another bug

If the factorization is smooth, you don't even implement the attack by hand. SageMath's discrete-log routine runs Pohlig-Hellman for you:

sage: G = E(Gx, Gy)        # the base point
sage: P = E(Px, Py)        # the public point, P = d*G
sage: d = G.discrete_log(P)
sage: d                    # the private scalar, in seconds

The same fingerprint applies to the multiplicative group behind plain Diffie-Hellman, and it is exactly why safe primes exist. A prime p is safe when p - 1 = 2q for another large prime q, which forces the group order to have a giant prime factor and starves Pohlig-Hellman. If a challenge ships a DH prime where p - 1 factors into small pieces, the discrete log is recoverable even without any leak. The author who set Shared Secrets leaked a key so you wouldn't have to check; a meaner author would have shipped an unsafe prime and let Pohlig-Hellman do the work.

ECDSA nonce reuse: the two-time pad on a curve

This is the one to learn cold, because it is the highest-value bug in the category and because you already understand it. If you have read the stream cipher or AES posts, you have met its twin: reuse a one-time random value, and two observations are enough to recover the secret by linear algebra. On a stream cipher that random value is the keystream nonce, and reusing it gives you a two-time pad. In ECDSA it is the signing nonce k, and reusing it gives you the private key. Same bug. Different notation.

To sign a message hash z with private key d, ECDSA picks a random nonce k, computes the point k*G, takes its x-coordinate as r, and produces:

r = (k * G).x   mod n
s = k^-1 * (z + r*d)   mod n      # n is the group order
signature = (r, s)

The nonce k must be unique per signature and never revealed. RFC 6979 exists entirely because that requirement is so easy to get wrong; it specifies how to derive k deterministically from the key and message so a broken random number generator can't sink you. When two signatures share a nonce, they share an r (because r comes only from k*G), and that shared r is the visible tell in the ciphertext, the same way a repeated 16-byte block is the tell for ECB.

Now the algebra. Two signatures, same k, messages z1 and z2. Everything here is mod n, and dividing mod n just means multiplying by the modular inverse (the number that multiplies back to 1), so no fractions actually appear:

s1 = k^-1 (z1 + r*d)
s2 = k^-1 (z2 + r*d)
s1 - s2     = k^-1 (z1 - z2)        # subtract: the r*d term cancels
k (s1 - s2) = z1 - z2               # multiply both sides by k
  =>  k = (z1 - z2) / (s1 - s2)     mod n
 
now put k back into  s1 = k^-1 (z1 + r*d):
s1*k = z1 + r*d                     # multiply both sides by k
r*d  = s1*k - z1                    # subtract z1
  =>  d = (s1*k - z1) / r           mod n

Subtract the two signature equations and the secret r*d term cancels. That is the same cancellation you get when you XOR two ciphertexts encrypted under one nonce, just with subtraction instead of XOR:

two-time pad:  C1 XOR C2 = P1 XOR P2     # the keystream cancels
ECDSA reuse:   s1 - s2   = k^-1(z1 - z2) # the r*d secret cancels

One reused random value, two observations, and the thing you weren't supposed to know falls out by elementary algebra. Once you have k, you back out d. The whole recovery is a handful of modular inverses:

from Crypto.Util.number import inverse, long_to_bytes
 
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141  # secp256k1
r, s1, s2 = ...        # s1, s2 from the two signatures (same r)
z1, z2 = ...           # the two message hashes, reduced mod n
 
k = ((z1 - z2) * inverse((s1 - s2) % n, n)) % n   # inverse(x, n) is x^-1 mod n
d = ((s1 * k - z1) * inverse(r, n)) % n
print(hex(d))                  # d is a scalar (a number), not text
# if the flag is hidden in the key bytes: print(long_to_bytes(d))

That is the entire attack. No curve operations, no point arithmetic, no discrete log. You exploited a signature scheme built on the hardest problem in applied cryptography using nothing but subtraction and division mod n.

ECDSA nonce reuse is two-time-pad reuse with bigger numbers. Reuse the random value once, and two signatures hand you the private key.

And people ship it. In December 2010, the group fail0verflow stood on stage at the 27th Chaos Communication Congress (27C3) and explained that Sony had signed every piece of PlayStation 3 firmware with the same constant k. Not a weak random number generator. A constant. The same nonce on every signature, forever. That single slip let them recover Sony's private signing key, the master key that decided what code the console would run. It is the cryptographic equivalent of using one password everywhere and also having it tattooed on your forehead. The math protecting that key was flawless. Nobody had to touch it.

It happened again with real money attached. On August 11, 2013, bitcoin.org issued a security advisory: a flaw in Android's SecureRandom made it return repeating values, so Bitcoin wallet apps on affected phones signed different transactions with colliding nonces. Every collision leaked a private key the moment both signatures hit the public blockchain, where anyone could scrape them. Attackers did, and emptied the wallets. The chain is a permanent, worldwide log of (r, s) pairs; a single repeated r is a published private key.

Cursed curves: when the curve isn't really a curve

The last family is curves chosen so the discrete log is easy in the first place. A challenge author hands you a perfectly normal-looking y^2 = x^3 + a*x + b over some prime field, and the curve has a property that quietly demolishes the ECDLP. There are three you actually meet, and the move for all three is the same: don't eyeball the equation, plug the parameters into a checker.

Singular curves are the bluntest. If 4a^3 + 27b^2 = 0 mod p, the shape has a cusp or a self-intersection, and it is not an elliptic curve at all. Its smooth points are isomorphic to either the additive group of the field (a cusp, where "discrete log" is just division) or the multiplicative group (a node, where it's an ordinary finite-field discrete log, itself often smooth). One modular computation tells you which, and either way the secret scalar drops out. The single most useful line you can run on any EC challenge is checking whether the discriminant is zero.

Anomalous curves are subtler and nastier. When the number of points on the curve equals the field prime exactly, Nigel Smart showed in 1999 (building on independent work by Satoh-Araki and Semaev around 1997 to 1998) that you can lift the problem into the p-adic numbers and read the discrete log off a derivative, in polynomial time, regardless of how big the curve is. A 512-bit anomalous curve falls in seconds. The tell is purely arithmetic: E.order() == p. You will never see it by looking at a and b.

Supersingular curves and their low-embedding-degree relatives are the original elliptic-curve break. Menezes, Okamoto, and Vanstone (1993) used the Weil pairing to map the ECDLP into the multiplicative group of a small field extension F_(p^k), where the sub-exponential index-calculus attacks that don't work on curves suddenly do. The MOV attack (named for those three authors) is why nobody deploys supersingular curves for ordinary signatures. The embedding degree k is small, so the field you land in is reachable.

The diagnostic for the whole family is a short Sage ritual, run before you think about anything clever:

sage: disc = (4*a^3 + 27*b^2) % p
sage: disc == 0            # singular? -> map to additive/multiplicative group
sage: E = EllipticCurve(GF(p), [a, b])
sage: E.order() == p       # anomalous? -> Smart's attack, polynomial time
sage: factor(E.order())    # smooth?    -> Pohlig-Hellman
# embedding degree small?  -> MOV. (supersingular curves have k <= 6)

None of these is something you reason out from the curve equation. They are properties you test. The author picked a cursed curve hoping you'd be intimidated by the Weierstrass form and never run E.order(). Run it.

The cheat sheet

Every row starts with a parameter you measure, not a theorem you prove. Run the five checks top to bottom before you open a single point-arithmetic tutorial.

Where to start

Start with Shared Secrets if you have never touched this category. It is a discrete-log problem with the answer left in the open, which is the perfect place to feel how the hard problem and the leak relate without fighting any math. From there, the discrete-log family is where CTF crypto goes once you have cleared RSA and AES modes: harder events lean on it heavily, and picoCTF eases you in on purpose.

The honest thing to admit is that picoCTF barely scratches this family. Shared Secrets is the one clean anchor in the set, and it doesn't even make you solve a discrete log. That's fine. The reason to learn the family now is that the moment you step up to a harder CTF, every one of these five checks earns its keep, and they protect the things that matter: the signatures your phone makes, the keys that move Bitcoin, the certificates behind TLS.

For the rest of the crypto map: the RSA Attacks post covers the other half of public-key crypto. The stream cipher and AES posts develop the nonce-reuse bug that turns out to be the exact same move as ECDSA nonce reuse, one field over. When a challenge turns out to be a hash in disguise, the hash cracking post takes it from there.

Open the challenge. Read the parameters before the equation. Factor the order, check the discriminant, count the points, compare the nonces. The discrete log is the whole game, and almost every time, somebody already lost it for you.