two signatures, one nonce: recovering an ECDSA key

The flag-signing service will sign any message you send and hand back (r, s). It signs two of them before it rotates the nonce. Find the key.

ECDSA is unforgiving about one thing above all others: the per-signature nonce $k$ must be secret and never repeated. Repeat it once and the private key falls out with grade-school algebra.

the signing relation#

For a curve of order $n$ , private key $d$ , message hash $z$ and nonce $k$ , a signature is the pair $(r, s)$ with $r = (k G)_{x} mod n$ and

s \equiv k^{- 1} (z + r d) (\mod n) .

Everything here is mod $n$ , the group order — not the field prime. Mixing the two moduli is the most common way to spend an afternoon debugging a correct attack.

symbol	meaning	known to me?
$n$	order of the base point $G$	yes (public)
$d$	private key	target
$k$	per-signature nonce	secret
$z$	$H (m)$ truncated to bits	yes
$r, s$	the signature	yes

reuse collapses it#

Two signatures $(r, s_{1})$ and $(r, s_{2})$ on hashes $z_{1} \neq z_{2}$ share the same $r$ — which is the tell, since $r$ depends only on $k$ . Equal $r$ means equal $k$ . Subtract the two signing relations and $d$ drops out:

s_{1} - s_{2} \equiv k^{- 1} (z_{1} - z_{2}) (\mod n) .

Solve for the nonce directly,

k \equiv (z_{1} - z_{2}) (s_{1} - s_{2})^{- 1} (\mod n),

and back-substitute into either signature to recover the key:

d \equiv r^{- 1} (s_{1} k - z_{1}) (\mod n) \equiv \frac{s_{2} z_{1} - s_{1} z_{2}}{r (s_{1} - s_{2})} (\mod n) .

That last form is the one to memorise — given $r$ , two $s$ values and two hashes, it's a single modular division.

recover.pypython

from hashlib import sha256
n  = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551  # secp256r1

def H(m):  # truncated hash -> integer mod n
    return int.from_bytes(sha256(m).digest(), "big") % n

z1, z2 = H(b"transfer 1 coin"), H(b"transfer 9999 coins")
r, s1, s2 = sig1[0], sig1[1], sig2[1]

k = (z1 - z2) * pow(s1 - s2, -1, n) % n
d = (s1 * k - z1) * pow(r, -1, n) % n
print("d =", hex(d))

spotting it in the wild

You don't need the source to know a nonce repeated — you need two signatures with an identical $r$ . Collect a handful, sort by $r$ , look for a collision. The same trick works across different keys if a bad RNG seeds them in lockstep.

when the nonce is only biased#

Real leaks are rarely a clean repeat. More often $k$ is short — the top bits are zero — and one signature tells you nothing, but a few hundred do. This is the Hidden Number Problem: each signature is a noisy linear equation in $d$ ,

d \cdot t_{i} - u_{i} \equiv k_{i} (\mod n), t_{i} = r_{i} s_{i}^{- 1}, u_{i} = z_{i} s_{i}^{- 1},

where every $k_{i}$ is small. Stack the equations as a lattice whose short vectors encode the answer:

B = [\begin{matrix} n & 0 & \dots & 0 \\ 0 & n & \dots & 0 \\ ⋮ & ⋱ & ⋮ \\ t_{1} & t_{2} & \dots & 1 \end{matrix}]

Run LLL (or BKZ for tight bias), and the row closest to the origin spells out the $k_{i}$ — and with them, $d$ . Two-thirds of a leaked nonce over ~80 signatures is plenty.¹

the flag

Once you have d, sign the challenge token yourself: segfault{n0nce_r3us3_1s_a_pr1v4te_k3y_l3ak}

The bridge from "biased nonce" to "lattice" is the part worth internalising: a bound on the unknown becomes a short vector, and short vectors are what LLL finds. Most ECDSA CTF crypto is some disguise over this one reduction. ↩