本文将解释 ECDSA（Elliptic Curve Digital Signature Algorithm，椭圆曲线数字签名算法）是如何工作的，以及它为什么有效。

在本教程中，我们将从第一性原理出发，逐步“重新发现”该算法。

先决条件

我们假定您已具备以下背景知识：

• Elliptic Curve Arithmetic
• Elliptic Curve Arithmetic in Finite Fields

数字签名回顾

数字签名算法是一种协议，它使用户能够对字符串提供加密的认可印记。

这样的用户拥有一个 public key（公钥，对应于椭圆曲线点的一对 $(x,y)$）。该点是由一个 private key（私钥）生成的，私钥是一个秘密的标量值。

给定公钥、消息和 signature（签名），另一个用户可以验证该签名是由拥有该公钥对应私钥的人生成的，并且只有该人才能生成该签名。

例如，加密货币使用数字签名来验证用户确实想要进行交易。用户 Alice 可以向区块链发送一条消息，说“发送我的 10 个代币给 Bob”。区块链网络必须确定 Alice 确实对该消息给予了认可印记，并且 Bob 没有窃取 Alice 的代币。

生成的签名必须是专属于该消息的，而不能被其他消息接受。否则，攻击者可能会利用签名让受害者批准恶意交易。如果“转账 10 个代币给 Bob”这条消息的签名也能被用作对“转账 10 个代币给 Eve”这条消息的认可印记，那么 Eve 就可以利用 Bob 转账的签名来窃取 Alice 的代币。

我们将生成签名的人称为 prover（证明者）或 signer（签名者），将测试 (公钥, 消息, 签名) 元组是否有效的人称为 verifier（验证者）。

从本质上讲，椭圆曲线数字签名是对私钥知识的证明。具体来说，它是对椭圆曲线点的离散对数知识的证明。

对于那些已经见过 ECDSA 算法的读者：

如果你不知道这些公式是怎么来的，你将会学到推导它们背后的思路。

术语和符号

我们用大写字母（如 $Q$）来表示椭圆曲线点。生成元将被称为 $G$。$G$ 的值对所有相关方都是已知的。标量和点之间的乘法写成 $aG$，这意味着将 $G$ 与自身相加 $a$ 次。

给定两点 $P$ 和 $Q$，如果某人知道 $x$ 使得 $xP = Q$，或者知道 $y$ 使得 $P = yQ$，我们称他们知道 $P$ 和 $Q$ 之间的离散对数关系（discrete log relationship）。

如果某人知道一个标量 $q$ 使得 $Q = qG$，我们称他们知道点 $Q$ 的离散对数。

除非另有说明，我们用相同字母的小写形式来表示某个点的离散对数。

所有算术运算都是在一个 finite field 中进行的，但为了简洁起见，我们省略了 $\pmod p$ 符号。

失败的数字签名尝试

朴素方法：泄露私钥

我们想证明我们知道公钥 $P$ 的私钥 $p$，其中 $P = pG$。

最朴素的方法是将私钥 $p$ 泄露给验证者，以便验证者可以检查确实存在 $P = pG$。

当然，这违背了对 $p$ 保密的初衷。

证明知道 $P$ 和 $Q$ 之间的离散对数关系

证明我们知道 $p$，等价于证明我们知道生成元 $G$ 和公钥 $P$ 之间的离散对数关系。也就是说，$G$ 与自身相加 $p$ 次得到 $P$。泄露 $G$ 和 $P$ 之间的离散对数关系就会泄露私钥。

因此，我们可以不证明我们知道生成元 $G$ 和公钥 $P$ 之间的离散对数关系，而是证明我们知道 $P$ 和 $Q$ 之间的离散对数关系，其中 $Q$ 由证明者选择，且它的离散对数 $q$ 对验证者来说是未知的。如果验证者不知道 $Q$ 的离散对数，那么给定 $P$ 和 $Q$ 之间的离散对数关系，验证者也无法推导出私钥。

设 $s$ 为 $P$ 需要与自身相加多少次才能产生 $Q$；换句话说，$sP = Q$。如果证明者分别知道 $P$ 和 $Q$ 的离散对数为 $p$ 和 $q$，他们可以轻松计算出 $s = q/p$。

