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

  • I think you should preserve the indentation the original script had so it will be easier for people to read. – David Grayson Jun 3 '15 at 17:29
  • why this ques get -1 i need the ruby script in python , then whats wrong with this, -1 is very bad – Prabu r Jun 8 '15 at 5:21
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))
| improve this answer | |
  • Unlike the script in the original post (which I wrote), the script in this answer does not account for the fact that the signs on s1 and s2 might have been flipped, requiring you to try 4 different possible values for k. I think you are aware of this because you did mention "signature malleability issues". – David Grayson Jun 3 '15 at 17:26
  • @DavidGrayson You're right, it doesn't take into account that s1 and s2 may have been negated by a third party. I was being a bit lazy when I posted this; I'll update it in a bit. – Christopher Gurnee Jun 3 '15 at 19:05
  • What is going on with all these posts? I assume the BCI random.org debacle? – Wizard Of Ozzie Jun 4 '15 at 7:16
  • @WizardOfOzzie Perhaps, but the txs which OP has been referencing as examples date back to 2012, long before the two (sigh....) recent BCI failures. – Christopher Gurnee Jun 4 '15 at 9:31
  • 1
    @WizardOfOzzie BCI doesn't use Bouncy Castle (BCI is JavaScript, Bouncy Castle is Java). I was referring to this issue where BCI messed up their RNG, and if not for user johoe's heroic efforts, they would have lost 260+ of their users' btc. They've also had SSL downgrade attack issues, HSTS issues, and probably others.... – Christopher Gurnee Jun 4 '15 at 11:18

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.