简介

最近从 Ethernaut 学习到了很多，抛开那些比较基础的，记录一些 ECDSA 相关的

以下公式中小写字母代表一个值，大写字母代表一个点，除了 N 是曲线的 order

我们知道 ECDSA 依赖于椭圆曲线上的离散对数问题，对于私钥 privkey，公钥 PubKey 是椭圆曲线上的一个点并且有 $\text{PubKey} = \text{privkey} \cdot G$，其中 G 是椭圆曲线的生成元，正是因为椭圆曲线上的离散对数问题，已知 PubKey 和 G 求 privkey 是困难的，才让数字签名得以可能

Sign

签名公式

$$ s = k^{-1} \cdot (h + r \cdot \text{privkey})\mod{N} $$

k 是随机数，RFC6979 提供了生成方法，不建议真的随机生成，因为重用会导致私钥泄漏，后续会提到

h 是要被签名的 hash 值

r 是 k * G 这个点的 x 轴坐标

计算出 s 后，和 r 共同构成签名 (r, s)，但在签名恢复的过程还会产生歧义，有两种结果，所以还要引入一个 v 来确认是哪一个结果，后续会提到

 1import hashlib
 2from eth_hash.auto import keccak
 3from ecdsa import SECP256k1
 4from ecdsa.rfc6979 import generate_k
 5
 6CURVE = SECP256k1
 7N = CURVE.order
 8G = CURVE.generator
 9
10priv_key = 0xac0974bec39a17e36ba4a6b4d238ff944bacb478cbed5efcae784d7bf4f2ff80
11
12h = keccak(b'hello')
13print(f'hash: 0x{h.hex()}')
14
15h_int = int.from_bytes(h, 'big')
16
17# random k, important
18k = generate_k(
19    order=N,
20    secexp=priv_key,
21    hash_func=hashlib.sha256,
22    data=h,
23)
24
25R = k * G
26r = R.x() % N
27k_inv = pow(k, -1, N)
28
29# s = k^-1 * (h + r * pk)
30s = (k_inv * (h_int + r * priv_key)) % N
31
32print(f'sig : 0x{r.to_bytes(32, 'big').hex()}{s.to_bytes(32, 'big').hex()}')
33print(f'r   : 0x{r.to_bytes(32, 'big').hex()}')
34print(f's   : 0x{s.to_bytes(32, 'big').hex()}')

Recover

签名恢复公式，即从签名 (r, s) 中恢复出公钥 Pub

已知签名公式，可以推导

$$ \begin{aligned} s &= k^{-1} \cdot (h + r \cdot \text{privkey}) &\mod{N} \\ \text{privkey} &= (s \cdot k - h) \cdot r^{-1} &\mod{N} \\ \text{Pub} &= \text{privkey} \cdot G \\ &= (s \cdot k - h) \cdot r^{-1} \cdot G & \\ &= (s \cdot k \cdot G - h \cdot G) \cdot r^{-1} & \\ &= (s \cdot R - h \cdot G) \cdot r^{-1} & \\ \end{aligned} $$

其中 R 是 k * G 得到的点，而签名中的 r 是点 R 的 x 轴坐标，而 R 这个点又在椭圆曲线上，所以可以通过 x 轴坐标带入椭圆曲线公式计算出 y 轴坐标从而得到 R

根据椭圆曲线公式我们知道对于每一个 x 坐标，y 都会有两个不同的取值，并且刚好一正一负（但 mod p 之后就没有负数了），这两个不同取值就可以恢复出两个不同的公钥，具体应该取哪一个就要依赖于签名过程提供的 v 了，这里给出的示例没有使用 v，计算了两个结果

 1# utils.py
 2from ecdsa import SECP256k1
 3from ecdsa.numbertheory import square_root_mod_prime
 4
 5# y^2 = x^3 + ax + b mod p
 6def curve_x_to_y(x, CURVE = SECP256k1):
 7    a = CURVE.curve.a()
 8    b = CURVE.curve.b()
 9    p = CURVE.curve.p()
10
11    try:
12        y = square_root_mod_prime((pow(x, 3, p) + a * x + b) % p, p)
13    except Exception as e:
14        raise ValueError(f'square_root_mod_prime() error: {e}')
15
16    return [y, p-y]

 1import utils
 2
 3from eth_hash.auto import keccak
 4from eth_utils import to_checksum_address
 5from ecdsa import SECP256k1
 6from ecdsa.ellipticcurve import Point
 7
 8CURVE = SECP256k1
 9N = CURVE.order
