DSA基础

ECDSA是基于椭圆曲线数字签名算法(DSA)的变种。DSA包含三个核心算法：

1. 密钥生成：随机选择私钥x，计算公钥y = gˣ mod p
2. 签名：生成随机nonce k，计算r = (gᵏ mod p) mod q，s = k⁻¹(H(m) + xr) mod q
3. 验证：检查r = [(gᴴ⁽ᵐ⁾yʳ)ˢ⁻¹ mod p] mod q

ECDSA的致命弱点

1. Nonce重用攻击

若两个签名使用相同nonce k：

1
2

k = (s₁ - s₂)⁻¹(H(m₁) - H(m₂))
x = r⁻¹(ks - H(m))

2. 部分Nonce泄露攻击

• 仅需3比特泄露+100签名 → 攻破160-bit DSA
• 仅5比特泄露+4000签名 → 攻破384-bit ECDSA
• LadderLeak攻击：仅0.2比特泄露即可恢复密钥

3. RNG偏差攻击

• 256-bit ECDSA中仅4比特偏差 → 完全破解

实战攻击演示

基础攻击（已知128-bit nonce前缀）

1
2
3
4
5
6
7

matrix = [
    [order, 0, 0, 0],
    [0, order, 0, 0],
    [r₁s₁⁻¹, r₂s₂⁻¹, 2¹²⁸/order, 0],
    [m₁s₁⁻¹, m₂s₂⁻¹, 0, 2¹²⁸]
]
new_matrix = olll.reduction(matrix)

YubiKey漏洞利用（80-bit固定前缀）

构建6签名矩阵：

1
2
3

row.append((rᵢsᵢ⁻¹) - rₙsₙ⁻¹)
row2.append((mᵢsᵢ⁻¹) - mₙsₙ⁻¹)
x = (rₙs₁ - r₁sₙ)⁻¹(sₙm₁ - s₁mₙ - s₁sₙ(k₁-kₙ))

防护方案

1. 替代方案：优先使用EdDSA（如Ed25519）
2. 恒定时间实现：防止时序侧信道
3. RFC 6979：确定性nonce生成
4. 盲签名技术：隐藏时序信息

攻击签名数需求表

警告：即使仅1比特泄露，观察足够签名后系统仍可能被完全攻破。