Image for post
Image for post

ECDSA: Revealing the private key, from four signed messages, two keys and shared nonces (SECP256k1)

It’s well known that the ECDSA signature (as used in Bitcoin) needs to be carefully created, or the private key can be discovered. The nightmare would thus be to sign a few messages and for Eve to then discover the private key from these. In this case, we will look at the case where Alice has two key pairs and signs four messages with these, and for Eve to discover where private keys.

Alice will have two key pairs [1], 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 the 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 for messages 1 and 2, and another nonce (k_2) is used to sign messages 3 and 4. Now let’s say we have four messages (m_1 .. m)4) and have hashes of:

The signatures for the messages will then be (s1,r1), (s2,r1), (s3,r2), and (s4,r2):

Image for post
Image for post

Using Gaussian elimination, we can also recover the private keys with:

Image for post
Image for post

and:

Image for post
Image for post

Here is some code which discovers the private keys [here]:

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) % orderx2rec = ((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 [here]:

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): 82160419381684073393977402015108188969157550419795710258656483526045067388858Private recovered (x1): 82160419381684073393977402015108188969157550419795710258656483526045067388858Private key (x2): 114347697544140976184770951847100304992433696701232754239964044576164337336942Private recovered (x2): 114347697544140976184770951847100304992433696701232754239964044576164337336942

And code:

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].

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store