ECDSA

First Post:

Last Update:

ECDSA

ECDSA又叫做椭圆曲线数字签名算法，有点类似于ECC。一般是选定一个曲线E，然后找一个曲线上点P，曲线所处有限域p内选取私钥a，一个质数q，计算Q=aP，公钥为E,P,Q,p，q，私钥为a

每次签名都要选取一个随机数k，对要签名的数据先hash计算，计算kP=(x,y)，签名的第一部分r=x mod q(若r=0则继续选随机数),第二部分$t=k^{-1} mod n$,伪造签名的关键在于私钥a和随机数k，只要知道这两个中任何一个就可以求出另一个，从而伪造签名

ECDSA攻击原理

最基础的一种ECDSA的漏洞模型所随机数k的复用，由于私钥a具有身份标识作用，所以私钥在一段时间内不会更换，如果对两次或以上的签名使用了同一随机数k，就会导致私钥a的泄露，导致签名被伪造。
QQ20250313-205832.png
如果k1和k2之间存在比例关系，那也可以使用这种方法

参数定义

椭圆曲线：由参数组(a,b,p,G,n,h)定义，其中G为基点，n为基点阶数
私钥:随机整数d(1<=d<n)
公钥:Q=d*G

步骤：
1.对m计算哈希值h=Hash(m)
2.生成随机数k
3.计算kG=(x,y),取横坐标r=x mod n
4.计算签名s=k^-1^(h+rd) mod n
5.输出签名(r,s)

过程

现有椭圆曲线

  • y^2^≡x^3^+ax+b mod p
  • n*G=O
  • Qa=da*G
  • e=hash(m)
  • k*G=(x1,y1)
  • r=x1 mod n
  • s=k^-1^(e+rda) mod n
    r和s是数字签名
    验证签名:
  • u1=es^-1^ mod n
  • u2=rs^-1^ mod n
  • u1G+u2Qa
  • =es^-1^*G+rs^-1^(dA*G)
  • =(e+rda)s^-1^*G
  • =k*G=(x1,y1)
  • check if r=x1 mod n
    即先选择一个椭圆曲线和一个基点G，再随机选择一个私钥d，计算公钥(Q=dG)
    再选择一个随机数k(确保每次签名不同),使用椭圆曲线计算点R=k    G,得到R为x的坐标，记为r
    s的公式就和DSA是一样的，即s=k^(-1)(H(m)+dr) mod q，H(m) 是消息的哈希值，n 是椭圆曲线的阶，(r,s)就为签名。

常见题型：
1.随机数k的复用：
使用两次相同的k，我们可以通过方程求解私钥即上述攻击
代码实现:

1
2
3
4
5
6
7
from Crypto.Util.number import inverse

def recover_private_key(h1, s1, h2, s2, r, n):
    numerator = (h1 * s2 - h2 * s1) % n
    denominator = (r * (s1 - s2)) % n
    d = (numerator * inverse(denominator, n)) % n
    return d

2.弱椭圆曲线参数
使用非标准或者低阶椭圆曲线，使得ECDLP可以求解,或者使用异常曲线(Smart曲线，阶等于域大小p)
方法：使用Pohlig-Hellman算法分解阶数n的素因子，简化离散对数计算
1.分解曲线阶n的素因子;n=p1^e1^·p2^e2^…
2.对每个子群pi^ei^求解d mod pi^ei^
3，用中国剩余定理合并得到完整的d

1
2
3
4
5
6
7
8
9
10
11
E = EllipticCurve(GF(p), [a, b])  # 定义椭圆曲线
Q = E(x_q, y_q)                   # 公钥点
factors = factor(n)               # 分解阶n
dlogs = []
for pi, ei in factors:
    ki = n // (pi^ei)
    Pi = ki * G                   # 子群基点
    Qi = ki * Q                   # 子群公钥
    dlog = discrete_log(Qi, Pi, operation='+')
    dlogs.append(dlog)
d = crt(dlogs, [pi^ei for pi, ei in factors])

3.签名伪造
未验证公钥是否在曲线上：攻击者可提交不在曲线上的恶意公钥。
未检查签名参数范围：如允许r=0或s=0
我们可以构造公钥Q不在原曲线但满足验证公式
例如：Q=(r^-1^·h)·G+(r^-1^·s)·Q
生成签名(r,s)后，再构造新签名(r,-s mod n),由于椭圆曲线对称点x横坐标相同，所以新签名也有效

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from ecdsa import SigningKey, SECP256k1
from hashlib import sha256

# 假设原系统使用SECP256k1曲线，但未验证公钥在曲线上
curve = SECP256k1
n = curve.order

# 攻击者构造恶意公钥和签名
def forge_signature(target_message):
    # 1. 生成随机k（无需知道私钥）
    k = 123456  # 任意随机数
    G = curve.generator
    point_kG = k * G
    r = point_kG.x() % n

    # 2. 计算哈希值
    h = int(sha256(target_message).hexdigest(), 16)

    # 3. 构造s值（任意值，例如s=1）
    s = 1

    # 4. 构造公钥Q'，使其满足验证公式
    w = pow(s, -1, n)
    u1 = (h * w) % n
    u2 = (r * w) % n
    Q_fake = (u1 * G + u2 * (-G))  # 选择-Q_fake为基点G的对称点

    # 5. 提交伪造的签名(r, s)和公钥Q_fake
    return (r, s), Q_fake

# 验证伪造的签名（系统未检查Q_fake是否在曲线上）
(r_fake, s_fake), Q_fake = forge_signature(b"flag")
print(f"伪造的签名: (r={r_fake}, s={s_fake})")
print(f"恶意公钥坐标: ({Q_fake.x()}, {Q_fake.y()})")

4.已知部分k
若已经k的高位或低位，或者k与时间有关可以用时间戳
用LLL算法，可以恢复完整的k
例如：假如给出k的低8bit,(k=已知部分+x)
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#公式 k = k_low + 2^t * x
t = 8
k_low = ...  # 已知的低t比特
h = ...      # 哈希值
r = ...      # 签名中的r
s = ...      # 签名中的s
n = ...      # 曲线阶

# 构建格矩阵
M = matrix(ZZ, [
    [2^t, 0, 0],
    [0, n, 0],
    [k_low, r, n//2^t]
])
M = M.LLL()
for row in M:
    if abs(row[2]) == n//2^t:
        k_candidate = row[0] + k_low
        d = (s * k_candidate - h) * inverse(r, n) % n
        break

5.Ocacle攻击
签名Oracle：允许提交任意消息获取签名。
攻击方法：通过多次交互获取足够信息，构造私钥。
这种题目一般为远程题。提供在线签名服务，我们需要提交特定构造的信息，如哈希可控的消息，收集多个签名，再分析是否存在k复用或者k有线性关系的情况，恢复私钥

6.特殊曲线攻击(如NIST P-256)
后门曲线：某些标准曲线参数可能隐藏数学弱点。
攻击方法：利用特定数学性质（如移动点攻击）。

≡