12

In this blog: http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html the author showed a case that using same k twice will leak private key.

Many people know this method. But I find sometimes, the formula can not give the right answer(or I compute wrong).

Look at this, you can verify signatures by public key:

public_key = 02a50eb66887d03fe186b608f477d99bc7631c56e64bb3af7dc97e71b917c5b364
msghash1 = 01b125d18422cdfa7b153f5bcf5b01927cf59791d1d9810009c70cd37b14f4e6
msghash2 = 339ff7b1ced3a45c988b3e4e239ea745db3b2b3fda6208134691bd2e4a37d6e1
sig1 = 304402200861cce1da15fc2dd79f1164c4f7b3e6c1526e7e8d85716578689ca9a5dc349d02206cf26e2776f7c94cafcee05cc810471ddca16fa864d13d57bee1c06ce39a3188
sig2 = 304402200861cce1da15fc2dd79f1164c4f7b3e6c1526e7e8d85716578689ca9a5dc349d02204ba75bdda43b3aab84b895cfd9ef13a477182657faaf286a7b0d25f0cb9a7de2

So input data:

r=0861cce1da15fc2dd79f1164c4f7b3e6c1526e7e8d85716578689ca9a5dc349d
s1=6cf26e2776f7c94cafcee05cc810471ddca16fa864d13d57bee1c06ce39a3188
s2=4ba75bdda43b3aab84b895cfd9ef13a477182657faaf286a7b0d25f0cb9a7de2
z1=01b125d18422cdfa7b153f5bcf5b01927cf59791d1d9810009c70cd37b14f4e6
z2=339ff7b1ced3a45c988b3e4e239ea745db3b2b3fda6208134691bd2e4a37d6e1

I work out:

private key = eaa57720a5b012351d42b2d9ed6409af2b7cff11d2b8631684c1c97f49685fbb
public key = 04e0e81185567ea58fc7e7258aa4d5c3e201a8d4ce2810c1007d87727a67eeb9a8c2ba06935280209f8bf42fc7603b65095f036044c4124ddf7c6a250cb450e4c8

However, it's wrong.

I'm using this python code to compute:

# this function is from 
# https://github.com/warner/python-ecdsa/blob/master/ecdsa/numbertheory.py
def inverse_mod( a, m ):
    """Inverse of a mod m."""
    if a < 0 or m <= a: a = a % m
    # From Ferguson and Schneier, roughly:
    c, d = a, m
    uc, vc, ud, vd = 1, 0, 0, 1
    while c != 0:
        q, c, d = divmod( d, c ) + ( c, )
        uc, vc, ud, vd = ud - q*uc, vd - q*vc, uc, vc

    # At this point, d is the GCD, and ud*a+vd*m = d.
    # If d == 1, this means that ud is a inverse.
    assert d == 1
    if ud > 0: return ud
    else: return ud + m


def derivate_privkey(p, r, s1, s2, hash1, hash2):
    z = hash1 - hash2
    s = s1 - s2
    r_inv = inverse_mod(r, p)
    s_inv = inverse_mod(s, p)
    k = (z * s_inv) % p
    d = (r_inv * (s1 * k - hash1)) % p
    return d, k


p  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

# this case is right
public_key=0x04dbd0c61532279cf72981c3584fc32216e0127699635c2789f549e0730c059b81ae133016a69c21e23f1859a95f06d52b7bf149a8f2fe4e8535c8a829b449c5ff
r =0xd47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1
s1=0x44e1ff2dfd8102cf7a47c21d5c9fd5701610d04953c6836596b4fe9dd2f53e3e
s2=0x9a5f1c75e461d7ceb1cf3cab9013eb2dc85b6d0da8c3c6e27e3a5a5b3faa5bab
z1=0xc0e2d0a89a348de88fda08211c70d1d7e52ccef2eb9459911bf977d587784c6e
z2=0x17b0f41c8c337ac1e18c98759e83a8cccbc368dd9d89e5f03cb633c265fd0ddc
print "private:%x\n random:%x" % derivate_privkey(p,r,s1,s2,z1,z2)
print

