Recovering private key from Secp256k1 signatures

Question

I've seen many answers here and many articles that says we can recover the private key from reused R signatures. But, what if the r,s signatures are different in transaction of bitcoin then is there a way we could find the ephemeral Key k used in both the cases and find the private key?

Answer 1

In ECDSA, each signature has its own ephemeral key $k$. If $k$ is generated properly, then no amount of signatures will help you recover the private key. "Proper" generation here means either random uniform selection in the proper range, or an appropriate derandomization process such as the one described in RFC 6979.

If the very same $k$ value is used in two signatures, on two distinct messages, but with the same private key $x$, then the private key is revealed. This is the deadly mistake of Sony back in early 2011 (and the initial motivation for RFC 6979, btw). Indeed, if the two messages are $m_1$ and $m_2$, and both values use the same $k$ values, then the two signatures are $(r,s_1)$ and $(r,s_2)$: \begin{eqnarray} s_1 &=& (h(m_1) + xr) / k \\ s_2 &=& (h(m_2) + xr) / k \\ \end{eqnarray} The ephemeral key $k$, and the private key $x$, can then be computed as: \begin{eqnarray} k &=& \frac{h(m_1) - h(m_2)}{s_1 - s_2} \\ x &=& \frac{ks_1 - h(m_1)}{r} \\ \end{eqnarray}

If the values of $k$ are not reused, but are generated with some bias (i.e. not all values in the $[1,q-1]$ range are selected with the same probability), then the private key $x$ can still be recovered from a set of signatures. If for instance $q$ has size 256 bits, but values of $k$ are always lower than $2^{253}$ (i.e. the top three bits are always zero), then a few hundreds of signatures suffice.

If the values of $k$ are generated with a strong, cryptographically secure source, and with no bias, then there is no known attack against ECDSA that would recover the private key $x$, even if many signatures are known. The first reuse of $k$ out of pure back luck is expected to happen after an average of $2^{n/2}$ signatures for an $n$-bit curve, i.e. never in practice if you use a decent curve.

Also, in Bitcoin, people tend not to sign a lot with any given key. For privacy reason, address reuse is discouraged.

Answer 2

So, let me recall a few details about ECDSA:

An ECDSA signature is a pair of integers $(r,s)$.

In order to generate a signature for a given message $m$, a given hash function $H$, curve parameters $(\mathcal{C}, G, n)$ for $\mathcal{C}$ a curve, $G$ a base point of prime order $n$ of $\mathcal{C}$, a private key integer $d$ and a public key point $Q = d\times G$, one can:

1. Compute $e = H(m)$, where $H$ is a cryptographic hash function and let $z$ be the integer representing the leftmost bits of $e$, when $e$ is truncated to the bit length of the group order.
2. Pick uniformly at random a value $k$ where $0 < k < n-1$ ;
3. Compute the point $(x, y) = k G$ ;
4. Compute $r = x\,\bmod\,n$. If $r = 0$, go back to 2 ;
5. Compute $s = k^{-1}(z + r d_A)\,\bmod\,n$. If $s = 0$, go back to step 2.

Then, when one has signed the message $m$, one can transmit the tuple $(m, r,s)$ and anybody can verify the signature $(r, s)$ by performing the following steps:

1. Compute $e = H(m)$ and let $z$ be like in the signature process ;
2. Compute $w = s^{-1}\,\bmod\,n$ ;
3. Compute $u_1 = zw\,\bmod\,n$ and $u_2 = rw\,\bmod\,n$ ;
4. Compute the point $(x, y) = u_1 G + u_2 Q$.

If $r \equiv x \mod n$, then the signature is valid, otherwise it is invalid.

Note that ECDSA crucially relies on the uniqueness (just like in the PS3 fail), but also on the entropy used in the choice of $k$, since a bias there can also lead to private key recovery by an attacker having only public signatures at her disposal, see for example this paper [1].

Now, what happens actually when you have re-used twice the same $k$ value?

Let's assume you obtained two signatures for two distinct messages $m_1$ and $m_2$, then you have the two signatures $(r_1,s_1)$ and $(r_2,s_2)$ and the $s$-values are computed as in step 5 above. This means that you can easily recover the value of $k$ by computing:

$$ k = (z_1 - z_2)(s_1-s_2)^{-1} \bmod{n} $$ where we are working with the inverse modulo the order of our curve. From $k$, it is easy also to compute the value of the secret integer $d$, with the help of any of the two signatures: $$ d= (ks-z)r^{-1} \bmod{n} $$ Once this has been done, you can easily check you have recovered the private key by comparing the public key with the value of $d\times G$, since if you have the correct $d$, both will be the same.

Finally, notice that this is true for any instance of ECDSA, not only using Secp256k1.

References

[1] De Mulder, Elke, et al. "Using Bleichenbacher's solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA." International Workshop on Cryptographic Hardware and Embedded Systems. Springer, Berlin, Heidelberg, 2013.