當有人在 ECDSA 簽名中使用相同的 k 兩次時恢復私鑰

在此部落格中：https ://web.archive.org/web/20160308014317/http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html 作者展示了一個使用案例相同的 k 兩次會洩漏私鑰。

這個方法很多人都知道。但我有時發現，公式不能給出正確的答案（或者我計算錯誤）。

看這個，可以通過公鑰驗證簽名：

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

所以輸入數據：

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

我鍛煉：

private key = eaa57720a5b012351d42b2d9ed6409af2b7cff11d2b8631684c1c97f49685fbb
public key = 04e0e81185567ea58fc7e7258aa4d5c3e201a8d4ce2810c1007d87727a67eeb9a8c2ba06935280209f8bf42fc7603b65095f036044c4124ddf7c6a250cb450e4c8

然而，這是錯誤的。

我正在使用這個 python 程式碼來計算：

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

其實還有一個人遇到過這個問題：

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

但他沒有提供更多資訊，也許他想通了。

我沒有發現更多的人抱怨它，所以，不知何故，這很可能是我的錯。

你能指出我的錯誤嗎？或者只是指出正確的方法？謝謝你。

這是關於 ECDSA 簽名的一個有趣的事情：你總是可以替換s為-s(mod N) 並且簽名仍然有效。因此，當您推斷k值時，有可能其他人翻轉了符號，s您將不得不撤消它。因此，您必須列出（候選人k？）的候選人名單，然後選擇實際有效的候選人。k 候選人的一個好的列表是：

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

我喜歡使用Ruby ECDSA gem來玩這些東西。這是我編寫的程式碼，它成功找到了您提供的第一個輸入數據的私鑰：

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

程序的輸出是：

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

引用自：https://bitcoin.stackexchange.com/questions/35848