ECDSA背后的直觉

椭圆曲线数字签名（ECDSA）的直觉

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

在本教程中，我们将逐步“重新发现”该算法。

先决条件

我们假设你具备以下基础知识

• 椭圆曲线算术
• 有限域中的椭圆曲线算术

数字签名回顾

数字签名算法是一种协议，使得用户能够为字符串提供加密的批准印章。

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

给定公钥、一条消息和一个签名，其他用户可以验证该签名确实是由拥有该公钥的私钥的人生成的，只有那个人才能生成该签名。

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

产生的签名必须特定于该消息，不能被接受为其他消息的签名。否则，攻击者可能会利用一个签名让受害者批准恶意交易。如果“转移10个币到Bob”的消息的签名也能作为“转移10个币到Eve”的消息的批准印章，那么Eve就可以使用来自Bob转移的签名从Alice那里盗取币。

我们将生成签名的人称为证明者或签名者，而测试（公钥、消息、签名）三元组是否有效的人称为验证者。

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

对于已经看过ECDSA算法的读者：

$$ \begin{align} r &= kG\\ s &= k^{-1}(h + rp)\\ r &\stackrel{?}= s^{-1}(hG + rP) \end{align} $$

但不知道这些公式是从哪里来的，你将学习它们是如何推导出来的思考过程。

术语和符号

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

给定两个点$P$和$Q$，我们称某人知道$P$和$Q$之间的离散对数关系，如果他们知道$x$使得$xP = Q$，或者另外一个值$y$使得$P = yQ$。

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

我们用同样字母的小写版本来表示某一点的离散对数，除非另有说明。

所有算术都是在有限域中进行的，但为了简洁起见，我们省略了 $\pmod p$ 表示法。

数字签名的失败尝试

天真的方法：公开私钥

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

天真的方法是向验证者公开私钥$p$，这样验证者可以检查确实$P = pG$。

当然，这违背了保密$p$的目的。

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

证明我们知道$p$等同于证明我们知道生成器$G$和公钥$P$之间的离散对数关系。也就是说，$G$加到自身$p$次得到$P$。公开$G$和$P$之间的离散对数关系实际上揭露了私钥。

因此，我们可以证明我们知道$P$和$Q$之间的离散对数关系，$Q$由证明者选择，而验证者未知其离散对数$q$。如果$Q$的离散对数对验证者是未知的，那么验证者不能根据$P$与$Q$之间的离散对数关系推导出私钥。

设$s$为生成$Q$所需的$P$相加自身的次数，即$sP = Q$。如果证明者知道$P$和$Q$的离散对数，分别为$p$和$q$，他们可以轻松计算出$s$，即$s = q/p$。

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

$$ \begin{align} Q &= sP\\ Q &= qG\\ P &= pG\\ qG &= spG \\ q &= sp \\ \frac{q}{p} &= s\\ \end{align} $$

然后验证者可以检查确实$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$次来选择的。

在那种情况下，验证者检查

