跳转至

ECDSA

ECDSA 是一个基于椭圆曲线的签名算法,使用时需要确定一个椭圆曲线,以及它的 base point G,且 G 的阶是素数 n

本文主要参考了 ECDSA - Wikipedia

生成 key pair

生成 key pair 的时候,私钥是整数 dA[1,n1],那么公钥就是圆锥曲线上一点 QA=dA×G,这里 × 表示整数与圆锥曲线上一点的乘法。

签名

签名的时候,对于给定的消息 m,签名流程如下:

  1. 计算哈希:e=HASH(m),例如用 SHA 系列的哈希算法
  2. 考虑到 e 的位数可能比 n 的位数更多,取 e 的高位,使得位数和 n 一致,得到的结果记为 z
  3. 生成一个密码学安全的随机数 k[1,n1]
  4. 计算 k×G,取它的 X 坐标为 x1
  5. 计算 r=x1modn
  6. 计算 s=k1(z+rdA)modn
  7. 如果 r 或者 s 等于 0,取新的 k 再重试
  8. 得到的 ECDSA 签名就是 (r,s) 两个数

验证

验证签名的时候,已知 r,s,m,QA,按照下面的流程进行:

  1. 前两步和计算签名的算法一致,求哈希和截断后得到 z
  2. 计算 u1=zs1modn,u2=rs1modn
  3. 计算 u1×G+u2×QA,取它的 X 坐标为 x2
  4. 如果 rx2(modn),则签名合法

上面的过程忽略了一些边界情况的检查,详细版本见 Wikipedia。

下面进行验算:

u1×G+u2×QA=zs1×G+rs1×QA=zs1×G+rs1dA×G=(zs1+rs1dA)×G=(z+rdA)s1×G=(z+rdA)k(z+rdA)1×G=k×G

等式左边的 X 坐标等于等式右边的 X 坐标,等价于 rx2(modn),验算没问题。

公钥恢复

ECDSA 支持公钥恢复算法,已知 r,s,m,恢复 QA。首先进行推导:

QA=dA×Gs=k1(z+rdA)modnsk=z+rdAmodnsk×G=(z+rdA)×GrdA×G=(skz)×GQA=dA×G=r1(skz)×GQA=r1(s(k×G)z×G)

上式中 r,s 已知,z 可以从 m 通过哈希计算得出,k×G 的 X 坐标 x1 满足 r=x1modn,因此恢复过程就是:

  1. 在椭圆曲线上找到 X 坐标模 n 等于 r 的点,这个点就是 k×G
  2. 按照计算哈希的前两步,从 m 计算出 z
  3. 按照上述公式,计算出 QA

但是实际上第一步没有这么简单:首先同一个 X 坐标对应椭圆曲线上的两个点,其次 rx1 只是同余关系,可能二者之间差了一个倍数。因此实际在 BTC 或者 ETH 里使用的时候,还额外附加了一个参数 recid,范围是 0 到 3,对应 Y 坐标是正还是负,rx1 之间差 0 还是 n

// Source: https://github.com/ethereum/go-ethereum/blob/e1fe6bc8469c626afaa86b1dfb819737e980a574/crypto/secp256k1/libsecp256k1/src/modules/recovery/main_impl.h#L104-L112
if (recid & 2) {
    if (secp256k1_fe_cmp_var(&fx, &secp256k1_ecdsa_const_p_minus_order) >= 0) {
        return 0;
    }
    secp256k1_fe_add(&fx, &secp256k1_ecdsa_const_order_as_fe);
}
if (!secp256k1_ge_set_xo_var(&x, &fx, recid & 1)) {
    return 0;
}

参考:Crypto Magic: Recovering Alice’s Public Key From An ECDSA SignatureCan We Recover The Public Key from an ECDSA Signature?

DSA 公钥恢复

如果在 DSA 算法上尝试上面的公钥恢复流程,就会遇到困难:

g=h(p1)/qmodpy=gxmodpr=(gkmodp)modqs=(k1(H(m)+xr))modqskH(m)+xrmodqxrskH(m)modqxr1(skH(m))modqy=gxmodp=gr1(skH(m))+nqmodp,nZy=gr1skgr1H(m)+nqmodp

此时会发现无法从 r 推断出 gkmodp 的值,中间差了 q 的整数倍。后面的 gnqmodp 也无法计算。

更加完整的讨论可以见 Can we recover public key from DSA signatures as we can from ECDSA?

Nonce Reuse Attack

在生成 ECDSA 签名的时候,注意不能用固定的 nonce(k),否则会被攻击。假如攻击者用一对 ECDSA key pair 对不同的两个消息 m1m2 分别做了一次签名,并且采用了相同的 nonce,那么:

两次签名的 nonce k 相等,因此 x1 相等,r 也相等,只有 s 不同:

s1=k1(z1+rdA)modns2=k1(z2+rdA)modn

签名是公开信息,也就是说 rs1s2 是攻击者已知的。此外消息 m1m2 也是已知的,所以攻击者可以求出 z1z2。现在尝试求解 dA

s1=k1(z1+rdA)modns2=k1(z2+rdA)modnk=s11(z1+rdA)modnk=s21(z2+rdA)modns11(z1+rdA)=s21(z2+rdA)modn(s11s21)rdA=s21z2s11z1modndA=r1(s11s21)1(s21z2s11z1)modn

这样就把私钥 dA 求了出来。

评论