10G = CURVE.generator
11
12h = keccak(b'hello')
13print(f'hash: 0x{h.hex()}')
14
15h_int = int.from_bytes(h, 'big')
16
17# R = k * G
18# r = x of R(x, y)
19# pub = pk * G
20
21# s = k^-1 * (h + r * pk)
22# r^-1 * (s * k - h) = pk
23# pub = r^-1 * (s * k - h) * G
24# pub = r^-1 * (s * k * G - h * G)
25# pub = r^-1 * (s * R - h * G)
26
27r = 0x73eebf81a611136662d65778960c853fdcaf6eca86793ed9cabc30f2195937af
28s = 0x78a07e601627da5b4cc80c0ab35f6894da19b4a01759d90c101d9c9dd1c6745d
29
30r_inv = pow(r, -1, N)
31r_y_candidates = utils.curve_x_to_y(r, CURVE=CURVE)
32
33for r_y in r_y_candidates:
34    try:
35        R = Point(curve=CURVE.curve, x=r, y=r_y, order=N)
36    except Exception as e:
37        raise ValueError(f'Point() error: {e}')
38
39    tmp = s * R + (-h_int % N) * G.to_affine() # to_affine: PointJacobi => Point
40    pub = r_inv * tmp
41    pub_bytes = pub.x().to_bytes(32, 'big') + pub.y().to_bytes(32, 'big')
42    print(f'pub : 0x{pub_bytes.hex()}')
43    pub_hash = keccak(pub_bytes)
44    print(f'addr: {to_checksum_address('0x' + pub_hash.hex()[-40:])}')

Nonce reuse

在签名过程中有一个随机数 k 很重要，也叫做 nonce，它一定是不能被重复使用的，一旦私钥用了相同的 nonce 签名了两个不同的 hash，就会导致私钥泄漏，这也是为什么每次签名都应该遵循 RFC 来生成安全的 nonce

现在假定有个私钥使用了同样的 k 签名了两个不同的 hash 分别是 h1, h2 得到两个不同的签名 s1, s2

k 相同也就意味着 R = k * G 也相同，r = R.x() mod N，所以签名中的 r 也相同

根据签名公式我们可以进行以下推导

$$ \begin{gathered} \begin{aligned} s1 &= k^{-1} \cdot (h1 + r \cdot \text{privkey}) &\mod{N} \\ s2 &= k^{-1} \cdot (h2 + r \cdot \text{privkey}) &\mod{N} \end{aligned} \\[2em] \begin{aligned} k \cdot s1 - h1 &= r \cdot \text{privkey} &\mod{N} \\ k \cdot s2 - h2 &= r \cdot \text{privkey} &\mod{N} \end{aligned} \\[2em] \begin{aligned} k \cdot s1 - h1 &= k \cdot s2 - h2 &\mod{N} \\ k &= (h1 - h2) \cdot (s1 - s2)^{-1} &\mod{N} \end{aligned} \\[2em] \begin{aligned} h1 + r \cdot \text{privkey} &= s1 \cdot (h1 - h2) \cdot (s1 - s2)^{-1} &\mod{N} \\ \text{privkey} &= (h1 \cdot s2 - s1 \cdot h2) \cdot (s1-s2)^{-1} \cdot r^{-1} &\mod{N} \end{aligned} \end{gathered} $$

于是就能通过已知的 s1 s2 h1 h2 和 r 共同计算出私钥

 1from ecdsa import SECP256k1
 2
 3CURVE = SECP256k1
 4N = CURVE.order
 5
 6r = 0xe5648161e95dbf2bfc687b72b745269fa906031e2108118050aba59524a23c40
 7
 8s1 = 0x4c3ac03b268ae1d2aca1201e8a936adf578a8b95a49986d54de87cd0ccb68a79
 9h1 = 0x6a0d6cd0c2ca5d901d94d52e8d9484e4452a3668ae20d63088909611a7dccc51
