# ECDSA

ECDSA 是一个基于椭圆曲线的签名算法，使用时需要确定一个椭圆曲线，以及它的 base point \\(G\\)，且 \\(G\\) 的阶是素数 \\(n\\)。ECDSA 支持如下的操作：

1. 生成签名
2. 验证签名
3. 从签名和明文推导出公钥

本文的内容已经整合到[知识库](</kb/cryptography/ecdsa.html>)中。

本文参考了 [ECDSA - Wikipedia](<https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm>)。

## 生成 key pair

生成 key pair 的时候，私钥是整数 \\(d\_A \\in \[1, n-1\]\\)，那么公钥就是圆锥曲线上一点 \\(Q\_A = d\_A \\times G\\)，这里 \\(\\times\\) 表示整数与圆锥曲线上一点的乘法。

## 签名

签名的时候，对于给定的消息 \\(m\\)，签名流程如下：

1. 计算哈希：\\(e = \\mathrm{HASH}(m)\\)，例如用 SHA 系列的哈希算法
2. 考虑到 \\(e\\) 的位数可能比 \\(n\\) 的位数更多，取 \\(e\\) 的高位，使得位数和 \\(n\\) 一致，得到的结果记为 \\(z\\)
3. 生成一个密码学安全的随机数 \\(k \\in \[1, n-1\]\\)
4. 计算 \\(k \\times G\\)，取它的 X 坐标为 \\(x\_1\\)
5. 计算 \\(r = x\_1 \\bmod n\\)
6. 计算 \\(s = k^{-1}(z + r d\_A) \\bmod n\\)
7. 如果 \\(r\\) 或者 \\(s\\) 等于 0，取新的 \\(k\\) 再重试
8. 得到的 ECDSA 签名就是 \\((r, s)\\) 两个数

## 验证

验证签名的时候，已知 \\(r, s, m, Q\_A\\)，按照下面的流程进行：

1. 前两步和计算签名的算法一致，求哈希和截断后得到 \\(z\\)
2. 计算 \\(u\_1 = zs^{-1} \\bmod n, u\_2 = rs^{-1} \\bmod n\\)
3. 计算 \\(u\_1 \\times G + u\_2 \\times Q\_A\\)，取它的 X 坐标为 \\(x\_2\\)
4. 如果 \\(r \\equiv x\_2 \\pmod n\\)，则签名合法

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

下面进行验算：

\\\[\\begin{align} &amp; u\_1 \\times G + u\_2 \\times Q\_A \\\\\\ &amp;= zs^{-1} \\times G + rs^{-1} \\times Q\_A \\\\\\ &amp;= zs^{-1} \\times G + rs^{-1}d\_A \\times G \\\\\\ &amp;= (zs^{-1} + rs^{-1}d\_A) \\times G \\\\\\ &amp;= (z+rd\_A)s^{-1} \\times G \\\\\\ &amp;= (z+rd\_A)k(z+rd\_A)^{-1} \\times G \\\\\\ &amp;= k \\times G \\end{align}\\\]

等式左边的 X 坐标等于等式右边的 X 坐标，等价于 \\(r \\equiv x\_2 \\pmod n\\)，验算没问题。

## 公钥恢复

ECDSA 支持公钥恢复算法，已知 \\(r, s, m\\)，恢复 \\(Q\_A\\)。首先进行推导：

\\\[\\begin{align} Q\_A &amp;= d\_A \\times G \\\\\\ s &amp;= k^{-1}(z + rd\_A) \\bmod n \\\\\\ sk &amp;= z + rd\_A \\bmod n \\\\\\ sk \\times G &amp;= (z + rd\_A) \\times G \\\\\\ rd\_A \\times G &amp;= (sk - z) \\times G \\\\\\ Q\_A &amp;= d\_A \\times G = r^{-1}(sk-z) \\times G \\\\\\ Q\_A &amp;= r^{-1}(s(k \\times G) - z \\times G) \\end{align}\\\]

上式中 \\(r, s\\) 已知，\\(z\\) 可以从 \\(m\\) 通过哈希计算得出，\\(k \\times G\\) 的 X 坐标 \\(x\_1\\) 满足 \\(r = x\_1 \\bmod n\\)，因此恢复过程就是：

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

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

```c
// 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 Signature](<https://medium.com/asecuritysite-when-bob-met-alice/crypto-magic-recovering-alices-public-key-from-an-ecdsa-signature-e7193df8df6e>) 和 [Can We Recover The Public Key from an ECDSA Signature?](<https://medium.com/asecuritysite-when-bob-met-alice/can-we-recover-the-public-key-from-an-ecdsa-signature-7af4b56a8a0f>)