En este blog: https://web.archive.org/web/20160308014317/http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html el autor mostró un caso que usando mismo k dos veces filtrará la clave privada.
Mucha gente conoce este método. Pero a veces encuentro que la fórmula no puede dar la respuesta correcta (o calculo mal).
Mira esto, puedes verificar firmas por clave pública:
public_key = 02a50eb66887d03fe186b608f477d99bc7631c56e64bb3af7dc97e71b917c5b364
msghash1 = 01b125d18422cdfa7b153f5bcf5b01927cf59791d1d9810009c70cd37b14f4e6
msghash2 = 339ff7b1ced3a45c988b3e4e239ea745db3b2b3fda6208134691bd2e4a37d6e1
sig1 = 304402200861cce1da15fc2dd79f1164c4f7b3e6c1526e7e8d85716578689ca9a5dc349d02206cf26e2776f7c94cafcee05cc810471ddca16fa864d13d57bee1c06ce39a3188
sig2 = 304402200861cce1da15fc2dd79f1164c4f7b3e6c1526e7e8d85716578689ca9a5dc349d02204ba75bdda43b3aab84b895cfd9ef13a477182657faaf286a7b0d25f0cb9a7de2
Así que datos de entrada:
r=0861cce1da15fc2dd79f1164c4f7b3e6c1526e7e8d85716578689ca9a5dc349d
s1=6cf26e2776f7c94cafcee05cc810471ddca16fa864d13d57bee1c06ce39a3188
s2=4ba75bdda43b3aab84b895cfd9ef13a477182657faaf286a7b0d25f0cb9a7de2
z1=01b125d18422cdfa7b153f5bcf5b01927cf59791d1d9810009c70cd37b14f4e6
z2=339ff7b1ced3a45c988b3e4e239ea745db3b2b3fda6208134691bd2e4a37d6e1
Hago ejercicio:
private key = eaa57720a5b012351d42b2d9ed6409af2b7cff11d2b8631684c1c97f49685fbb
public key = 04e0e81185567ea58fc7e7258aa4d5c3e201a8d4ce2810c1007d87727a67eeb9a8c2ba06935280209f8bf42fc7603b65095f036044c4124ddf7c6a250cb450e4c8
Sin embargo, está mal.
Estoy usando este código Python para calcular:
# 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)
De hecho, hay otro que se encontró con este problema:
https://crypto.stackexchange.com/questions/16615/ecdsa-how-to-retrieve-a-non-random-k
Pero no dio más información, tal vez se dio cuenta.
No he encontrado más personas que se quejen de eso, así que es probable que sea mi culpa de alguna manera.
¿Puedes señalar mi error? o simplemente señalar el camino correcto? Gracias.
Aquí hay algo divertido sobre las firmas ECDSA: siempre puede reemplazar s
con -s
(mod N) y la firma sigue siendo válida. Entonces, cuando estés deduciendo el k
valor, es posible que alguien más cambie el signo s
y tengas que deshacerlo. Entonces, debe hacer una lista de candidatos para k
(¿candidatos?) y luego seleccionar el que realmente funcione. Una buena lista de k candidatos sería:
Me gusta usar la gema Ruby ECDSA para jugar con este tipo de cosas. Aquí está el código que escribí que encuentra con éxito la clave privada para los primeros datos de entrada que proporcionó:
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
La salida del programa es:
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
Cryptodome/PyCrypto/ecdsa
objetos poblados con clave privada. La lib se puede usar fácilmente para recuperar claves privadas de transacciones btc vulnerables.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))
producción:
0xe773cf35fce567d0622203c28f67478a3361bae7e6eb4366b50e1d27eb1ed82e
Basado en la fórmula existente de OP y la respuesta anterior de David Grayson, aquí hay una solución más moderna (Python 3.8+) que funciona para las cuentas de Bitcoin y Ethereum, para aquellos curiosos:
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)}")
Nick ODell
jiedo