$s = q/p$ 的推导如下：

然后验证者可以检查确实有 $Q = sP$，这就表明证明者知道 $P$ 和 $Q$ 之间的离散对数关系。

然而，这种方法失败了，因为恶意的证明者可以拿走别人的 $P$（他们不知道其私钥），选择一个随机值 $s$，计算 $Q = sP$，然后将 $(P, Q, s)$ 发送给验证者。

因此，证明者证明他们知道 $P$ 和 $Q$ 之间的离散对数关系，并不足以证明他们知道 $P$ 本身的离散对数。它仅仅表明他们将某个 $P$ 乘以 $s$ 从而生成了 $Q$。

防止随机选择的 $Q$

上面的方法失败是因为证明者可以在实际上不知道 $Q$ 本身离散对数的情况下提供 $Q$。

如果为了确保证明者知道 $Q$ 的离散对数，证明者向验证者泄露 $q$（即 $Q$ 的离散对数）会怎样？

在这种情况下，证明者必须将 $q$ 和 $s$ 都泄露给验证者。然后，$s$ 证明了证明者知道需要将 $P$ 与自身相加多少次才能得到 $Q$，而 $q$ 证明了证明者知道 $Q$ 的离散对数。提供 $q$ 证明了 $Q$ 不是通过任意选择一个值 $s$ 并将 $P$ 与自身相加 $s$ 次来选定的。

在这种情况下，验证者检查：

有了这些检查，证明者在不知道 $Q$ 的离散对数和 $P$ 的离散对数的情况下，就无法创建或生成有效的关系。

然而，验证者可以基于这些信息计算出私钥。

所以我们陷入了困境：如果我们泄露 $Q$ 的离散对数，验证者就能计算出私钥。如果证明者可以随意选择 $Q$，那么证明者就可以为他们不知道离散对数的公钥创建签名。

我们绝不能让验证者能够计算出私钥，所以泄露 $q$ 是绝对不行的。

因此，我们的解决方案必须包含由证明者挑选 $Q$ 的环节——但我们必须防止证明者能够完全任意地挑选 $Q$（例如通过选择任意的 $s$ 并生成 $Q = sP$）。

继续往下看，证明者必须证明他们知道 $Q$ 的离散对数和 $P$ 的离散对数，但又不能泄露任何一个离散对数 $p$ 或 $q$。

事实证明，证明我们知道两个点的离散对数而不泄露它们，比证明我们知道一个点的离散对数而不泄露这单一的离散对数要容易得多。

如果证明者知道 $P$ 和 $Q$ 的离散对数，那么他们还必须知道什么？

核心思想是这样的：

如果证明者知道 $P$ 和 $Q$ 的离散对数，那么他们不仅必须知道满足 $sP = Q$ 的 $s$，还必须知道满足 $s'(hG + P) = Q$ 的 $s'$，其中 $h$ 是由验证者选择的任意值，且是证明者无法预测的值。

换句话说，我们将开始在 $P$ 和 $Q$ 之间的关系中引入加法和乘法“偏移”（shifts）——如果证明者知道 $P$ 和 $Q$ 的离散对数，那么只要证明者知道偏移量 $h$ 是多少，他们就必须能够计算出 $s'$ 使得 $s'(hG + P) = Q$。

加法偏移可防止伪造

为了防止证明者选择的 $Q$ 只是 $P$ 的简单标量乘法，验证者可以注入一个加法偏移 $h$。

在证明者将 $P$ 和 $Q$ 发送给验证者之后，验证者回复 $h$（一个公开的标量值）。证明者必须随后提供 $s$ 使得 $Q = s(hG + P)$（我们不再需要 $s'$ 符号了）。

现在证明者无法控制 $P$ 和 $Q$ 之间的离散对数关系，他们必须改为证明自己知道 $(hG + P)$ 和 $Q$ 之间的离散对数关系。

由于验证者已经拥有了 $P$ 和 $Q$，证明者不能仅仅挑选一个随机的 $s$ 并生成满足 $Q = s(hG + P)$ 的 $Q$。证明者必须证明他们知道新点 $(hG + P)$ 和原始 $Q$ 之间的离散对数关系。

