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 four messages with two keys and two nonces [1]. In this case she will sign message 1 with the first private key (\(x_1\)), sign message 2 with a second private key (\(x_2\)), sign message 3 with first private key (\(x_1\)) and sign message 4 with the second private key (\(x_2\)) The same nonce (\(k_1\)) is used in the signing for messages 1 and 2, and another nonce (\(k_2\)) is used in the signing of messages 3 and 4.
ECDSA: Revealing the private key, from two keys and shared nonces (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.
In this case Alice will have two key pairs, and with two private keys (\(x_1\) and \(x_2\)). She will sign message 1 (\(m_1\)) with the first private key (\(x_1\)), sign message 2 (\(m_2\)) with a second private key (\(x_2\)), sign message 3 (\(m_3\)) with first private key (\(x_1\)) and sign message 4 (\(m_4\)) with the second private key (\(x_2\)). The same nonce (\(k_1\)) is used in the signing for messages 1 and 2, and another nonce (\(k_2\)) is used in the signing of messages 3 and 4. Now let's say we have four messages (\(m_1\) .. \(m_4\)) and have hashes of:
\(h_1=H(m_1)\)
\(h_2=H(m_2)\)
\(h_3=H(m_3)\)
\(h_4=H(m_4)\)
The signatures for the messages will then be \((s_1,r_1)\), \((s_2,r_1)\), \((s_3,r_2)\), and \((s_4,r_2)\):
\(s_1={k_1}^{-1}(h_1 + r_1 \cdot x_1) \pmod p\)
\(s_2={k_1}^{-1}(h_2 + r_1 \cdot x_2) \pmod p\)
\(s_3={k_2}^{-1}(h_3 + r_2 \cdot x_1) \pmod p\)
\(s_4={k_2}^{-1}(h_4 + r_2 \cdot x_2) \pmod p\)
Using Gaussian elimination, we can also recover the private keys with:
\( x_1=\frac{h_1 r_2 s_2 s_3 - h_2 r_2 s_1 s_3 - h_3 r_1 s_1 s_4 + h_4 r_1 s_1 s_3}{r_1 r_2 (s_1 s_4 - s_2 s_3)} \)
and:
\( x_2=\frac{h_1 r_2 s_2 s_4 - h_2 r_2 s_1 s_4 - h_3 r_1 s_2 s_4 + h_4 r_1 s_2 s_3}{r_1 r_2 (s_2 s_3 - s_1 s_4)} \)
Here is some code which discovers the private keys:
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) priv2 = random.randrange(1,order) Public_key2 = ecdsa.ecdsa.Public_key(G, G * priv2) x2 = ecdsa.ecdsa.Private_key(Public_key2, priv2) k1 = random.randrange(1, 2**127) k2 = random.randrange(1, 2**127) msg1="Hello" msg2="Hello1" msg3="Hello3" msg4="Hello4" if (len(sys.argv)>1): msg1=(sys.argv[1]) if (len(sys.argv)>2): msg2=(sys.argv[2]) if (len(sys.argv)>3): msg3=(sys.argv[3]) if (len(sys.argv)>4): msg4=(sys.argv[4]) h1 = int(hashlib.sha256(msg1.encode()).hexdigest(),base=16) h2 = int(hashlib.sha256(msg2.encode()).hexdigest(),base=16) h3 = int(hashlib.sha256(msg3.encode()).hexdigest(),base=16) h4 = int(hashlib.sha256(msg4.encode()).hexdigest(),base=16) sig1 = x1.sign(h1, k1) sig2 = x2.sign(h2, k1) sig3 = x1.sign(h3, k2) sig4 = x2.sign(h4, k2) r1,s1 = sig1.r,sig1.s r1_1,s2 = sig2.r,sig2.s r2,s3 = sig3.r,sig3.s r2_1,s4 = sig4.r,sig4.s valinv = libnum.invmod( r1*r2*(s1*s4-s2*s3),order) x1rec = ((h1*r2*s2*s3-h2*r2*s1*s3-h3*r1*s1*s4+h4*r1*s1*s3 ) * valinv) % order x2rec = ((h1*r2*s2*s4-h2*r2*s1*s4-h3*r1*s2*s4+h4*r1*s2*s3 ) * valinv) % order print ("Message 1: ",msg1) print (f"Signature r={r1}, s={s1}") print ("\nMessage 2: ",msg2) print (f"Signature r={r1_1}, s={s2}") print ("\nMessage 3: ",msg3) print (f"Signature r={r2}, s={s3}") print ("\nMessage 4: ",msg4) print (f"Signature r={r2_1}, s={s4}") print ("\nPrivate key (x1):",priv1) print ("\nPrivate recovered (x1): ",x1rec) print ("\nPrivate key (x2):",priv2) print ("\nPrivate recovered (x2):",x2rec)
A sample run is:
Message 1: hello Signature r=96094994597103916506348675161520648758285225187589783433159767384063221853577, s=11930786632149881397940019723063699895405239832076777367931993614016265847425 Message 2: hello1 Signature r=96094994597103916506348675161520648758285225187589783433159767384063221853577, s=86716405197525298580208026914311340731533780839926210284720464080897845438167 Message 3: hello2 Signature r=12047241901687561506156261203581292367663176900884185151523104379030284412704, s=42453302255950972549884862083375617752595228510622859389343928824741407916152 Message 4: hello3 Signature r=12047241901687561506156261203581292367663176900884185151523104379030284412704, s=64279036158699242111613174757286438038132181593159757823380636958768174455517 Private key (x1): 82160419381684073393977402015108188969157550419795710258656483526045067388858 Private recovered (x1): 82160419381684073393977402015108188969157550419795710258656483526045067388858 Private key (x2): 114347697544140976184770951847100304992433696701232754239964044576164337336942 Private recovered (x2): 114347697544140976184770951847100304992433696701232754239964044576164337336942
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].