Wiederherstellen des privaten Schlüssels, wenn jemand dasselbe k zweimal in ECDSA-Signaturen verwendet

In diesem Blog: https://web.archive.org/web/20160308014317/http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html zeigte der Autor einen Fall, bei dem die Verwendung von Dasselbe k zweimal wird den privaten Schlüssel verlieren.

Viele Menschen kennen diese Methode. Aber ich finde manchmal, die Formel kann nicht die richtige Antwort geben (oder ich rechne falsch).

Sehen Sie sich das an, Sie können Signaturen mit dem öffentlichen Schlüssel verifizieren:

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

Also Eingabedaten:

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

Ich trainiere:

private key = eaa57720a5b012351d42b2d9ed6409af2b7cff11d2b8631684c1c97f49685fbb
public key = 04e0e81185567ea58fc7e7258aa4d5c3e201a8d4ce2810c1007d87727a67eeb9a8c2ba06935280209f8bf42fc7603b65095f036044c4124ddf7c6a250cb450e4c8

Es ist jedoch falsch.

Ich verwende diesen Python-Code zur Berechnung:

# 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 der Tat hat ein anderer dieses Problem gelöst:

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

Aber er hat keine weiteren Informationen gegeben, vielleicht hat er es herausgefunden.

Ich habe nicht mehr Leute gefunden, die sich darüber beschwert haben, also ist es wahrscheinlich irgendwie meine Schuld.

Könnt ihr auf meinen Fehler hinweisen? oder nur den richtigen Weg weisen? Vielen Dank.

Es scheint, als wäre der zweite öffentliche Schlüssel komprimiert - vielleicht ist das das Problem?
Nein, die Signatur hat nichts damit zu tun, ob der öffentliche Schlüssel komprimiert ist oder nicht. weil die Überprüfung der Signatur immer einen unkomprimierten öffentlichen Schlüssel verwendet. und die Formel benötigt keinen öffentlichen Schlüssel.

Antworten (3)

Hier ist eine lustige Sache über ECDSA-Signaturen: Sie können immer smit -s(mod N) ersetzen und die Signatur ist immer noch gültig. Wenn Sie also den kWert ableiten, ist es möglich, dass jemand anderes das Zeichen umgedreht shat und Sie es rückgängig machen müssen. Sie müssen also eine Liste mit Kandidaten für k(Kandidaten?) erstellen und dann auswählen, welcher tatsächlich funktioniert. Eine gute Liste mit k Kandidaten wäre:

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

Ich verwende gerne das Ruby ECDSA-Juwel , um mit solchen Sachen herumzuspielen. Hier ist der Code, den ich geschrieben habe, der erfolgreich den privaten Schlüssel für die ersten von Ihnen angegebenen Eingabedaten findet:

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

Die Ausgabe des Programms ist:

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
sehr gut! Ich finde, die ersten beiden Kandidaten reichen aus, die letzten beiden sind dasselbe.
Das habe ich mir überlegt, aber eigentlich braucht man alle 4 Kandidaten. Nur einer der 4 produziert am Ende den richtigen öffentlichen Schlüssel. Die Formel (s*kz)/r wird durch das Vorzeichen von k beeinflusst.
Ergänzend zu David Graysons hervorragender Antwort ist die Python-Bibliothek ecdsa-private-key-recovery ein einfach zu verwendender Wrapper für ecdsa/dsa-Signaturen, der in der Lage ist, den privaten Schlüssel aus Signaturen mit demselben k/r wiederherzustellen. Nach der Wiederherstellung können Sie mit privaten Schlüsseln gefüllte Cryptodome/PyCrypto/ecdsaObjekte verwenden. Die Bibliothek kann leicht verwendet werden, um private Schlüssel von anfälligen BTC-Transaktionen wiederherzustellen.
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))

Ausgang:

0xe773cf35fce567d0622203c28f67478a3361bae7e6eb4366b50e1d27eb1ed82e

Basierend auf der bestehenden Formel von OP und der obigen Antwort von David Grayson ist hier eine modernere (Python 3.8+) Lösung, die sowohl für Bitcoin- als auch für Ethereum-Konten funktioniert, für Neugierige:

r = 0x...
s1 = 0x...
s2 = 0x...
# For Ethereum msg hash, feel free to use this excellent online toolkit: https://toolkit.abdk.consulting/ethereum#recover-address
z1 = 0x...
z2 = 0x...

# This function is from
# https://github.com/tlsfuzzer/python-ecdsa/blob/master/src/ecdsa/numbertheory.py
def inverse_mod(a, m):
    """Inverse of a mod m."""
    if a == 0:  # pragma: no branch
        return 0
    return pow(a, -1, m)

# Magic: https://en.bitcoin.it/wiki/Secp256k1
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

for (i, j) in [(1,1),(1,-1),(-1,1),(-1,-1)]:
    z = z1 - z2
    s = s1*i + s2*j
    r_inv = inverse_mod(r, p)
    s_inv = inverse_mod(s, p)
    k = (z * s_inv) % p
    d = (r_inv * (s1 * k - z1)) % p
    print(f"Private key: {hex(d)}, {hex(k)}")
Wiederherstellen des privaten Schlüssels, wenn jemand dasselbe k zweimal in ECDSA-Signaturen verwendet
AntwortenHierDatenschutz-Bestimmungen1y, 0v