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

Question

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 send 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?

Answer 1

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 = (m1s2 - m2s1) / (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.org/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.

Answer 2

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

Answer 3

It's simple!!

1. https://blockchain.info/tx/56ec7ca7dfea1c105acf0974331686e973b737e1fd97fc7f970a0cf0882ba7ac?format=hex

2. https://2xoin.com/getRSZfromRawTX/

"sigR": "00db0c51cc634a4096374b0b895584a3ca2fb3bea4fd0ee2361f8db63a650fcee6",
"sigS": "59a23e4521da413a2c7d0f9a668eedc2e5eac88347c67c48dcca0128fda1cad7",
"sigZ": "4b2cdf712dc7d3fac8e7ed63b3a2e806556ca7d5c30ed5f4b34dbb2a12b0c18f",
"pubKey": "02ac75a5bd9640d55b8300fad347740ac447e4604fbc59260c2dce39f356a0558f",

"sigR": "00db0c51cc634a4096374b0b895584a3ca2fb3bea4fd0ee2361f8db63a650fcee6",
"sigS": "39d5e056231a5823dc0957e3d0fa3923ce71f781ad67140a6433fe6829bdf811",
"sigZ": "1cd506860c52d7e042f56b33a856b94fdefa3bcc808a06dd3b82619db2c01969",
"pubKey": "02ac75a5bd9640d55b8300fad347740ac447e4604fbc59260c2dce39f356a0558f",

possible k = 539

Public Key: C 02db0c51cc634a4096374b0b895584a3ca2fb3bea4fd0ee2361f8db63a650fcee6

possible k = fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0363c08

Public Key: C 03db0c51cc634a4096374b0b895584a3ca2fb3bea4fd0ee2361f8db63a650fcee6 !!!!!

Privkey = 79c7f119413edb1a9a9a2ea655196e0e3b6380b6d612dcc69c7c143816c8ef29

C L1JSKFNgNh7FyNw642ofHzivm8ua4EqpEqZyVQ8rmC6q6S9RgzYj

Here is the answer to your question!