Solving Linear Dependencies in ECDSA Nonce Reuse Cases

Hey all, Just reposting my issue with some updates, but I'm still at a standstill. Anyone got ideas or solutions? So here’s the deal: We’ve got 9 signatures and 7 private keys: d1, d2, d3, d4, d5, d6, d7, along with 3 nonces: k1, k2, k3. d1 uses the nonces k1, k2, k3 (or their negatives: -k1, -k2, -k3). d2 and d3 are reusing k1 (or -k1). d4 and d5 reuse k2 (or -k2). d6 and d7 reuse k3 (or -k3). The signs are currently not an issue, since if we remove the nonces from the equations, we can find relationships between the keys and check them through scalar multiplication by n. When a public key doesn’t match, we just flip S and the correct public key pops up. We get relationships that look like this: Nonce setup The nonces can actually be expressed as affine functions of d1, with U1 and U2 as coefficients (where U1 = γ and U2 = δ): At this point, it all boils down to a single free variable: d1. The system is underdetermined, and there’s an extra constraint needed to really close it up. I realize that if d2 had used k1 and k2 with two independent relationships like this: (with different coefficients), then the whole thing would become solvable. Now, here’s the problem: In this arrangement, for any key from d1 to d7, using the relationship: and the U1, U2 coordinates from a signature, I can create a new signature for d2 with k2 (thus the same R value). The problem is that this creates a signature that looks valid, but k2 still relies on d1, leading to a logical loop like: So, does anyone have suggestions on how to disrupt this linear structure or add a constraint to wrap up the system?

With ECDSA, the basic equation is still s*k = z + r*d mod n. When the same nonce is reused, you can eliminate the nonce and get a relation between private keys. That part is fine. But if all you ever get are relations like "this key is an affine function of d1", then you have not recovered the keys, you have just chosen d1 as the free variable for the whole family of possible solutions. No, not from the data as you've described it. You can express everything relative to d1, but unless something pins d1 down, the system will stay open.

There is an industrial way to run the lattice attack at scale and it's https://github.com/bitlogik/lattice-attack . It requires that you know at least 4 bits of each nonce, with MSB and LSB being preferred as it simplifies things. You also need at least 88 signatures. If you have more bits, you'll need less. There are several solvers with increasingly long runtime and more accurate results, such as LLL, BKZ-15 BKZ-25, BKZ-35, etc You must understand however, that even with a large signature set, finding a solution is not guaranteed. Because increasing the number of dimensions in the lattice via adding more signatures merely makes the problem space bigger, and it is possible that the algorithm fails to find a solution, similar to a given linear algebra system.