This repository implements a Python function that recovers the private key from two different signatures that use the same random nonce during signature generation.
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.
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
$$ 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.
$$ 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.
$$ 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.
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.
k
Value?