如果证明者知道 $P$ 和 $Q$ 的离散对数，那么很容易计算出 $s$ 为：

具体来说，证明者解出了：

让我们总结一下刚刚创建的交互式算法：

1. 我们假设双方都同意使用 $G$（及其所属的椭圆曲线群）。
2. 证明者发布他们的公钥 $P$ 并希望证明自己知道私钥 $p$。
3. 验证者以一个标量 $h$ 作为响应。
4. 证明者挑选一个随机的 $q$ 并计算 $Q = qG$。
5. 证明者计算 $s = q(h + p)^{-1}$ 并将 $(s, Q)$ 发送给验证者。
6. 验证者检查 $Q \stackrel{?}= s(hG + P)$。

最后一步的检查之所以有效，是因为在底层运算中，$s$ 抵消了 $h$ 和 $p$ 的离散对数：

抵御伪造签名

让我们看看恶意的证明者将如何试图在不知道 $P$ 和 $Q$ 离散对数的情况下去计算 $s$，并看看为什么这种尝试会失败。

证明者捏造了一个值 $\tilde{q}$ 并生成 $Q = \tilde{q}P$，然后将 $Q$ 发送给验证者。设 $\tilde{q}$ 是由恶意证明者捏造的值，而不是 $Q$ 的离散对数。

验证者回复标量 $h$。

恶意的证明者现在必须求解方程式：

由于证明者知道 $Q = \tilde{q}P$（但不知道 $p$），他们可以尝试两种代入方式：

• $Q = \tilde{q}P$
• $P = \tilde{q}^{-1}Q$

然而，无论证明者代入的是 $Q$ 还是 $P$，他们都会遇到一个问题：由于不知道 $P$ 的离散对数，他们无法解出 $s$。

代入 $Q$

在这里，证明者代入 $Q$：

我们不能对椭圆曲线点进行除法运算，因此为了计算上述分数，我们需要知道 $p$：

但是证明者不知道 $p$，所以他们无法计算 $s$。

代入 $P$

现在恶意证明者尝试代入 $P$ 而不是 $Q$，但又遇到了由于不知道 $Q$ 离散对数而产生的问题：

现在恶意证明者需要知道 $Q$ 的离散对数才能计算上述公式。然而，证明者不知道 $Q$ 的离散对数，他们只知道它是 $\tilde{q}P$，但不知道 $p$。因此，恶意证明者无法生成 $s$。

为什么偏移必须是加法

我们怎么知道要对 $P$ 加上 $hG$，而不是乘以 $hP$ 并要求证明者得出 $s$ 使得 $Q = hsP$ 呢？

问题在于，如果使用乘法偏移，证明者就能抵消掉 $Q$ 和 $P$ 的离散对数因子。

回顾一下：恶意的证明者不知道 $Q$ 的离散对数 $q$，也不知道 $P$ 的离散对数 $p$。然而，他们确实知道 $Q$ 比 $P$ 大 $\tilde{q}$ 倍，其中 $\tilde{q}$ 是他们捏造的数字，并非真实的离散对数 $q$。

如果验证者给出了 $h$，并要求证明者算出一个 $s$ 使得 $Q = shP$，那么证明者只需计算 $s = \tilde{q}/h$。

这将通过验证者的测试：

因此，协议中必须包含加法偏移，以便在第一个点 ($P + hG$) 和第二个点 $Q$ 之间不存在简单的乘法关系 $sh$。

让我们的协议变为非交互式

不幸的是，我们的解决方案要求验证者在接收到 $P$ 和 $Q$ 之后发送 $h$，这要求证明者和验证者彼此进行交互。

如果我们想让我们的协议变成非交互式，那么 $h$ 就不能来自验证者，必须由证明者来生成它。

如果证明者事先知道 $h$（如果证明是非交互式的，这是必然的），那么我们又回到了最初的问题。

在这种情况下，恶意证明者可以随机挑选 $h$，然后随机挑选 $s$，并计算

