椭圆曲线数字签名算法（ECDSA）中的随机数k的重要性与重复使用的危害

题目描述
在椭圆曲线数字签名算法（ECDSA）中，签名过程需要生成一个临时随机数k（称为nonce）。若k被重复使用或预测，会导致私钥泄露。本题要求分析k的作用，并解释重复使用k如何破坏ECDSA的安全性。

解题过程

1. ECDSA签名基础

   • 设椭圆曲线参数为（G, n），其中G是基点，n是G的阶。
   • 私钥d为[1, n-1]内的随机整数，公钥Q = dG。
   • 对消息m的签名过程：
     a. 计算哈希值h = Hash(m)，截断为模n的整数。
     b. 生成随机数k ∈ [1, n-1]。
     c. 计算点R = kG，取R的x坐标r = x_R mod n（若r=0则重新选k）。
     d. 计算s = k⁻¹(h + dr) mod n（若s=0则重新选k）。
     e. 签名结果为(r, s)。

2. k的作用与安全性要求

   • k的作用是隐藏私钥d：在计算s时，d被k盲化（k⁻¹(dr)项），且每次签名需唯一k。
   • 安全要求：k必须不可预测、一次性使用。若攻击者获知k，可从s = k⁻¹(h + dr)反推私钥d = (sk - h)r⁻¹ mod n。

3. 重复使用k的攻击场景

   • 假设同一k被用于两个不同消息m₁和m₂，签名分别为(r, s₁)和(r, s₂)。
     • 由于k相同，点R = kG相同，故r值相同。
     • 两签名的s值满足：
       s₁ = k⁻¹(h₁ + dr) mod n
       s₂ = k⁻¹(h₂ + dr) mod n
     • 联立方程，消去d：
       s₁ - s₂ = k⁻¹(h₁ - h₂) mod n
       → k = (h₁ - h₂)(s₁ - s₂)⁻¹ mod n
     • 解得k后，代入s₁公式即可求出d = (s₁k - h₁)r⁻¹ mod n。

4. 实例验证

   • 假设n=23，G=(13,7)，d=7，Q=7G=(19,20)。
   • 对m₁（h₁=5）和m₂（h₂=8）重复使用k=3：
     • 签名1：R=3G=(17,20)，r=17，s₁=3⁻¹(5+7×17) mod 23=18。
     • 签名2：s₂=3⁻¹(8+7×17) mod 23=12。
     • 攻击计算：k=(5-8)(18-12)⁻¹ mod 23=(-3)×6⁻¹ mod 23=20×4=3（正确）。
     • 私钥d=(18×3-5)×17⁻¹ mod 23=49×19 mod 23=7（正确）。

5. 防护措施

   • 使用密码学安全的随机数生成器（如硬件RNG）。
   • 遵循RFC 6979，采用确定性ECDSA：通过哈希函数（如HMAC）基于私钥和消息生成k，避免随机性缺陷。
   • 严格校验k的唯一性（如通过缓存检测）。

总结
k的随机性和唯一性是ECDSA安全的基石。重复使用k会直接导致私钥泄露，实际应用中需通过可靠随机源或确定性方法确保k的安全生成。