🛡️ ECDSA Nonce Reuse Attack

This repository implements a Python function recover_private_key that recovers the private key from two different signatures that use the same random nonce $k$ during signature generation. Note that if the same $k$ is used in two signatures, this implies that the secp256k1 32-byte signature parameter $r$ is identical. This property is asserted in this function.

🧠 Mathematical Derivation

First, note that the integer order $n$ of $G$ (a base point of prime order on the curve) for the secp256k1 elliptic curve is:

# Represented as hex value.
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd036414
# Represented as integer value.
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337

1. Public-Private-Key-Relationship

$$ Q_{A} = d_{A} \cdot G $$

$Q_{A}$ is the public key, $d_{A}$ is the private key, and $G$ is the elliptic curve base point.

2. The secp256k1 32-Byte Signature Parameter $r$

$$ r = G \cdot k \quad \left(\textnormal{mod} \enspace n\right) $$

$r$ is the first secp256k1 32-byte signature parameter, $n$ is the integer order of $G$, and $k$ is the random nonce value.

3. The secp256k1 32-Byte Signature Parameter $s$

$$ s = \frac{h + d_{A} \cdot r}{k} \quad \left(\textnormal{mod} \enspace n\right) $$

$s$ is the second secp256k1 32-byte signature parameter and $h$ is the 32-byte message digest of a message.

4. Recover the Private Key

Let's assume that $d_{A}$ has used the same random value $k$ for two different signatures. This implies from the above definition of $r$ that $r$ is the same for both signatures, since $G$ and $n$ are constants. Thus, we have:

$$ s_{1} = \frac{h_{1} + d_{A} \cdot r}{k} \quad \left(\textnormal{mod} \enspace n\right) $$

and

$$ s_{2} = \frac{h_{2} + d_{A} \cdot r}{k} \quad \left(\textnormal{mod} \enspace n\right). $$

We can solve for $k$ with the above system of equations:

$$ s_{1} - s_{2} = \frac{h_{1} + d_{A} \cdot r}{k} - \frac{h_{2} + d_{A} \cdot r}{k} \quad \left(\textnormal{mod} \enspace n\right), $$

$$ s_{1} - s_{2} = \frac{h_{1} + d_{A} \cdot r - h_{2} - d_{A} \cdot r}{k}\quad \left(\textnormal{mod} \enspace n\right), $$

$$ s_{1} - s_{2} = \frac{h_{1} - h_{2}}{k}\quad \left(\textnormal{mod} \enspace n\right), $$

$$ k = \frac{h_{1} - h_{2}}{s_{1} - s_{2}}\quad \left(\textnormal{mod} \enspace n\right). $$

Eventually, we can now plug $k$ into the equation $s_{1}$ and recover the private key $d_{A}$:

$$ s_{1} = \frac{h_{1} + d_{A} \cdot r}{\frac{h_{1} - h_{2}}{s_{1} - s_{2}}} \quad \left(\textnormal{mod} \enspace n\right), $$

$$ s_{1} = \frac{\left(s_{1} - s_{2}\right)\cdot\left(h_{1} + d_{A} \cdot r\right)}{h_{1} - h_{2}} \quad \left(\textnormal{mod} \enspace n\right), $$

$$ d_{A} = \frac{(s_{2} \cdot h_{1} - s_{1} \cdot h_{2})}{r \cdot (s_{1} - s_{2})} \quad \left(\textnormal{mod} \enspace n\right). $$

The function recover_private_key uses the last equation in conjunction with modular arithmetic properties to recover the private key.

📚 Further References

• Elliptic Curve Digital Signature Algorithm
• RFC 6979
• A Glimpse of the Deep: Finding a Creature in Ethereum's Dark Forest
• How Hackers Can Exploit Weak ECDSA Signatures
• ECDSA Nonce Reuse Exploit Example
• Identifying Key Leakage of Bitcoin Users
• How Do You Derive the Private Key From Two Signatures That Share the Same k Value?