$$ \begin{align} qG &\stackrel{?}{=} Q &&\text{ // 证明者知道Q的离散对数}\\ sP &\stackrel{?}{=} Q &&\text{ // 证明者知道多少次加P得到Q} \end{align} $$

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

然而，验证者可以根据这些信息计算私钥。

$$ \begin{align} Q &= sP\\ s^{-1}Q&=P\\ s^{-1}(qG)&=P\\ s^{-1}q &= P/G\\ s^{-1}q &= p\\ \end{align} $$

所以我们有一个难题：如果我们公开$Q$的离散对数，验证者可以计算出私钥。如果证明者能随意选择$Q$，那么他们就能为他们不知道离散对数的公钥生成签名。

我们不能让验证者能够计算出私钥，因此公开$q是不行的。

因此，我们的解决方案必须包括证明者选择$Q$——但我们必须防止证明者完全任意选择$Q$（比如通过选择任意的$s$并生成$Q = sP$）。

接下来，证明者必须证明他们知道$Q$和$P$的离散对数，但不暴露任一离散对数$p$或$q$。

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

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

关键思想是这样的：

如果证明者知道$P$和$Q$的离散对数，那么他们不仅必须知道$s$使得$sP = Q$，他们还必须知道$s’$使得$s’(hG + P) = Q$，其中$h$是验证者随机选择的值，证明者无法预测的值。

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

加法偏移防止伪造

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

在证明者向验证者发送$P$和$Q$后，验证者返回一个标量$h$（公共标量值）。然后，证明者必须生成$s$使得$Q = s(hG + P)$（我们不再需要$s’$标记）。

此时，证明者无法控制$P$和$Q$之间的离散对数关系，而必须证明他们知道$(hG + P)$和$Q$之间的离散对数关系。

由于验证者已经拥有$P$和$Q$，证明者无法简单选择随机的$s$并生成$Q$使得$Q = s(hG + P)$。证明者必须证明他们知道新点$(hG + P)$和原始$Q$之间的离散对数关系。

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

$$ s = \frac{q}{h + p} $$

具体而言，证明者推导出：

$$ \begin{align} s(hG + P)&=Q\\ s(h + p) &= q\\ s&=\frac{q}{h+p} \end{align} $$

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

1. 我们假设$G$（以及它所属的椭圆曲线组）是双方协商一致的。 2.证明者发布它们的公钥$P$，并希望证明他们知道私钥$p$。
2. 验证者响应一个标量$h$。
3. 证明者选择一个随机$q$并计算$Q = qG$。
4. 证明者计算$s = q(h + p)^{-1}$并将$(s, Q)$发送给验证者。
5. 验证者检查$Q \stackrel{?}= s(hG + P)$。

最后的检查有效，因为在底层，$s$抵消了$h$和$p$的离散对数：

$$ \begin{align} Q &= s(hG + P)\\ qG &= \frac{q}{h + p}(hG+P)\\ qG &= \frac{q}{h + p}(hG+pG)\\ qG &= \frac{q}{h + p}(h+p)G\\ qG &= \frac{q}{\cancel{h + p}}(\cancel{h+p})G\\ qG &= qG \end{align} $$

防范伪造签名

让我们看看恶意证明者如何尝试计算$s$而不知道$P$和$Q$的离散对数，并看看为什么尝试会失败。

证明者虚构一个值$\tilde{q}$并生成$Q = \tilde{q}P$，并将$Q$发送给验证者。让$\tilde{q}$是恶意证明者虚构的值，而不是$Q$的离散对数。

验证者用标量$h$进行响应。

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

$$s(P + hG) = Q$$

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

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

然而，无论证明者如何替代$Q$或$P$，他们都会面临一个问题，因为他们无法解决$s$，因为$P$的离散对数对他们来说是未知的。

替代$Q$

这里证明者替代$Q$：

$$s(P + hG) = \boxed{Q}$$

$$s(P + hG) = \boxed{\tilde{q}P}$$

$$s = \frac{\tilde{q}P}{P + hG}$$

我们不能对椭圆曲线点做除法，因此要计算上述分式，我们需要知道$p$：

$$s = \frac{\tilde{q}p}{p + h}$$

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

替代$P$

现在，恶意证明者尝试替代$P$而不是$Q$，但遇到的问题是他们不知道$Q$的离散对数：

$$s(\tilde{q}^{-1}Q + hG) = Q$$

$$s = \frac{Q}{(\tilde{q}^{-1}Q + hG)}$$

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

为什么偏移需要是加法

我们怎么知道应该将$hG$添加到$P$而不是将$hP$乘以并要求证明者提出$s$使得$Q = hsP$？

问题在于，通过乘法偏移，证明者可以抵消$Q$和$P$的离散对数的因子。

回顾：恶意的证明者不知道$q$，即$Q$的离散对数，或者$p$，即$P$的离散对数。然而，他们知道$Q$是比$P$大$\tilde{q}$倍，其中$\tilde{q}$是他们自己虚构的数字，而不是$q$的真实离散对数。

如果验证者提出$h$，并要求证明者提出使得$Q = shP$的$s$，那么证明者简单计算出$s = \tilde{q}/h$。

这将通过验证者的测试：

$$ \begin{align} Q &= shP \\ Q &= \frac{\tilde{q}}{h}h P\\ Q &= \frac{\tilde{q}}{\cancel{h}}\cancel{h} P\\ Q &= qP \\ \end{align} $$

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

使我们的协议非交互式

不幸的是，我们的解决方案要求验证者在收到$P$和$Q$后发送$h$，需要证明者和验证者相互“交互”。

如果我们想使我们的协议非交互式，则$h$不能来自验证者，证明者必须自己生成它。

如果证明者事先知道$h$（这也是必须的，特别是如果证明不是交互式的），那么我们开始回到原来的问题。

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

$$Q = s(hG + P)$$

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

为了避免证明者选择$h$和与验证者的交互，我们可以通过哈希$Q$来模拟验证者选择$h$：

$$h = \mathsf{hash}(Q)$$

由于验证者无论如何都会随机选择$h$，证明者可以通过使用哈希函数以伪随机的方式计算$h$。这种技术被称为Fiat-Shamir转换。

私钥知识的功能性证明

算法如下：

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$后，恶意证明者需要计算$s$使得$Q = s(hG + P)$。然而，他们无法做到这一点，因为他们不知道$(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$的离散对数的算法是

$$Q = s(hG + rP)$$

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$生成的。因此，证明者必须实际知道$P$的离散对数$p$以计算$s$。

优化预ECDSA算法

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

让我们回想一下$r = \mathsf{hash}(Q)$想要实现的目标。最终验证公式是：

$$Q \stackrel{?}= s(hG + rP)$$

其意图是我们希望$r$依赖于$Q$，使得$Q$不会完全由证明者完全控制的值$s$决定。为了计算$s$，证明者必须知道$P$的离散对数。

我们希望有一个更便宜的替代方式使得$r$依赖于$Q$。

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

现在考虑，如果我们给出一个标量值$a$，通过$A = aG$形成的椭圆曲线点$A$看起来随机。$A$与$a$之间没有明显的关系。正是这种缺乏明显关系使得计算离散对数变得困难。

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

因此，我们可以将$Q = qG$视为类似于$\mathsf{hash}(q)$的输出。也就是说，$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 = \frac{h + rp}{k} $$

注意，$s$是相对我们之前的实现“反转”的。实际上在ECDSA算法中，证明者计算$s^{-1}$，而验证者稍后进行反转，正如我们将看到的那样。

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

这个公式的背后过程如下：

$$ \begin{align} &=s^{-1}(hG + rP)\\ &=\frac{k}{h + rp}(hG + rP)\\ &=\frac{k}{h + rp}(hG + rpG)\\ &=\frac{k}{h + rp}(h + rp)G\\ &=\frac{k}{\cancel{h + rp}}(\cancel{h + rp})G\\ &=kG \end{align} $$

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

给定签名推导公钥

Ethereum和Bitcoin区块链没有验证签名，而是根据公钥、消息和签名。相反，给定消息和签名，它们推导出公钥，并检查计算出的公钥是否与预期的公钥匹配。

要了解这个过程的工作原理，我们可以对验证公式做一些代数学运算，推导出给定签名和消息哈希的公钥。

$$ \begin{align} R &= s^{-1}(hG + rP)\\ R &= s^{-1}hG + s^{-1}rP\\ R – s^{-1}hG &= s^{-1}rP\\ sr^{-1}R-r^{-1}hG&=P\\ \end{align} $$

但是，仅有$(\text{message}, r, s)$是不够的，因为$r$对应于两个$y$值的两个可能点，即$r = R.x$。为了消歧义，签名者还需发送一个布尔变量，以指示正在使用的$r$的$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 = sr^{-1}R – r^{-1}hG$$

并接受签名，如果计算得出的$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抵消，恢复的公钥相同：

$$ \begin{align}P &= (-s)r^{-1}(-R) – r^{-1}hG\\ &= sr^{-1}R – r^{-1}hG \end{align} $$

为防止此攻击，验证者应不接受对他们以前见过的相同消息的不同签名。更通用和稳健的解决方案是使用一个随机数，即一次性随机数，证明者必须将其包含在消息中。一次性数字（nonce）是每个签名的唯一标识符，通过要求证明者在每个签名中加入一个新的、更大的随机数，验证者可以轻松检测并拒绝试图重用或修改先前签名的行为。

如果验证者不对消息进行哈希，则可能会创建伪造的证明。

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

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

我们可以通过将虚假值$d$和$h$插入验证公式，看到这种攻击的工作原理：

$$ \begin{align} R &\stackrel{?}= s^{-1}(hG + rP) \\ R &\stackrel{?}= (\frac{r}{b})^{-1}((\frac{ar}{b})G + rP) \\ R &\stackrel{?}= (\frac{b}{r})((\frac{ar}{b})G + rP) \\ R &\stackrel{?}= (aG + bP) \end{align} $$

防止这种攻击的方法很简单：$h$必须是验证者对消息哈希的结果。计算哈希时，几乎不可能生成$ar/b$的哈希值。

总结

ECDSA算法是指向离散对数关系的证明，该关系在某个任意点$R$与一个表示将消息哈希乘以生成器和公钥的和的点之间，以及公钥乘以签名者没有控制的伪随机值之间。

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

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

资助与致谢

在创作本文时参阅了以下资源：

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

• 原文链接： rareskills.io/post/ecdsa...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～