Repeated / Linearly-Related Nonce Recovery — when nonces aren't reused, but ARE related by a known formula

Generalizes exact nonce reuse: whenever nonces across two or more (EC)DSA signatures satisfy a KNOWN linear (or low-degree polynomial) relation instead of exact equality — a counter, an LCG, k = f(public data) — the signing equations still collapse to a small, solvable algebraic system in the private key and the nonces, no lattice required.

The signal that betrays it

This sits between two other DSA/ECDSA breaks, and the triage is the whole game: - Not ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra — the r values across the suspicious signatures are *different*, not identical, so a naive "group by r" scan finds nothing. - Not DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery — you're not looking at a vague *bound* on k (a few known/shared bits); you have (or can conjecture) an *exact formula* relating one nonce to another.

Concrete tells, from field use: - A counter-style nonce generator in source or behavior: k_{i+1} = k_i + c for some constant stride c, whether or not c is disclosed — a fixed stride is itself the relation. - A leaked or recoverable PRNG seed. If the nonce generator is a seeded PRNG (classic LCG, or anything whose internal state you can reconstruct — see PRNG State Prediction — recovering the internal state of a non-cryptographic generator), every k_i becomes an explicit function of the seed and the call index, which *is* a known relation once you've pinned the seed down. - r values that repeat after a fixed period, or drift in a way that isn't random — a giveaway that the "random" nonce source is actually periodic (a short-period LCG, a cycling PRNG) or otherwise low-entropy. Recognizing the period itself hands you a relation: k_i = k_{i+period}. - A batch of many signatures over different messages from the same key, rather than just a suspicious pair — enough samples to test a low-degree polynomial recurrence hypothesis (the Polynonce shape below) even without knowing the exact coefficients in advance.

How to exploit it

Case 1 — the relation's coefficients are fully known. For k2 = a*k1 + b with a, b known (the trivial sub-case a=1, b=0 is exact reuse, ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra), the two signing equations s1*k1 = h1 + d*r1 and s2*(a*k1+b) = h2 + d*r2 (mod n) are two linear equations in two unknowns (k1, d) — solve directly, no lattice, no search:

``python def related_nonce(r1, s1, h1, r2, s2, h2, a, b, n): # s1*k1 - d*r1 = h1 ; s2*a*k1 - d*r2 = h2 - s2*b A = [[s1 % n, (-r1) % n], [(s2*a) % n, (-r2) % n]] B = [h1 % n, (h2 - s2*b) % n] det = (A[0][0]*A[1][1] - A[0][1]*A[1][0]) % n di = pow(det, -1, n) k1 = ((B[0]*A[1][1] - A[0][1]*B[1]) * di) % n d = ((A[0][0]*B[1] - B[0]*A[1][0]) * di) % n return k1, d ``

This closed-form-from-just-two-signatures result (even when both signatures are over the *same* message) is exactly the public result in "Breaking ECDSA with Two Affinely Related Nonces" (2025): pure modular arithmetic, no lattice reduction, no brute force, as long as a, b are known.

**Case 2 — only the *shape* of the relation is known, not the coefficients. If nonces are conjectured to follow a polynomial recurrence of some degree `D` (linear, quadratic, ...) but you don't know its coefficients, you can't plug them into Case 1 directly. Instead, treat the coefficients as extra unknowns and eliminate them algebraically across enough signatures — via resultants or a Gröbner basis — leaving a single polynomial whose roots include the private key `d`. This is the public "Polynonce" technique: field-tested rule of thumb (and matching the published requirement) is N ≥ D + 3 signatures** — 4 signatures for a linear (degree-1) relation, 5 for quadratic, and so on. More signatures than the minimum make elimination more robust; fewer leave the system underdetermined and elimination produces no usable root.

Case 3 — nonces come from an LCG or similar PRNG. Don't try to guess a, b blind. First recover the generator's internal parameters/state (modulus, multiplier, increment, or just the running state) — see PRNG State Prediction — recovering the internal state of a non-cryptographic generator — from the observed k values or from a side channel, *then* substitute the now-known relation into Case 1 (if it reduces to a simple affine step-to-step relation) or Case 2 (if you only have the degree/shape and must still eliminate coefficients).

Always verify the recovered `d` against the public key (d*G == Q for ECDSA, g^d mod p == y for DSA) before trusting it in any of the three cases — a wrong guess at a, b, or the relation's degree still produces *a* number out of the linear algebra or the root-finding step; only pubkey verification catches that it's garbage.

What does NOT work

- Treating this as exact reuse when `r` values differ. If r1 ≠ r2, don't reach for the simple subtract-and-divide trick from ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra — that only cancels d when k1 = k2 exactly. A genuine affine relation needs the full two-unknown system above; skipping straight to the reuse formula on non-matching r just produces a d that fails verification. - Guessing the wrong polynomial degree `D`. Too low a guessed degree under-models the real recurrence and the elimination step yields no consistent root across all sample pairs; too high wastes signatures and can produce spurious extra roots that pass root-finding but fail pubkey verification. Iterate D upward from 1, always with N ≥ D + 3 signatures for that degree, and verify every candidate. - Reaching for lattice reduction / Hidden Number Problem machinery when the relation is exact and known (or discoverable). That's solving a *harder* problem than the one you have — DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery is for a *bound* on k (partial bit knowledge), not an exact formula between nonces. If you can pin down a/b/the LCG state, the direct algebraic solve is faster and exact. - Assuming LCG-derived nonces are directly pluggable as a generic affine relation without recovering the generator first. Unless the LCG's modulus/multiplier/increment are public, blind-guessing (a, b) mod n is intractable — the search space is the same size as the private key itself. Recover the LCG's actual parameters/state first (PRNG State Prediction — recovering the internal state of a non-cryptographic generator), then substitute; don't skip straight to Case 1 with made-up coefficients. - Unconstrained brute force over `(a, b)`. Brute-forcing the relation's coefficients only works when prior knowledge narrows the search space hard — e.g., a counter stride you can bound to a small guessed range from context (a loop counter, a millisecond timestamp delta). A full search over a, b ∈ [0, n) is exactly as infeasible as brute-forcing the private key. - Trusting the algebra without checking it against the public key. As in the exact-reuse case, a truncation bug in h, a mislabeled signature pair, or a wrong sign/coefficient guess all produce *a* number that looks like a private key but isn't — verify before reporting anything recovered.

Related

ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra — the trivial case of this technique (a=1, b=0, i.e. exact reuse); use its cheap closed form first before reaching for the general two-unknown system here. DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery — the sibling technique for when nonces are only *bounded*/biased rather than exactly related by a known formula; needs lattice machinery this technique doesn't. Deterministic Nonce (RFC 6979) Failures — when 'no more RNG risk' still leaks the key — a common root cause that produces exactly-related or exactly-reused nonces (a broken RFC 6979 implementation, a counter standing in for real randomness). PRNG State Prediction — recovering the internal state of a non-cryptographic generator — how to recover the internal state of an LCG or similar PRNG feeding the nonce, the prerequisite for Case 3 above. Hidden Number Problem — recovering a secret from many small-bounded-error samples and Lattice Fundamentals — encoding a bounded unknown as a short vector — the machinery this technique deliberately avoids when the relation is exact rather than a bound. ECDSA Fundamentals — the s*k = h + d*r identity that routes every nonce attack and DSA Fundamentals — the linear signing equation every DSA attack exploits — the s*k = h + d*r identity every case above solves. Cryptanalysis Methodology — classify the family before you reach for an attack — where signature-nonce triage fits in the overall challenge-classification routine.