然后将 $(P, Q, s, h)$ 发送给验证者。验证者不知道 $Q$ 是否是由一个随机的 $s$ 生成的。

为了避免由证明者选择 $h$ 以及与验证者的交互，我们可以通过对 $Q$ 进行哈希运算来模拟验证者选择 $h$ 的过程：

既然验证者反正也是随机挑选 $h$ 的，证明者完全可以使用哈希函数以伪随机的方式计算出 $h$。这种技术被称为 Fiat-Shamir Transform。

一个对私钥知识的有效证明

算法如下：

1. 证明者挑选一个随机标量 $q$ 并计算 $Q = qG$。
2. 证明者计算 $h = \mathsf{hash}(Q)$。
3. 证明者计算 $s = \frac{q}{h + p}$。
4. 证明者将 $(P, Q, s, h)$ 发送给验证者。
5. 验证者计算 $h = \mathsf{hash}(Q)$。
6. 验证者检查 $Q = s(hG + P)$。

这之所以是安全的，是因为恶意的证明者在不知道 $Q$ 的离散对数和 $P$ 的离散对数的情况下，无法执行第 3 步。

伪造是不可能的

假设恶意证明者挑选了 $\tilde{q}$ 并生成 $Q = \tilde{q}G$。在这里，证明者知道 $Q$ 的离散对数，但不知道 $P$ 的离散对数。在对 $Q$ 进行哈希得到 $h$ 之后，恶意证明者需要计算出满足 $Q = s(hG + P)$ 的 $s$。然而，他们做不到这一点，因为他们不知道 $(hG + P)$ 的离散对数，毕竟 $P$ 的离散对数对他们来说是未知的。

至此，我们已经展示了一种安全的算法，用于在不泄露私钥的情况下证明对私钥知识的掌握。

ECDSA 的前置算法

我们上面介绍的算法仅仅证明了对私钥知识的掌握，它不允许签名者对一条消息进行签名。

在 ECDSA 中，签名是一种证明，证明我们知道某个点的离散对数，该点是通过将我们的公钥加上 $hG$ 生成的，其中 $h$ 是消息的哈希值与另一点 $Q$ 的离散对数。

然而，目前的设计引入了一个安全漏洞，因为证明者可以首先计算 $h = \mathsf{hash}(\text{message})$，然后挑选一个随机的 $s'$ 并计算 $Q = s'(hG + P)$。此时 $Q$ 再次完全受证明者控制，所以我们无法相信证明者真的知道离散对数 $q$。

为了确保安全，我们再次需要引入一些不受证明者控制的额外的伪随机性。

添加随机性 $r$

设 $r$ 是从对 $Q$ 进行哈希推导出的随机值。如果我们按照如下方式将 $r$ 乘上 $P$，我们就能得到一个安全的数字签名算法。起初，这看起来像是制造了一个循环依赖，但这实际上是让算法变得安全的核心所在。证明者证明他们知道 $(rP + hG)$ 和 $Q$ 离散对数的算法如下：

