With an ECDSA signature, we sign a message with a private key (\(priv\)) and prove the signature with the public key (\(pub\)). A random value (a nonce) is then used to randomize the signature. Each time we sign, we create a random nonce value and it will produce a different (but verifiable) signature. The private key, though, can be discovered if Alice signs two different messages with the same nonce [1]. In this case we will use SECP256k1.
ECDSA: Revealing the private key, if same nonce used (with SECP256k1) |
Theory
In ECDSA, Bob creates a random private key (\(priv\)), and then a public key from:
\(pub= priv \times G\)
Next, in order to create a signature for a message of \(M\), he creates a random number (\(k\)) and generates the signature of:
\(r = k \cdot G\)
\(s = k^{-1} (H(M) + r \cdot priv)\)
The signature is then \((r,s)\) and where \(r\) is the x-co-ordinate of the point \(kG\). \(H(M)\) is the SHA-256 hash of the message (\(M\)), and converted into an integer value.
Now let's say we have two messages (\(m_1\) and \(m_2\)) and have hashes of:
\(h_1=H(m_1)\)
\(h_2=H(m_2)\)
Now let's say that Alice signs the messages with the same private key (\(priv\) and the same nonce (\(k\), we can then recover the private key with:
\( \frac{s_2 \cdot h_1 - s_1 \cdot h_2}{r(s_1-s_2)} = \frac{h_1 \cdot h_2+r \cdot h_1 \cdot priv-h_1 \cdot h_2-r \cdot h_2 \cdot priv}{r \cdot h_1 \cdot r \cdot priv-r \cdot h_2-r \cdot priv} = \frac{r \cdot h_1 \cdot priv - r \cdot h_2 \cdot priv}{r \cdot h_1 - r \cdot h_2} = priv \)
We can also recover the nonce with:
\( \frac{h_1-h_2}{s_1-s_2} = \frac{h_1-h_2}{k^{-1}(h_1-h_2+priv(r-r))} = k\)
Here is some code which does a discovery of the private key, and the nonce (\(k\)) if we use the same nonce value:
import ecdsa import random import libnum import hashlib import sys G = ecdsa.SECP256k1.generator order = G.order() priv1 = random.randrange(1,order) Public_key = ecdsa.ecdsa.Public_key(G, G * priv1) x1 = ecdsa.ecdsa.Private_key(Public_key, priv1) k = random.randrange(1, 2**127) msg1="Hello" msg2="Hello1" if (len(sys.argv)>1): msg1=(sys.argv[1]) if (len(sys.argv)>2): msg2=(sys.argv[2]) h1 = int(hashlib.sha256(msg1.encode()).hexdigest(),base=16) h2 = int(hashlib.sha256(msg2.encode()).hexdigest(),base=16) sig1 = x1.sign(h1, k) sig2 = x1.sign(h2, k) r1,s1 = sig1.r,sig1.s r2,s2 = sig2.r,sig2.s valinv = libnum.invmod( r1*(s1-s2),order) x1rec = ( (s2*h1-s1*h2) * (valinv)) % order print ("Message 1: ",msg1) print (f"Signature r={r1}, s={s1}") print ("\nMessage 2: ",msg2) print (f"Signature r={r2}, s={s2}") print ("\nPrivate key",priv1) print ("\nPrivate recovered ",x1rec) valinv = libnum.invmod( (s1-s2),order) k1rec = ( (h1-h2) * valinv) % order print ("\nK: ",k) print ("\nK recovered ",k1rec)
A sample run is:
Message 1: hello Signature r=16163824871702315365636544754327339671279830383115616072776286071644348532176, s=78942102071383249892109282228339664393041099900407940222266026023142592864884 Message 2: hello1 Signature r=16163824871702315365636544754327339671279830383115616072776286071644348532176, s=83502523167965149244641473202679268630845178075816922294718909855670078364206 Private key 6542179820561127199468453109220159836323733777364616770035873205004743487369 Private recovered 6542179820561127199468453109220159836323733777364616770035873205004743487369 K: 109308891778201478280270581205739604663 K recovered 109308891778201478280270581205739604663
Presentation
References
[1] Brengel, M., & Rossow, C. (2018, September). Identifying key leakage of bitcoin users. In International Symposium on Research in Attacks, Intrusions, and Defenses (pp. 623-643). Springer, Cham [here].