DSA基础入门

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

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

ECDSA的特殊性

ECDSA与DSA的核心区别在于使用椭圆曲线群而非乘法群：

• 公钥y=gˣ变为椭圆曲线点
• r值取椭圆曲线点gᵏ的x坐标
• 验证时计算椭圆曲线点(gᴴ⁽ᵐ⁾yʳ)ˢ⁻¹的x坐标

非ce重用导致密钥泄露

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

1. 通过s₁-s₂ = k⁻¹(H(m₁)-H(m₂))可解出k
2. 代入x = r⁻¹(ks-H(m))即可恢复私钥

# 攻击示例代码
k = (s1 - s2)^-1 * (H(m1) - H(m2)) % q
x = (s1*k - H(m1)) * pow(r, -1, q) % q

非ce部分泄露攻击

即使仅泄露少量nonce比特，也能通过格攻击恢复密钥：

• Howgrave-Graham和Smart：3比特泄露即可攻破160-bit DSA
• Nguyen和Shparlinski：扩展至ECDSA
• LadderLeak攻击：仅需<1比特泄露

# 格攻击矩阵构造示例
matrix = [
    [order, 0, 0, 0],
    [0, order, 0, 0],
    [r1*s1_inv, r2*s2_inv, 2^128/order, 0],
    [msg1*s1_inv, msg2*s2_inv, 0, 2^128]
]

YubiKey真实漏洞利用

当nonce存在80比特固定前缀时：

1. 构造差值矩阵消除未知固定值
2. 通过LLL算法获取nonce差值
3. 代数推导恢复私钥：

x = (rn*s1 - r1*sn)^-1 * (sn*m1 - s1*mn - s1*sn*(k1-kn)) % order

防护建议

1. 首选EdDSA：内置安全nonce生成
2. 恒定时间实现：防止时序侧信道
3. RFC 6979：确定性nonce生成标准
4. 盲签名技术：隐藏算术操作

攻击所需签名数量与nonce泄露比特数的关系：

本文证明ECDSA的安全性极度依赖nonce的随机性，任何微小的偏差都可能导致整个签名体系崩溃。
更多精彩内容 请关注我的个人公众号 公众号（办公AI智能小助手）
公众号二维码