I wrote my own ECDSA signature algorithm just for the purpose of creating unit tests.

With it I created two signatures which went into transaction 56ec7ca7df..., sending from 1GXFXm3es.... These signatures used the same k values, although k values must never be reused.

Later on, someone was able to steal 0.0016 btc from 1GXFXm3es.... and sent them to 17WRjamox6VhTUaHsTWfFnMNDYHvwCtWio.

So someone must be monitoring the blockchain for mistakes like this and stealing funds if they encounter them.

How do you derive the private key from two signatures that share the same k value?

up vote 18 down vote accepted

ECDSA signatures are pairs (r,s) where r=(kG).x mod n, and s = (m + rx)/k mod n, where x is the secret key, k is the random nonce, and m is the message.

If you have two s values s1 and s2 for the same secret key and with the same nonce k (and thus the same value r), the following holds:

  • s1 = (m1 + r*x)/k
  • s2 = (m2 + r*x)/k

From that we can derive:

  • s1 * k = m1 + r*x
  • s2 * k = m2 + r*x
  • (s1 - s2) * k = m1 - m2
  • k = (m1 - m2) / (s1 - s2)
  • x = (s1 * (m1 - m2) / (s1 - s2) - m1) / r
  • x = (m1*s2 - m2*s1) / (r*(s1 - s2)) (all mod n)

So not only did you make it trivial to detect signatures with the same nonce (they have a recognizable r value), there is a trivial formula to compute the private key once someone sees two signatures.

This kind of attack has been known and actively exploited on the Bitcoin network since at least 2013: https://bitcointalk.to/index.php?topic=271486.0 . Don't reuse k values. Use RFC6979 to deterministically but securely generate them.

Also note that it's not sufficient that the nonces are different. They also can't be related in a known way. For example, you can't use k for one signature, and k+1 for the next work.

  • 2
    Thank you. I wanted deterministic signatures so I just entered a fixed number for my unit tests. But RFC6979 is a much better solution. – Thorkil Værge Apr 8 at 12:55

If you know two signatures about one random number, you can calculate the private key.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.