ECDSA nonce reuse across multiple private keys (9 signatures / 7 keys / 3 nonces

[punchkun99]

Hello,

I would like to present an interesting ECDSA signature scenario involving what appears to be nonce reuse across different private keys.

Problem setup

Private keys:
d1, d2, d3, d4, d5, d6, d7

Nonces:
k1, k2, k3

Total: 9 signatures

Signature structure
   •   d1 signs three times, using the nonces k1, k2, k3 (or possibly their opposites -k1, -k2, -k3).
   •   Nonce k1 (or -k1) is used by: d1, d2, d3
   •   Nonce k2 (or -k2) is used by: d1, d4, d5
   •   Nonce k3 (or -k3) is used by: d1, d6, d7

So we clearly have nonce reuse between different private keys, with d1 acting as a pivot, since it signs once with each of the three nonces.

It also appears that RFC 6979 was not used, otherwise each signature would have a deterministic unique nonce.

ECDSA equation

s = k⁻¹ (z + r·d) mod n

which can be rewritten as:

k·s = z + r·d (mod n)

In this setup we therefore have:

9 equations for 10 unknowns

Unknowns:

Private keys:
d1, d2, d3, d4, d5, d6, d7

Nonces:
k1, k2, k3

Question

Even though the system appears underdetermined (9 equations for 10 unknowns), the particular structure — with nonce reuse across multiple keys and d1 acting as a pivot connecting the three groups — might allow some reduction of the system.

Is there any known method to solve this kind of system?

Thanks in advance for any insights.

[0bs3ssed]

Very interesting and yes retrievable.
Have you tried further reducing the unknowns down to 1 ?
Got a nice in-depth system I built which finish this extremely quickly if you would like any help... Just pop me a PM

Have also tried popping a DM but because I'm new I can't.

[BattleDog]

What you have there is basically a one-parameter family, not a uniquely solvable recovery. If you take d1 as the pivot, then its three signatures let you write k1, k2 and k3 as functions of d1, and once those are pinned in that form, every other di also collapses into a function of d1.

So yes, the algebra can be reduced hard, but that is not the same thing as saying that all keys are now recoverable. It just means the whole system folds down to one free variable unless you bring in one more independent constraint from somewhere else.

[vdog99]

Seems like this is instead of Nonce Re-Occurrence this is sk recurrence problem. Does this happen in real world would be unlikely but maybe a good math exercise.

If you can rewrite the sk maybe to multivariate polynomial equation, it could be solvable

Use this Paper for your analysis although it is for nonce recurrence https://eprint.iacr.org/2023/305.pdf

[punchkun99]

Thanks for your responses.

Analyzing other keys from the same environment, I noticed that many private keys share common factors. For example, some pairs have GCDs like 63, 225, etc. It is therefore possible that the keys in the d1–d7 set also have nontrivial GCDs between them.

Since the system admits a family of solutions, I was able to generate valid signatures for different solutions of the equation. Some of these valid signatures have relatively small S values.

Could the potential GCDs between private keys or the observation of small S values in these valid signatures provide an exploitable constraint to help reduce the solution space?