converting RUBY script into PYTHON ( Recovering private key when someone uses the same k twice )

Question

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

some one please convert above code into python please from Recovering private key when someone uses the same k twice in ECDSA signatures

Answer 1

Here's what I've been doing recently in Python. This isn't a very complete solution (it doesn't validate its input, it requires that you've already decoded the signature into r & s, it doesn't derive a public key or address from the private key, it doesn't deal with signature malleability issues, it only works with certain types of curves such as Bitcoin's secp256k1), but it should be adequate in most cases.

n  = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141  # order of base point G
r  = 0xd47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1
s1 = 0x78c9d47ef31caf0102f9ae2489d7c78ab51692ddd898b6eb20b16a0d25b01c78
z1 = 0x4435b0704795962ac9efe71b841a5366434f552d8b5beca04a48426c15fd9ad7
s2 = 0x240bcda3967d66c71c92ffc4c4486d99968183f198c5fe1612a5cc99a05ba99a
z2 = 0x6b8bb3201a7ce4c7ed72eddc46d9b6d7350bc2eb8c28df9763518de8d66b0b52

def modinv(x, n=n): return pow(x, n-2, n)  # modular multiplicative inverse (requires that n is prime)

k = (z1 - z2) * modinv(s1 - s2) % n ; print('k = {:x}'.format(k))
print('privkey = {:x}'.format( (s1 * k - z1) * modinv(r) % n ))  # these two should
print('privkey = {:x}'.format( (s2 * k - z2) * modinv(r) % n ))  # be the same

Updated code

Here's a more complete (but also more difficult to read) version which which (a) displays different possibilities to compensate for negated s values (as noted by David Grayson in this answer), and (b) verifies the private key against the signature-derived public keys if you have pycoin installed.

# order of base point G of secp256k1
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

# modular multiplicative inverse (requires that n is prime)
def modinv(x, n=n):
    return pow(x, n-2, n)

# the two k candidates which aren't just negations of themselves
def k_candidates(s1, z1, s2, z2, n=n):
    z1_z2 = z1 - z2
    yield z1_z2 * modinv(s1 - s2, n) % n
    yield z1_z2 * modinv(s1 + s2, n) % n

# generates two tuples, each with (privkey, k_possibility_1, k_possibility_2)
def privkey_k_candidates(r, s1, z1, s2, z2, n=n):
    modinv_r = modinv(r, n)
    for k in k_candidates(s1, z1, s2, z2, n):
        yield (s1 * k - z1) * modinv_r % n,  k,  -k % n


r  = 0xd47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1
s1 = 0x78c9d47ef31caf0102f9ae2489d7c78ab51692ddd898b6eb20b16a0d25b01c78
z1 = 0x4435b0704795962ac9efe71b841a5366434f552d8b5beca04a48426c15fd9ad7
s2 = 0x240bcda3967d66c71c92ffc4c4486d99968183f198c5fe1612a5cc99a05ba99a
z2 = 0x6b8bb3201a7ce4c7ed72eddc46d9b6d7350bc2eb8c28df9763518de8d66b0b52

try:
    from pycoin.ecdsa import *
    pubkeys = possible_public_pairs_for_signature(generator_secp256k1, z1, (r, s1))
    for privkey, k1, k2 in privkey_k_candidates(r, s1, z1, s2, z2):
        if public_pair_for_secret_exponent(generator_secp256k1, privkey) in pubkeys:
            print('k       = {:x}'.format(k1))
            print('or k    = {:x}'.format(k2))
            print('privkey = {:x}'.format(privkey))
            break
    else:
        print('privkey not found')

except ImportError:
    for privkey, k1, k2 in privkey_k_candidates(r, s1, z1, s2, z2):
        print('possible k       = {:x}'  .format(k1))
        print('possible k       = {:x}'  .format(k2))
        print('possible privkey = {:x}\n'.format(privkey))