In this blog: https://web.archive.org/web/20160308014317/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:


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


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

# this case can be wrong
r =0x0861cce1da15fc2dd79f1164c4f7b3e6c1526e7e8d85716578689ca9a5dc349d

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

In fact, there have another one met this problem:


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

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)

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

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. 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
r =0x0861cce1da15fc2dd79f1164c4f7b3e6c1526e7e8d85716578689ca9a5dc349d  

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))  



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.