利用重复r值的ECDSA签名恢复以太坊私钥
题目分析
题目很简短:https://capturetheether.com/challenges/accounts/account-takeover/

要求调用 authenticate() 方法的地址等于 owner,等于说给出了地址求私钥。
发现问题
在测试网区块链浏览器 ropsten.etherscan.io 上面查看此地址相关的交易,View Outgoing Txns 可以看到有这样两笔同 from 地址且同 to 地址的交易。

- 0x061bf0b4b5fdb64ac475795e9bc5a3978f985919ce6747ce2cfbbcaccaf51009
- 0xd79fc80e7b787802602f3317b7fe67765c14a7d40c3e0dcb266e63657f881396
查询数据库①,三笔交易中有两笔的 r 值相同:

若两笔交易的 ECDSA 签名信息中 r 值相同的,则意味着这两笔交易使用了相同的随机数 k,通过这我们就能利用这两笔交易的信息来还原出私钥。
知识背景
参考:
https://xz.aliyun.com/t/6295
https://xz.aliyun.com/t/2718
破解过程
目前我们已经有两笔交易的签名值 s1 和 s2:
s1-s2 = k ^ -1(z1 + dA * r)-k ^ -1(z2+ dA * r)
= k^-1(z1-z2)
k = (z1-z2)/(s1-s2)
如果知道了 k,那么私钥 dA = (s*k-z)/r
所以目前未知的参数就是 z,是对要签名的消息取的 hash 值。
使用 nodejs 的 ethereumjs-tx 库来模拟对交易的签名过程,将前面得到的交易信息②进行 hash:
const EthereumTx = require('ethereumjs-tx').Transaction
var rawTx1 ={
nonce: 0,
gasPrice: '0x3b9aca00',
gasLimit: '0x5208',
to: '0x92b28647ae1f3264661f72fb2eb9625a89d88a31',
value: '0x1111d67bb1bb0000',
data: '0x',
v: '0x29',
r: '0x69a726edfb4b802cbf267d5fd1dabcea39d3d7b4bf62b9eeaeba387606167166',
s: '0x7724cedeb923f374bef4e05c97426a918123cc4fec7b07903839f12517e1b3c8'
}
var rawTx2 ={
nonce: 1,
gasPrice: '0x3b9aca00',
gasLimit: '0x5208',
to: '0x92b28647ae1f3264661f72fb2eb9625a89d88a31',
value: '0x1922e95bca330e00',
data: '0x',
v: '0x29',
r: '0x69a726edfb4b802cbf267d5fd1dabcea39d3d7b4bf62b9eeaeba387606167166',
s: '0x2bbd9c2a6285c2b43e728b17bda36a81653dd5f4612a2e0aefdb48043c5108de'
}
const tx1 = new EthereumTx(rawTx1, { chain: 'ropsten', hardfork: 'petersburg' })
const tx2 = new EthereumTx(rawTx2, { chain: 'ropsten', hardfork: 'petersburg' })
const z1 = tx1.hash(false).toString("hex");
const z2 = tx2.hash(false).toString("hex");
console.log(z1);
console.log(z2);
这里要注意:
- 见 line1,新版本的 ethereumjs-tx 跟旧版本此行写法不同
- line 24-25 指明 chain,跟旧版本写法不同
- line 27-28,这个库中的 hash 函数此时要选择参数 false,因为参数为 false 时进行 hash 的对象是不加入签名信息的,也就是我们需要的 z 值,否则默认的参数为 true 得到的就是添加了签名信息的 hash 值,得到的其实就是我们的交易 hash
运行 node script.js 计算得到两个 z 值:
350f3ee8007d817fbd7349c477507f923c4682b3e69bd1df5fbb93b39beb1e04 4f6a8370a435a27724bbc163419042d71b6dcbeb61c060cc6816cda93f57860c
下面继续来计算私钥:
「目前我们已经有两笔交易的签名值 s1 和 s2:
s1-s2 = k ^ -1(z1 + dA * r)-k ^ -1(z2+ dA * r)
= k^-1(z1-z2)
k = (z1-z2)/(s1-s2)
如果知道了 k,那么私钥 dA = (s*k-z)/r」
要注意这里的计算是基于有限域Fp的:
「实数域上的椭圆曲线是连续的,并不适用于加密,考虑到加密算法的可实现性,要把椭圆曲线定义在有限域上,使之变成离散的点。
给定一个有限域Fp:
– Fp只有p(p为素数)个元素0,1,2…p-2,p-1;
– Fp的加法(a+b)法则是a+b≡c(mod p);
– Fp的乘法(a×b)法则是a×b≡c(mod p);
– Fp的除法(a÷b)法则是a÷b≡c(mod p),即a×b^-1≡c(mod p),b^-1为b的逆元;
Fp的单位元是1,零元是0;
Fp域内运算满足交换律、结合律、分配律。参考:https://xz.aliyun.com/t/6295」
这里的 p 应该是多少呢?
为了生成一个随机的32字节、64 hex字符的数作为私钥,大小范围应该介于1~0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 之间,所以这里 ECDSA-secp256k 算法的 p 为定值 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141。
所以私钥 d = (s*k-z)/r
= (s*k-z) * inverse_mod(r, p) % p
k = (z1-z2)/(s1-s2)
= (z1 – z2)*inverse_mod(s1 – s2,p)%p
所以需要定义一个计算模逆元的函数,这里参考:https://github.com/gitzhou/threshold-signature-demo/blob/master/modular_inverse.py
然后得出私钥:
def extended_euclid_gcd(a:int, b:int) -> list:
"""
Returns [gcd(a, b), x, y] where ax + by = gcd(a, b)
"""
s, old_s = 0, 1
t, old_t = 1, 0
r, old_r = b, a
while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r
old_s, s = s, old_s - quotient * s
old_t, t = t, old_t - quotient * t
return [old_r, old_s, old_t]
def inverse_mod(a: int, n: int) -> int:
"""
Assumes that a and n are co-prime, returns modular multiplicative inverse of a under n
"""
# Find gcd using Extended Euclid's Algorithm
gcd, x, y = extended_euclid_gcd(a, n)
# In case x is negative, we handle it by adding extra n
# Because we know that modular multiplicative inverse of a in range n lies in the range [0, n-1]
if x < 0:
x += n
return x
def derivate_privkey(p, r, s1, s2, z1, z2):
z = z1 - z2
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 - z1)) % p
return d, k
z1 = 0x4f6a8370a435a27724bbc163419042d71b6dcbeb61c060cc6816cda93f57860c
s1 = 0x2bbd9c2a6285c2b43e728b17bda36a81653dd5f4612a2e0aefdb48043c5108de
r = 0x69a726edfb4b802cbf267d5fd1dabcea39d3d7b4bf62b9eeaeba387606167166
z2 = 0x350f3ee8007d817fbd7349c477507f923c4682b3e69bd1df5fbb93b39beb1e04
s2 = 0x7724cedeb923f374bef4e05c97426a918123cc4fec7b07903839f12517e1b3c8
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
print("privatekey:%x\n k:%x" % derivate_privkey(p,r,s1,s2,z1,z2))
私钥为:614f5e36cd55ddab0947d1723693fef5456e5bee24738ba90bd33c0c6e68e269
最后将私钥导入小狐狸连接到网站即会成功通过此关:

注解
①
select tx.from,tx.to,
v,r,s,public_key,
nonce
from tx
where tx.from = '0x6B477781b0e68031109f21887e6B5afEAaEB002b'
and upper(tx.to) = '0X92B28647AE1F3264661F72FB2EB9625A89D88A31'
②
select nonce,
gas_price as gasPrice,
gas as gasLimit,
tx.to as to,
value,
input as data,
v,
r,
s
from tx
where tx.from = '0x6B477781b0e68031109f21887e6B5afEAaEB002b'
and upper(tx.to) = '0X92B28647AE1F3264661F72FB2EB9625A89D88A31'
nonce | gasPrice | gasLimit | to | value | data | v | r | s | |
1 | 136 | 43000000000 | 21000 | 0x92b28647Ae1F3264661f72fb2eB9625A89D88A31 | 1230000000000000000 | 0x | 0x2a | 0xf0bc97b376138de15b1657b62a6433e06f013983b6db5ee5071f60083b575b78 | 0x2071470754cd4f9557f3ce79cbf57ff6a2a420018c40a34fa95dce972b6b51c1 |
2 | 1 | 1000000000 | 21000 | 0x92b28647Ae1F3264661f72fb2eB9625A89D88A31 | 1811266580600000000 | 0x | 0x29 | 0x69a726edfb4b802cbf267d5fd1dabcea39d3d7b4bf62b9eeaeba387606167166 | 0x2bbd9c2a6285c2b43e728b17bda36a81653dd5f4612a2e0aefdb48043c5108de |
3 | 0 | 1000000000 | 21000 | 0x92b28647Ae1F3264661f72fb2eB9625A89D88A31 | 1230000000000000000 | 0x | 0x29 | 0x69a726edfb4b802cbf267d5fd1dabcea39d3d7b4bf62b9eeaeba387606167166 | 0x7724cedeb923f374bef4e05c97426a918123cc4fec7b07903839f12517e1b3c8 |
参考:
https://xz.aliyun.com/t/6295
https://xz.aliyun.com/t/2718
https://cryptobook.nakov.com/asymmetric-key-ciphers/elliptic-curve-cryptography-ecc
请问这个数据库是什么工具
http://www.anyblockanalytics.com
无法注册了
SГ, gracias
Bravo, la ciencia-ficciГіn))))
https://mixfilesmaker.com/