# this case can be wrong
public_key=0x02a50eb66887d03fe186b608f477d99bc7631c56e64bb3af7dc97e71b917c5b364
r =0x0861cce1da15fc2dd79f1164c4f7b3e6c1526e7e8d85716578689ca9a5dc349d
s1=0x6cf26e2776f7c94cafcee05cc810471ddca16fa864d13d57bee1c06ce39a3188
s2=0x4ba75bdda43b3aab84b895cfd9ef13a477182657faaf286a7b0d25f0cb9a7de2
z1=0x01b125d18422cdfa7b153f5bcf5b01927cf59791d1d9810009c70cd37b14f4e6
z2=0x339ff7b1ced3a45c988b3e4e239ea745db3b2b3fda6208134691bd2e4a37d6e1

print "private:%x\n random:%x" % derivate_privkey(p,r,s1,s2,z1,z2)

In fact, there have another one met this problem:

https://crypto.stackexchange.com/questions/16615/ecdsa-how-to-retrieve-a-non-random-k

But he didn't gave more infomation, maybe he figured it out.

I have not found more people complaining about it, so, it's likely my fault somehow.

Can you point out my error? or just point out the right way? Thank you.

  • It seems like the second public key is compressed - maybe that's the issue? – Nick ODell Feb 2 '15 at 4:30
  • no, signature has nothing to do with public key compressed or not. because verifing signature always using uncompressed public key. and the formula doesn't need public key. – jiedo Feb 2 '15 at 4:44
13

Here is a fun thing about ECDSA signatures: you can always replace s with -s (mod N) and the signature is still valid. So when you are deducing the k value, it is possible that someone else flipped the sign of s and you will have to undo it. So, you have to make a list of candidates for k (kandidates?) and then select whichever one actually works. A good list of k candidates would be:

  • (z1 - z2) / (s1 - s2)
  • (z1 - z2) / (s1 + s2)
  • (z1 - z2) / (-s1 - s2)
  • (z1 - z2) / (-s1 + s2)

I like to use the Ruby ECDSA gem to play around with this kind of stuff. Here is the code I wrote which successfully finds the private key for the first input data you gave:

require 'ecdsa'

public_key_hex = '02a50eb66887d03fe186b608f477d99bc7631c56e64bb3af7dc97e71b917c5b364'
msghash1_hex = '01b125d18422cdfa7b153f5bcf5b01927cf59791d1d9810009c70cd37b14f4e6'
msghash2_hex = '339ff7b1ced3a45c988b3e4e239ea745db3b2b3fda6208134691bd2e4a37d6e1'
sig1_hex = '304402200861cce1da15fc2dd79f1164c4f7b3e6c1526e7e8d85716578689ca9a5dc349d02206cf26e2776f7c94cafcee05cc810471ddca16fa864d13d57bee1c06ce39a3188'
sig2_hex = '304402200861cce1da15fc2dd79f1164c4f7b3e6c1526e7e8d85716578689ca9a5dc349d02204ba75bdda43b3aab84b895cfd9ef13a477182657faaf286a7b0d25f0cb9a7de2'

group = ECDSA::Group::Secp256k1

def hex_to_binary(str)
  str.scan(/../).map(&:hex).pack('C*')
end

public_key_str = hex_to_binary(public_key_hex)
public_key = ECDSA::Format::PointOctetString.decode(public_key_str, group)

puts 'public key x: %#x' % public_key.x
puts 'public key y: %#x' % public_key.y

msghash1 = hex_to_binary(msghash1_hex)
msghash2 = hex_to_binary(msghash2_hex)
sig1 = ECDSA::Format::SignatureDerString.decode(hex_to_binary(sig1_hex))
sig2 = ECDSA::Format::SignatureDerString.decode(hex_to_binary(sig2_hex))

raise 'R values are not the same' if sig1.r != sig2.r

r = sig1.r
puts 'sig r: %#x' % r
puts 'sig1 s: %#x' % sig1.s
puts 'sig2 s: %#x' % sig2.s

sig1_valid = ECDSA.valid_signature?(public_key, msghash1, sig1)
sig2_valid = ECDSA.valid_signature?(public_key, msghash2, sig2)
puts "sig1 valid: #{sig1_valid}"
puts "sig2 valid: #{sig2_valid}"

