密码学 | 椭圆曲线数字签名方法 ECDSA（下）

目录

10  ECDSA 算法

11  创建签名

12  验证签名

13  ECDSA 的安全性

14  随机 k 值的重要性

15  结语

---

⚠️ 原文：Understanding How ECDSA Protects Your Data.

⚠️ 写在前面：本文属于搬运博客，自己留着学习。同时，经过几天的折磨后，我对椭圆曲线已经有点基础了，因此删除了一些我认为无关紧要的原文。

10  ECDSA 算法

现在让我们来谈谈 ECDSA 签名算法。

对于 ECDSA，你首先需要知道你的曲线参数，即 a、b、p、N 和 G。你已经知道 a 和 b 是曲线函数的参数：

还知道 p 是模数，N 是曲线的点数。但还需要知道 G 是什么。G 代表一个 “参考点” 或者说一个 “原点”，参考点可以是曲线上的任何一点。

NIST（美国国家标准与技术研究院）和 SECG（高效加密标准组）提供了预先制作和标准化的曲线参数，这些参数被认为是有保障且高效的。

私钥是一个 160 位的随机数，而公钥是曲线上的一个点，它是私钥与参考点 G 的点乘结果。设 dA 为私钥，Qa 为公钥，则有：Qa = dA * G，其中 G 是曲线参数中的参考点。

不懂 dA 和 Qa 为什么要这样大小写 😇

11  创建签名

一个签名的长度是 40 个字节，它由两个 20 字节的值组成，第一个称为 R，第二个称为 S，所以 (R, S) 共同构成 ECDSA 签名。具体流程如下：

首先，您必须生成一个随机值 k（20 字节），并使用 “点乘法” 计算 P 点：

P 点的 x 坐标值即为 R，它的长度是 20 个字节。

为了计算 S，您必须对消息进行 SHA1 散列，得到一个长为 20 个字节的值，我们将称之为 z 。现在您可以使用以下方程计算 S：

请注意 k^{-1}，它是 k 的 “模乘逆”。虽然 k^{-1} 本质上是 k 的倒数，但由于我们处理的是整数，所以这是不可能的。因此要求 k^{-1} 是一个整数，它能够使得 (k^{-1} * k) mod p 等于 1 。

暂时还没有学 “模乘逆”，应该就是一个求模数的方法。

再次提醒您，k 是用于生成 R 的随机数，z 是要被签署的消息的散列，dA 是私钥，R 是 k*G 的 x 坐标值，其中 G 是曲线参数的参考点。

12  验证签名

既然您已经有了签名，您想要验证它，这也是相当简单的。

您使用这个方程来计算一个点 P：

只要 P 点的 x 坐标值等于 R，就意味着签名是有效的，否则它就不是。

按照上述方程把 P 点计算出来，只要这个 P 点的 x 坐标值等于 R，就说明签名有效。

很简单，对吧？现在让我们看看为什么成立，这需要一些数学来验证。

我们有：

可以看出，算 P 点的时候只需要使用一些公开的数据，而不会涉及私钥。

其中

因此

我们代入 P 点的坐标值有：

我们可以通过消除 G 来简化，得到：

通过求 k 和 S 的逆，我们得到：

这正是用于生成签名的方程，因此等号左右两边的式子是相等的。这就是为什么您可以使用上面的第一个方程来验证签名。

签名的时候会需要使用私钥 dA，验证的时候只需要使用公钥 Qa，这就是所谓的零知识证明吧。

13  ECDSA 的安全性

因为 Qa=dA*G、P=k*G，又因为 ECDSA 的 “点乘法” 是一个陷门函数 —— 在第 9 步中解释过 —— 所以我们不能根据 Qa 和 P 来倒推 dA 或 k，这使得 ECDSA 算法是安全的。

我们没有办法找到私钥，也没有办法在不知道私钥的情况下伪造签名。

为什么 “也没有办法在不知道私钥的情况下伪造签名”？

14  随机 k 值的重要性

现在让我们讨论一下索尼在 Playstation 3 上使用的 ECDSA 签名是如何出现缺陷的，以及这是如何允许黑客获取 PS3 的 ECDSA 私钥的。

生成签名所需的方程如下：

S 方程的强度在于它一个方程含有两个未知数，即 k 和 dA，因此无法进行求解。

然而，算法的安全性基于其实现，即确保 “k 是随机生成的” 非常重要，确保没有任何人能够猜测、计算，或者使用时序攻击或其他任何类型的攻击来找到随机值 k 。

索尼

但是索尼在实现上犯了一个巨大的错误，他们在任何地方都使用相同的 k 值。

这意味着如果你有两个签名，它们都有相同的 k，那么它们都会有相同的 R 值。同时这意味着，只要你拥有同一个人的两个签名 S 和 S'，就能计算出 k 值。

首先让 S 和 S' 相减：

整理得到

从而有

其中，z 和 z'、S 和 S' 都是已知的。

一旦得到了 k，那么 S 方程就只含一个未知数了，从而可以很容易地解出 dA：

一旦得到了私钥 dA，你可以用它来签署自己的文件，而 PS3 将会认为它是索尼签名的合法文件。这就是为什么确保用于生成签名的随机数实际上是 “密码学上随机” 的非常重要的原因。

比特币

另一个例子是当一些比特币客户端在某些浏览器和某些 Android 客户端上使用非密码学随机数生成器时，这导致它们用相同的 k 值签署交易，恶意人士能够找到他们的比特币钱包私钥并盗取他们的资金。

小结

这显示了每次制作签名时使用真正随机数的重要性，因为如果你签名对的 (R, S) 中的 R 值在两个不同的签名中相同，你就会暴露私钥。

理论上，ECDSA 算法非常安全，不可能找到私钥。当然，它的前提是 “算法实现是正确的”。如果有一种方法可以找到私钥，那么每个计算机、网站、系统的安全性都可能受到威胁。

15  结语

最后！我希望这能让很多人更清楚地理解这个算法。我知道这仍然非常复杂和难以理解。我通常试图让非技术人士更容易理解事物，但这个算法太复杂了，无法用更简单的术语来解释。

但是，如果您是一名开发人员或数学家，或者您对学习此内容感兴趣，因为您想帮助或简单地获取知识，那么我相信这为您提供了开始学习或至少理解这个被称为 “ECDSA” 的未知野兽的概念的信息。

附言：在本文中，我使用了 “160位” 来讨论 ECDSA 签名，因为它通常与 160 位的 SHA1 散列值（20 字节）匹配，而且 PS3 安全机制就是使用的这种组合。但是，该算法本身可以使用任何大小的数字。本文可能存在其他不准确之处，但就像我说的，我不是专家，而且我已经尽可能地将内容简化，同时没有删除关于算法的任何信息。