大家好呀，上期介绍了什么是数字签名和ECDSA，本期带大家了解一下ECDSA的原理。（友情提醒：请备好晕车药和垃圾桶）
基础数学与二进制
ECDSA只使用整数，没有浮点数（这意味着可能的数值是1，2，3……，但不可能是1.5，2.5……），而且整数的范围受到签名中所使用的比特位数的限制，使用更多的比特意味着更大的数字范围，也拥有更高的安全性能，因为这使得“猜”到方程当中所采用的具体数字变得更难。
众所周知，计算机采用比特来表示数据，一个比特是二进制的“数字”（0和1），八个比特表示一个字节。
每次你增加一个比特，可表示的最大整数就可以翻一倍：
使用4个比特，你可以表示0~15，一共16个数字，
使用5个比特，你可以表示0~31，一共32个数字，
使用6个比特，你可以表示0~63，一共64个数字……
因此，8个比特，即1字节，可以表示256个数字，32字节，则可以表示4294967296个数字……通常ECDSA会总共使用160比特，它可以表示相当大的数，可以有49位数字在里面。
另一个你需要知道的知识点是数学里的模运算，简单的说，它是整数求除之后的余数。
举个例子，x mod 10意味着x除以10的其余部分，它将始终是0和9之间的数字，所以142 mod 10的结果是2；另一个例子是x mod 2，如果x是偶数则结果为0，如果x是奇数则结果为1。
ECDSA方程
现在言归正传，ECDSA是如何工作的呢？首先，椭圆曲线密码学是基于下面的一个方程式：
你需要注意的是，有一个模运算（mod），并且 y 是平方的（不要忘记这是图上曲线的方程），这意味着对于任何x坐标（不要忘记，我们只使用整数），将会有两个y值，并且曲线在X轴上是对称的。方程中模的底数p是一个素数，并确保所有的值在160位的范围内，它允许使用模平方根和模的乘法逆元来简化运算。
由于我们有一个模（p），这意味着 y ^ 2 的可能值在 0 和 p-1 之间，这之间便是所有可能的值。因为ECDSA规定只能是整数，只有那些值较小的子集才能构成一个“完美平方”（两个整数的平方值），这给了 N 个可能的点，其中 N <p（N 是数字 0 和 p 之间的完美平方）。
由于每个 x 将产生两个点（y ^ 2的平方根的正值和负值），这意味着有 N / 2 个可能的 “x” 坐标是有效的，并在曲线上给出一个点。因为整数计算和模数的限制，所以符合这些条件的点在椭圆曲线上是有限的。
看到这里，是不是有点难，你还能理解吗？
总结一下，然后再继续。ECDSA方程为我们提供了一个有限数量的有效点的曲线（N），因为 Y 轴受模量（p）的约束，并且需要是在 X 轴上具有对称性的完美平方（y ^ 2） 。我们总共有 N / 2 个可能的，有效的 x 坐标，不要忘记 N <p。
点加法
关于椭圆曲线你需要知道的另一件事是“点加法”的概念。曲线上点 P 与点 Q 的加法被定义为经过点P、Q的直线与椭圆曲线除P、Q外的第三个交点的对称点。如上图所示，P+Q=S，其中R为经过点P、Q的直线与椭圆曲线的交点，S为该椭圆曲线上R的对称点。
椭圆曲线的性质保证了经过曲线上两个点的直线，一定会跟曲线交于第三个点，并且只有这一个交点，切线可认为是经过曲线上两个相同的点（切点）的直线。
所以你可以看到一个形式为y ^ 2 = x ^ 3 + ax + b（其中a = -4和b = 0）的曲线，它在 X 轴上是对称的，其中 P + Q 是对称点 R 点是从 P 到 Q 的直线的第三个交点。
点乘法
同样的，如果你做 P + P，它将是 R 的对称点，它是与点 P 相切的线的交点。P + P + P 是所得点之间的相加点由于 P + P + P可以写成（P + P）+ P，这就定义了“点乘法”，即k * P 就是椭圆曲线上点P自身相加k次后得到的椭圆曲线上的点。可以看看上图的两个例子。
在这里，你可以看到两条椭圆曲线和一条从中画出切线的点 P，它与曲线相交于第三点，其对称点是 2P，然后从那里你从 2P 和 P 画出一条直线，会与曲线相交，对称点为3P。
现在你是否明白，为什么在进行加法时需要取 R 的对称点，因为相同点的多次加法总会给出相同的直线和相同的三个交点。
单向陷门函数
点乘法的一个特殊性是，如果有一个点 R = k * P，并且你知道椭圆曲线上的R和P这两个点，无法据此直接计算出 ‘k’ 的值是什么。这是因为椭圆曲线密码中没有点减法和点除法的运算，不能只求解 k = R / P道 P。
并且，因为你可以做成千上万次的加法，最终你只是知道在曲线上面结束的点，但是具体是如何到达这个点你也并不知道。你无法进行反向操作，得到与点P相乘以后给你点R的k 。
即使你知道原始点和终点也不能找到被乘数的东西，这是ECDSA算法背后安全的基础，但只要知道原始点和被乘数，很容易就能计算出终点，这个原理被称为 “单向陷门函数“。
ECDSA算法
上面是对 ECDSA 的铺垫，接下来让我们认识一下 ECDSA 签名算法的庐山真面目。
对于 ECDSA，首先需要知道曲线参数，参数是 a，b，p，N 和 G。你已经知道 a 和 b 是曲线函数的参数（y ^ 2 = x ^ 3 + ax + b），即 ‘p’ 是模的底数，’N’ 是曲线的点数，’G’ 是ECDSA所需要的，它代表一个’参考点’或者你可以理解为一个起点。参考点可以是曲线上的任何点。
曲线上的参数是非常重要的，不知道它们，你显然不能签名或验证签名。是的，验证签名不仅仅是知道公钥，还需要知道公钥的派生参数。NIST（美国国家标准技术研究院）和SECG（高效密码学标准组织）提供已知安全和高效的预制和标准化曲线参数。
所以首先，你将拥有一个私钥和一个公钥。私钥是一个随机数（也是160位），并且公钥是由 私钥点乘G 所生成的曲线的点。我们把’dA’作为私钥（随机数）和’Qa’作为公钥（椭圆曲线上的点），所以我们有：Qa = dA * G（其中G是曲线参数中的参考点）。
创造签名
那么如何利用ECDSA对一个文件/消息进行签名呢？
首先，你需要知道签名是 40 个字节，并且用两个 20 字节的值来表示，第一个被称为 R，第二个被称为 S 。值对（R，S）就是你的 ECDSA 签名。下面介绍如何计算这两个值，首先你必须生成一个随机值 ‘k’（20个字节），并使用点乘法来计算点 P = k * G。R为点P的 x坐标的值。
为了计算 S，你必须做一个消息的 SHA1 哈希值，这会给你一个 20 字节的值，你会认为它是一个非常大的整数，我们称它为 ‘z’。现在你可以用下面的公式计算S：
这里注意k ^ -1是k的 “模乘法逆元”，它不是 k 的倒数，而是一个使得（k ^ -1 * k）mod p等于1成立的整数。
再次提醒，k 是用于生成 R 的随机数，z 是要签名的消息的哈希，dA 是私钥，R是P点的X坐标值。
验证签名
最后这个就是之前用来产生签名的方程，这是相匹配的，这是我们可以采用本节开头给出的方程进行签名验证的原因。
ECDSA的安全性
你可能注意到，为了计算 S，需要 ‘k’（随机数）和 ‘dA’（私钥），但只需要 R和 Qa（公钥）来验证签名。
由于 R = k * G 和 Qa = dA * G，并且由于ECDSA 点乘法中的单向陷门函数（在上面的单向陷门函数），所以我们不能通过知道 Qa 和 R 来计算 dA 或 k，这使得 ECDSA 算法是安全的，找不到私钥，没有办法在不知道私钥的情况下伪造签名。
随机数K的重要性
所以你还记得产生一个签名所需的等式吧。R = k * G和S = k ^ -1（z + dA * R）mod p 这些等式的优势在于实际上有一个方程里有两个未知数（k和dA），因此是没办法确定其中的任意一个的。
话又说回来，算法的安全性是基于其实现的，确保“k”是随机生成的，并且没有办法让某人可以猜测、计算或使用计时攻击或任何其他类型的攻击来得到随机值’k’。但索尼在实现上犯了一个巨大的错误，他们在每个地方都使用相同的“k”值，这意味着如果你有两个相同的k，那么它们将具有相同的R值，这意味着您可以使用两个文件的两个S签名（分别为哈希z和z’以及签名S和S’）来计算k：
只要你知道了私钥dA，你现在就可以签名你的文件，PS3将把它识别为索尼签署的真实文件。这就是为什么确保用于生成签名的随机数实际上是“密码随机”的原因。这也是为什么PS3不可能拥有高于3.56的自定义固件的原因，仅仅是因为自从 3.56 版本以来，索尼已经固定了他们的 ECDSA 算法实现并且使用了现在不可能找到私钥的新密钥。
这个问题的另一个例子是，当一些比特币客户端使用非密码随机数生成器（在某些浏览器和某些Android客户端上）导致他们使用相同的“k”值签名交易时，恶意人员能够找到他们的比特币钱包的私钥和窃取他们的资金。
这显示了每次签名时使用真正的随机数字的重要性，因为如果（R，S）签名对的R值在两个不同的签名上相同，则会暴露私钥。
这是一个关于随机数的笑话，这成为了解释这个问题的前景。每当这种算法的执行错误发生时，图像经常被重新使用。
ECDSA算法是非常安全的，不可能找到私钥，只要正确完成就行了，因此很多计算机、网站、系统的安全性可能会受到影响。
总结
但愿这能够帮助大家初步理解ECDSA算法，也希望对大家有所帮助。
希望大家看完不是这副表情
来源：freebuf.com 2020-11-25 09:26:52 by: beikatech
请登录后发表评论
注册