# Step 1: k = (z1 - z2)/(s1 - s2)
field = ECDSA::PrimeField.new(group.order)
z1 = ECDSA::Format::IntegerOctetString.decode(msghash1)
z2 = ECDSA::Format::IntegerOctetString.decode(msghash2)

k_candidates = [
  field.mod((z1 - z2) * field.inverse(sig1.s - sig2.s)),
  field.mod((z1 - z2) * field.inverse(sig1.s + sig2.s)),
  field.mod((z1 - z2) * field.inverse(-sig1.s - sig2.s)),
  field.mod((z1 - z2) * field.inverse(-sig1.s + sig2.s)),
]

private_key = nil
k_candidates.each do |k|
  next unless group.new_point(k).x == r
  private_key_maybe = field.mod(field.mod(sig1.s * k - z1) * field.inverse(r))
  if public_key == group.new_point(private_key_maybe)
    private_key = private_key_maybe
  end
end

puts 'private key: %#x' % private_key

The output of the program is:

public key x: 0xa50eb66887d03fe186b608f477d99bc7631c56e64bb3af7dc97e71b917c5b364
public key y: 0x7954da3444d33b8d1f90a0d7168b2f158a2c96db46733286619fccaafbaca6bc
sig r: 0x861cce1da15fc2dd79f1164c4f7b3e6c1526e7e8d85716578689ca9a5dc349d
sig1 s: 0x6cf26e2776f7c94cafcee05cc810471ddca16fa864d13d57bee1c06ce39a3188
sig2 s: 0x4ba75bdda43b3aab84b895cfd9ef13a477182657faaf286a7b0d25f0cb9a7de2
sig1 valid: true
sig2 valid: true
private key: 0xe773cf35fce567d0622203c28f67478a3361bae7e6eb4366b50e1d27eb1ed82e
  • very good! I find the first two candidates are enough, last two are the same thing. – jiedo Feb 2 '15 at 8:34
  • 1
    I considered that, but actually you do need all 4 candidates. Only one of the 4 produces the right public key in the end. The formula (s*k-z)/r is affected by the sign of k. – David Grayson Feb 2 '15 at 16:27
  • Adding to David Grayson's excellent answer the python ecdsa-private-key-recovery library is an easy to use wrapper for ecdsa/dsa signatures that is capable of recovering the private key from signatures sharing the same k/r. Once recovered you'll get ready to use private key populated Cryptodome/PyCrypto/ecdsa objects. The lib can easily be used to recover private keys from vulnerable btc transactions. – tintin Aug 23 '17 at 20:56
0
r =0x0861cce1da15fc2dd79f1164c4f7b3e6c1526e7e8d85716578689ca9a5dc349d  
s1=0x6cf26e2776f7c94cafcee05cc810471ddca16fa864d13d57bee1c06ce39a3188  
s2=0x4ba75bdda43b3aab84b895cfd9ef13a477182657faaf286a7b0d25f0cb9a7de2  
z1=0x01b125d18422cdfa7b153f5bcf5b01927cf59791d1d9810009c70cd37b14f4e6  
z2=0x339ff7b1ced3a45c988b3e4e239ea745db3b2b3fda6208134691bd2e4a37d6e1  


h1 = r*(s1-s2)  
p1 = (z1*s2) - (z2*s1)  

h1 = r*(s1+s2)  
p1 = (z1*s2) - (z2*s1)  

h1 = r*(-s1-s2)  
p1 = (z1*s2) - (z2*s1)  

h1 = r*(-s1+s2)  
p1 = (z1*s2) - (z2*s1)  

h1 = r*(s1-s2)  
p1 = (z1*s2) + (z2*s1)  

h1 = r*(s1+s2)  
p1 = (z1*s2) + (z2*s1)  

h1 = r*(-s1+s2)  
p1 = (z1*s2) + (z2*s1)  

h1 = r*(-s1-s2)  
p1 = (z1*s2) + (z2*s1)  
print(hex((p1 *inverse_mod(h1, p)) % p))  

output:

0xe773cf35fce567d0622203c28f67478a3361bae7e6eb4366b50e1d27eb1ed82e

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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