Hey everyone,
ECDSA remains widely implemented across asymmetric cryptosystems, but its existential dependency is an unpredictable, uniform ephemeral scalar: the nonce k must never repeat or exhibit bias under the same private key.
When an implementation relies on a broken pseudo-random number generator (such as flaws in random seed generation or low-entropy PRNGs), two signatures generated with an identical nonce allow algebraic recovery of the signer's private key via basic modular arithmetic.
I developed an open-source research tool called RSZ-Scanner to parse signature tuples (r, s), extract message digests (z), and identify nonce collisions across signature sets. Here is a brief mathematical overview of the recovery pipeline.
**Mathematical Model**
In standard ECDSA over secp256k1, a signature is the pair (r, s):
r = (k \* G)_x mod n
s = k\^(-1) \* (z + r \* d) mod n
Where:
\- G is the generator point of the elliptic curve group.
\- n is the group order.
\- d is the private scalar (secret key).
\- z is the cryptographic message hash truncated to group order length.
\- k is the ephemeral random scalar in \[1, n - 1\].
**Explicit Recovery on Identical Nonces (k1 = k2)**
If a public key signs two distinct message digests z1 and z2 using the exact same nonce k, both signatures share the identical r parameter:
s1 = k\^(-1) \* (z1 + r \* d) mod n
s2 = k\^(-1) \* (z2 + r \* d) mod n
Subtracting the equations eliminates the secret key d:
s1 - s2 = k\^(-1) \* (z1 - z2) mod n
Solving directly for the ephemeral secret k:
k = (z1 - z2) / (s1 - s2) mod n
Once k is known, the private key d is recovered via direct substitution:
d = (s1 \* k - z1) / r mod n
**Implementation Details: RSZ-Scanner**
RSZ-Scanner was written to demonstrate and evaluate this phenomenon against arbitrary signature dumps:
- Tuple Extraction: Parses signature structures to extract raw (r, s, z) components.
- Collision Detection: Maps and indexes unique r values against corresponding public keys to detect duplicate nonces across large datasets.
- Modular Solver & Verification: Runs the inverse arithmetic above and validates the derived private scalar against the associated EC public point.
Discrete Log Search: Includes an implementation of the Baby-Step Giant-Step (BSGS) algorithm to handle bounded partial nonce leakage and small nonce offsets.
**Repository & Discussion**
The implementation is open-source under the MIT license:
https://github.com/harshjamdar/RSZ-Scanner
I would appreciate feedback on:
\- Numerical optimizations for modular inverse computations when processing large batch sizes.
\- Extending BSGS search ranges or evaluating lattice-based attacks (Hidden Number Problem / Bleichenbacher-style lattices) for biased nonces.
\- Verifying edge-case handling around high-s malleable signatures.
Feedback, theoretical critiques, and contributions are welcome!