15年做啥网站能致富,网站上线方案,广告传媒公司简介,深圳宝安区租房目录
10 ECDSA 算法
11 创建签名
12 验证签名
13 ECDSA 的安全性
14 随机 k 值的重要性
15 结语 ⚠️ 原文#xff1a;Understanding How ECDSA Protects Your Data.
⚠️ 写在前面#xff1a;本文属于搬运博客#xff0c;自己留着学习。同时#xff0c;经过几…目录
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 签名。具体流程如下
首先您必须生成一个随机值 k20 字节并使用 “点乘法” 计算 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 的安全性
因为 QadA*G、Pk*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 安全机制就是使用的这种组合。但是该算法本身可以使用任何大小的数字。本文可能存在其他不准确之处但就像我说的我不是专家而且我已经尽可能地将内容简化同时没有删除关于算法的任何信息。