1. 证明者随机挑选一个 $p$，并将其公钥 $P$ 作为 $P = pG$ 发布。
2. 证明者挑选一个随机标量 $q$ 并计算 $Q = qG$。
3. 证明者挑选一个消息字符串 $\text{message}$ 并计算 $h = \mathsf{hash}(\text{message})$。
4. 证明者计算 $r = \mathsf{hash}(Q)$。
5. 证明者计算 $s = q\cdot(h + rp)^{-1}$。
6. 证明者将 $(\text{message}, Q, s)$ 发送给验证者。
7. 验证者计算 $r' = \mathsf{hash}(Q)$。
8. 验证者计算 $h = \mathsf{hash}(\text{message})$。
9. 验证者检查 $Q \stackrel{?}= s(hG + r'P)$。

尽管证明者可以挑选任意的 $h$，但他们无法控制点 $(hG + rP)$ 的离散对数，因为 $r$ 是通过哈希 $Q$ 生成的。因此，为了计算出 $s$，也就是 $Q$ 和 $(hG + rP)$ 之间的离散对数关系，证明者必须真实地知道 $P$ 的离散对数 $p$。

优化 ECDSA 前置算法

优化 1：哈希 $Q$ 是不必要的，因为椭圆曲线乘法本身表现得就像一个哈希函数

让我们回想一下 $r = \mathsf{hash}(Q)$ 试图达成的目的。最终的验证公式是：

核心思想是我们希望 $r$ 依赖于 $Q$，这样 $Q$ 就不会完全由证明者可完全控制的值 $s$ 决定。为了计算 $s$，证明者必须知道 $P$ 的离散对数。

我们需要寻找一种比哈希更廉价的替代方案来让 $r$ 依赖于 $Q$。

考虑到如果 $r$ 依赖于 $Q$，那么它也依赖于 $Q$ 的离散对数 $q$，因为 $q$ 完全决定了 $Q$。

现在想想看，如果给定我们一个标量值 $a$，由 $A = aG$ 产生的椭圆曲线点 $A$ 看起来是随机的。$A$ 和 $a$ 之间没有明显的关系。这种明显关系的缺失正是计算离散对数困难的原因所在。

哈希函数的输出同样看起来也是随机的：哈希的输入和输出之间没有明显的关系。

因此，我们可以像处理 $\mathsf{hash}(q)$ 一样来处理 $Q = qG$。也就是说，$Q$ 本身表现得就像哈希的输出。然而，我们不能直接设定 $r = Q$，因为它们类型不同。相反，我们只需取 $Q$ 的 $x$ 值并让它成为 $r$（记住，$Q$ 是一个 $(x, y)$ 点）。

现在 $r$ 本质上就是 $q$ 的哈希，且因为 $Q$ 直接依赖于 $q$，$r$ 表现得就像是 $Q$ 的哈希。

因此，我们不计算 $r = \mathsf{hash}(Q)$，而是设定 $r = Q.x$（意味着取点 $Q$ 的 $x$ 值）。

优化 2：我们不需要发送整个点 $Q$，只需要发送 $Q$ 的 $x$ 值

椭圆曲线点由两个标量组成：点的 $x$ 和 $y$ 值。每一个 $x$ 值只对应两个可能的 $y$ 值，即 $\sqrt{x^3 + b} \mod p$ 的解。

因此，没有必要发送 $Q$，只需发送 $r$，因为 $r$ 就是 $Q$ 的 $x$ 值。

完整的 ECDSA 算法：分步指南

我们现在展示标准的 ECDSA 算法，并附上最常用的符号表达。我们会指出我们之前使用的符号在哪里存在差异。

1. 证明者随机挑选一个 $p$，并将其公钥 $P$ 作为 $P = pG$ 发布。
2. 证明者挑选一条他们想要签名的消息，并对其进行哈希处理得到 $h = \mathsf{hash}(\text{message})$。
3. 证明者挑选一个随机标量 $k$（也就是我们之前一直称作的 $q$，但文献中称之为 $k$）并计算 $R = kG$。同样地，我们之前称之为 $Q$ 的点，文献中称之为 $R$。只有 $R$ 的 $x$ 值会被保留，记作 $r = R.x$。
4. 证明者为 $R = s^{-1}(hG + rP)$ 计算 $s$，公式如下：

注意，$s$ 与我们先前的实现相比是“倒置”（inverted）的。在实际的 ECDSA 算法中，证明者计算 $s^{-1}$，而验证者稍后会对 $s$ 求逆，正如我们将看到的那样。

5. 签名者将 $(P, h, r, s)$ 发送给验证者。
6. 验证者计算 $R' = s^{-1}(hG + rP)$ 并检查 $R'$ 的 $x$ 值是否等于 $r$。

该公式在底层的运算逻辑如下：

这产生了相同的点 $R$，因此 $r$ 将与计算出的点 $s^{-1}(hG + rP)$ 的 $x$ 值相匹配。

给定签名推导公钥

以太坊和比特币区块链并不在给定公钥、消息和签名的情况下验证签名。相反，给定消息和签名，它们会求解出公钥，并检查该公钥是否与预期公钥相匹配。

要了解这是如何运作的，我们可以对验证公式做一些代数运算，从而在给定签名和消息哈希的情况下推导出公钥。

然而，仅凭 $(\text{message}, r, s)$ 是不够的，因为 $r$ 对应于两个可能的点，这源于 $r = R.x$ 存在两个 $y$ 值。为了消除歧义，签名者还需要发送一个布尔变量来指明使用了哪个 $y$ 值。发送完整的 $y$ 值会占用更多空间。

给定签名“恢复”公钥的 ECDSA 算法如下：

1. 证明者将其公钥 $P$ 作为 $P = pG$ 发布。
2. 证明者挑选一条他们想要签名的消息 $\text{message}$，并对其进行哈希处理得到 $h = \mathsf{hash}(\text{message})$。
3. 证明者挑选一个随机标量 $k$ 并计算 $R = kG$。
4. 证明者计算 $h = \mathsf{hash}(\text{message})$。
5. 证明者在 $R = s^{-1}(hG + rP)$ 中求解 $s$，公式为 $s = \frac{h + rp}{k}$。
6. 签名者向验证者发送 $(\text{message}, r, s, v)$，其中 $v$ 是一个布尔值，用于指示使用了 $r$ 的哪个 $y$ 值。
7. 验证者根据 $v$ 和 $r$ 推导出 $R$。
8. 验证者推导出公钥 $P$，公式为：

如果计算出的 $P$ 与证明者发布的公钥 $P$ 相匹配，则接受该签名。

滥用 ECDSA 的潜在漏洞

ECDSA 中的延展性

给定签名 $(\text{message}, r, s, v)$，攻击者可以计算出第二个签名 $(\text{message}, r, s', v')$，使得 $v \neq v'$ 且 $s \neq s'$，而它依然能恢复出相同的公钥 $P$。

攻击者只需计算 $s$ 的加法逆元 $s' = s^{-1}$ 并翻转 $v$ 的值，使得 $R$ 变为其加法逆元。本质上，我们将 $s$ 替换为 $-s$，将 $R$ 替换为 $-R$。由于这两个值乘在一起，-1 会相互抵消，所以恢复出来的公钥是一样的：

为了防止这种攻击，验证者不应接受同一消息曾出现过的不同签名。更通用、更稳健的解决方案是使用 nonce，即证明者必须包含在消息中的一个不断递增的数字。nonce（代表“number used once”，即只使用一次的数字）充当每个签名的唯一标识符。通过要求证明者在每个签名中合并一个全新且更大的 nonce，验证者可以轻松检测并拒绝重用或修改过往签名的尝试。

如果验证者未对消息进行哈希处理，就可以创建伪造证明。

让我们考虑一种情况：攻击者可以创建一个我们不知道离散对数的值 $R$，但我们知道它的组成部分。例如，攻击者挑选随机值 $a$ 和 $b$ 并计算 $R = aG + bP$，以及 $r = R.x$。

然后，攻击者计算 $s = r/b$ 和 $h = ar / b$。

我们可以通过将伪造的 $s$ 和 $h$ 值代入验证公式，来看看这种攻击是如何运作的：

防御这种攻击的方法很简单：$h$ 必须是验证者对消息进行哈希运算的结果。当一条消息被哈希时，哈希值恰好等于 $ar/b$ 的可能性微乎其微。

总结

ECDSA 算法是一种对离散对数关系的知识证明，这种关系存在于任意点 $R$ 和一个特定的点之间，后者代表了消息哈希乘上生成元再加上公钥，同时公钥还乘上了签名者无法控制的伪随机值。

具体来说，它是对 $R$ 和 $(hG + rP)$ 之间离散对数关系的知识证明。

尽管签名者可以任意挑选 $R$，但他们无法控制点 $(hG + rP)$ 的离散对数，因为 $r$ 伪随机地依赖于 $R$。签名者能够在 $R = s(hG + rP)$ 中计算出 $s$ 的唯一途径，是他们实际上确实知道 $P$ 的离散对数，即私钥。

鸣谢

在撰写本文的过程中，我们参考了以下资源：

• https://cryptobook.nakov.com/digital-signatures/ecdsa-sign-verify-messages
• https://jimmysong.medium.com/faketoshis-nonsense-signature-8700a44536b5