10
11s2 = 0x70026fc30e4e02a15468de57155b080f405bd5b88af05412a9c3217e028537e3
12h2 = 0x937fa99fb61f6cd81c00ddda80cc218c11c9a731d54ce8859cb2309c77b79bf3
13
14# s1 = k^-1 * (h1 + r * pk)
15# s2 = k^-1 * (h2 + r * pk)
16
17# k * s1 = h1 + r * pk
18# k * s2 = h2 + r * pk
19
20# k * s1 - h1 = k * s2 - h2
21# k * (s1 - s2) = h1 - h2
22# k = (h1 - h2) * (s1 - s2)^-1
23
24# s1 * (h1 - h2) / (s1 - s2) = h1 + r * pk
25# (s2h1 - s1h2) / (s1 - s2) = r * pk
26# pk = (r * (s1 - s2))^-1 * (s2h1 - s1h2)
27
28tmp = pow((r * (s1 - s2)) % N, -1, N)
29pk = tmp * (s2 * h1 - s1 * h2) % N
30
31print(f'priv: 0x{pk.to_bytes(32, 'big').hex()}')

Spoofing

在签名恢复的过程中，我们可以通过 hash，签名 (r, s) 计算出签名对应的 PubKey

对于同一个私钥，可以对很多不同 hash 签名得到不同的 (r, s)，他们都能恢复出同一个 PubKey

也就是说，对于任意一个 PubKey，都存在很多很多对不同的 hash, (r, s) 的组合可以恢复出这个 PubKey

我们都知道要签名某个确定的 hash 得到对应的 (r, s) 必须要有 privkey 的参与

如果没有 privkey 的参与，那么就只能从很多很多对中随机找出一对了，这就是 Spoofing

也就是当我们已知 PubKey 时，可以随机生成一组 hash, (r, s) 使得其能够恢复出这个 PubKey

根据签名恢复公式可以推导

$$ \begin{gathered} \begin{aligned} \text{Pub} &= (s \cdot R - h \cdot G) \cdot r^{-1} &\mod{N} \\ s \cdot R &= \text{Pub} \cdot r + h \cdot G &\mod{N} \\ R &= r \cdot s^{-1} \cdot \text{Pub} + h \cdot s^{-1} \cdot G &\mod{N} \end{aligned} \\[2em] \begin{aligned} u &= r \cdot s^{-1} &\mod{N} \\ v &= h \cdot s^{-1} &\mod{N} \end{aligned} \\[2em] \begin{aligned} R &= u \cdot \text{Pub} + v \cdot G &\mod{N} \\ s &= u \cdot r^{-1} &\mod{N} \\ h &= v \cdot s &\mod{N} \\ &= v \cdot u \cdot r^{-1} &\mod{N} \end{aligned} \end{gathered} $$

其中随机取了 N 以下的随机数 u 和 v 来作为中间值

计算出 R 点之后就可以得到 r，因为 r 是 R 点的 x 轴横坐标

于是就可以通过 r, u, v 再计算出签名 (r, s) 和 h

这也就告诉我们，不能直接信任传入的 hash，而是要通过已知参数自己计算，并且不能赋予如金额等实际的意义

 1import secrets
 2
 3from ecdsa import SECP256k1
 4from ecdsa.ellipticcurve import Point
 5
 6CURVE = SECP256k1
 7N = CURVE.order
 8G = CURVE.generator
 9
10# pub = r^-1 * (s * R - h * G)
11
12# Pub * r = s * R - h * G
13# h * G = s * R - r * Pub
14
15# R = s^-1 * h * G + s^-1 * r * Pub
16
17# R = u1 * G + u2 * Pub
18# u1 = s^-1 * h
19# u2 = s ^ -1 * r
20# s = r * u2^-1
21# h = s * u1 = r * u2^-1 * u1
22
23alice_pub = 0x33da8e7fe906411e4fc12842632ec77c2aee6a4324a4a3ca554b56667e4ccf97eda346ace5f9dce2781697ad353350c7509e1ffb491fedf49e37d4504185c676
24alice_pub_x = 0x33da8e7fe906411e4fc12842632ec77c2aee6a4324a4a3ca554b56667e4ccf97
25alice_pub_y = 0xeda346ace5f9dce2781697ad353350c7509e1ffb491fedf49e37d4504185c676
26
27u1 = secrets.randbelow(N)
28u2 = secrets.randbelow(N)
29Pub = Point(curve=CURVE.curve, x=alice_pub_x, y=alice_pub_y, order=N)
30
31R = u1 * G.to_affine() + u2 * Pub
32r = R.x() % N
33s = r * pow(u2, -1, N) % N
34h = s * u1 % N
35
36print(f'hash: 0x{h.to_bytes(32, 'big').hex()}')
37print(f'sig : 0x{r.to_bytes(32, 'big').hex()}{s.to_bytes(32, 'big').hex()}')
38print(f'r   : 0x{r.to_bytes(32, 'big').hex()}')
39print(f's   : 0x{s.to_bytes(32, 'big').hex()}')