ECDSA随机数

摘要

在ECDSA过程中，需要一个随机数（也可能是确定性的不重复的哈希）来对消息签名。

如果你对不同的消息使用了同一个随机数，则私钥会暴露。

以下为几步简化的ECDSA过程:

Q_A=d_A*G \\ \text{G为曲线的生成元}

s = k^{-1}(h+rd_A)(\bmod \,n)

这样就得到了签名(r,s).

s_1=s^{-1}(\bmod \,n)

R' = (hs_1) \times G + (r s_1) \times Q_A

显然，如果我们对不同的消息M使用了相同的k（也意味着r相同），可以通过下列几步解出私钥：

\begin{cases} s = k^{-1}(h+rd_A)(\bmod \,n) \\ s' = k^{-1}(h'+rd_A)(\bmod \,n) \end{cases} \\ \implies \\ \begin{cases} k = (h-h')(S-S')^{-1} \\ d_A = (sk-h)r^{-1} \end{cases}

最后更新于2年前

密码学背景

以下为几步简化的ECDSA过程:

密钥生成

私钥 d_A，由RNG生成的随机数

公钥 Q_A:

Q_A=d_A*G \\ \text{G为曲线的生成元}

签名

计算消息M的哈希值h = hash(M)

生成随机数k

计算随机点R = kG

将点R的横坐标R.x记为r, 然后计算s

s = k^{-1}(h+rd_A)(\bmod \,n)

这样就得到了签名(r,s).

验证签名

计算消息M的哈希值h = hash(M)

计算其逆

s_1=s^{-1}(\bmod \,n)

恢复在签名时使用的随机点

R' = (hs_1) \times G + (r s_1) \times Q_A

检查是否有R'.x == r

攻击细节

显然，如果我们对不同的消息M使用了相同的k（也意味着r相同），可以通过下列几步解出私钥：

\begin{cases} s = k^{-1}(h+rd_A)(\bmod \,n) \\ s' = k^{-1}(h'+rd_A)(\bmod \,n) \end{cases} \\ \implies \\ \begin{cases} k = (h-h')(S-S')^{-1} \\ d_A = (sk-h)r^{-1} \end{cases}