[译]你知道ECDSA是如何保护你的数据的么？

2018-01-16 本文已影响47人 wolf4j

每个人都可能以某种形式听说过ECDSA。当我说“数字签名”时，有些哥们会更好地认识到这一点，当然有些哥们根本不知道我在说什么。

我曾经试着去了解ECDSA是如何工作的，但很难搞清楚，因为大多数在线参考文献是不够的。他们要么是太基本了 - 他们只是解释算法的基础知识，或者他们太牛叉-“它是如何工作的？” 。所以你在“它是如何工作的”和“我们是如何到达这里的？”之间挣扎着。所以，如果你没有数学或密码学的学位，但仍然想知道它是如何工作的（除非“奇迹发生，或者你是天才”），那么，恭喜你，你来对地方了。

Step1: ECDSA 是什么？

ECDSA 全称 “Elliptic Curve Digital Signature Algorithm”，它用于创建数据的数字签名（例如文件），以便在不影响安全性的情况下验证其真实性。把它想象成一个真实的签名，你可以识别某人的签名，但是如果没有其他人知道你就不能伪造它。 ECDSA签名与真实签名之间的区别在于，伪造ECDSA签名是不可能的。

理解 ECDSA 要注意区分其与用于加密数据的 AES（高级加密标准）的区别。ECDSA不会加密或阻止某人查看或访问你的数据，但它可以防止数据被篡改。

在“ECDSA”这里有两个词值得注意，那就是“曲线”和“算法”，因为这意味着 ECDSA 基本上都是关于数学的。所以我认为首先要说：“嗨，兄弟们，你现在还在扯学的那些高数完全没有什么卵用么！“ECDSA涉及到的数学是相当复杂的，所以我尽量庸俗化，让非技术人员可以理解，但你仍然可能需要一些在数学知识正确理解。下面，我将分两部分来处理，一部分是关于它是如何工作的一个高层次的解释，另一部分是深入理解其内部的工作原理。

Step2:了解基础知识

其实原理很简单，你拿出纸来，绘制一个数学上的曲线方程，然后你在该曲线上随机选择一点作为你起始的点，然后你生成一个随机数，这是你的私钥，你用这个随机数和“起点”来做一些神奇的数学方程，并且在曲线上得到第二个点，那就是你的公钥。

当你想签署一个文件时，你将使用这个私钥（随机数）和一个散列的文件（一个唯一的数字来表示文件）为一个神奇的方程，这会给你你的签名。签名本身分为两部分，分别称为R和S.为了验证签名是否正确，您只需要公钥（使用私钥生成的曲线上的那个点），然后将其放入另一个神奇的方程与签名的一部分（S），如果它使用私钥正确签名，它会给你另一部分的签名（R）。所以为了简短起见，一个签名由两个数字R和S组成，你用一个私钥生成R和S，如果一个使用公钥和S的数学方程给你R，那么签名是有效的。没有办法知道私钥或仅使用公钥创建签名。

Step3:为什么使用 ECDSA？

OK，目前你只了解了一点基础知识，你或许没意识到，ECDSA 是复杂的，公钥、私钥又是什么鬼？别担心，你马上就会明白，但首先解释一下，为什么使用ECDSA以及它可能有什么用？

除了上述提到的“我需要签署合同/文件”之外，下面是一些别的用例：例如，我们不希望其数据被用户破坏或修改，例如只允许用户你加载官方地图但不可以进入国防部或电话或其他类型的设备，只允许你安装官方的应用程序。

在这种情况下，文件（应用程序，游戏地图，数据）将用 ECDSA 签名，公钥将与应用程序/游戏/设备捆绑在一起并验证签名，以确保数据没有被修改，而私钥被锁在一个安全的地方。虽然你可以使用公钥验证签名，但是你不能用它创建/伪造一个新的签名，那么这个公钥就可以随应用/游戏/设备一起分发，而不用担心。

这与AES加密系统不同，后者允许您对数据进行加密，但您需要密钥进行解密，而这样的应用程序需要捆绑你的密钥。

一个很好的例子就是PlayStation 3游戏机被打开了，所有的文件都可以被解密，PS3文件中的所有密钥都可以被提取出来，但是还有一件东西需要破解，就是ECDSA签名，它可以防止任何人使应用程序运行在最新的固件上

再通俗一点的解释，http与https的区别，我们拥有一个SA认证机构，私钥拿在自己手里，公钥广播出去，我拿私钥验证公钥（这个仅仅是用来理解公钥和私钥，到此为止啊）。

Step 4:基础数学和二进制

OK，接下来建议你备好垃圾桶，可能会感到恶心或者不适。

让我们从基本知识开始（对于知道这个知识的人可能是无聊的，但对于那些不了解的人是必须的）：ECDSA只使用整数数学，没有浮点数（这意味着可能的值是1，2，3等等，但不是1.5, 2.5等），而且数字的范围受到签名中使用多少比特的限制（更多比特意味着更大的数字，更高的安全性，因为猜测变得更难（在这个等式中使用的关键数字）。计算机使用“位”来表示数据，一位是二进制符号（0和1）中的“数字”，而8位代表一个字节。每增加一位，可以表示的最大数量加倍，4位可以表示0到15（总共16个可能的值），5位可以表示32位数值，6位，您可以表示64个值等。一个字节（8位）可以表示256个值，32位可以表示4294967296个值（4千兆）。通常ECDSA将使用总共160位，嗯哼，一个 49 位大的数字.....

你需要知道的另一个数学结构是模数，可以通过说它是整数的其余部分来简化模数。例如，x mod 10意味着x除以10的其余部分，它将始终是0和9之间的数字，所以142 mod 10例如给出2。另一个例子是x mod 2，其中偶数和0分别为0和1。

Step 5: Hash

ECDSA 与消息的 SHA1 加密散列一起使用来签名（文件）。哈希是另一个数学方程式，适用于每个数据字节，这将给一个数据唯一的数字。例如，所有字节的值的总和可以被认为是非常 low 的散列函数。所以如果消息（文件）有任何变化，那么哈希将是完全不同的。在 SHA1 哈希算法的情况下，它总是 20 个字节（160位）。这对于验证文件没有被修改或损坏是非常有用的，对于任何大小的文件，你都会得到 20 字节的哈希值，你可以轻松地重新计算哈希值以确保匹配。 ECDSA 所标记的实际上就是散列，所以如果数据发生变化，散列会发生变化，而且签名不再有效。

为了理解，我们来一个例子。我们将使用最简单的（和最 low 的）散列函数，其中我们将所有数据的总和作为结果的模数10。

首先，你需要明白一点，世间万物将被用一个数字来表示。一个文本文件是一系列的字节，正如我们前面所解释的，它代表了8位，这意味着它可以表示一个介于0和255之间的数字。所以，如果我们将每个字节作为一个数字并添加文件的每个字节，那么我们结果为 10 的模数，我们将以 0 到 9 之间的数字作为结果散列。数据相同，我们将总是得到相同的哈希值，如果更改了文件中的一个字节，结果可能会不同。当然，你也会明白，为了获得相同的散列值，改变文件将是非常容易的，因为只有10种可能性（0到9），那么就有十分之一的机会获得相同的散列值通过改变文件的内容。

这就是 SHA1 起作用的地方，SHA1 算法比我们简单的“模数 10 ”散列函数复杂得多，它将给出非常大的数字（160位，所以是一个十进制的49位数），它的特殊性使得我们如果从文件中修改了一位数据，结果就会彻底改变。

这使得 SHA1 成为一个非常好的哈希算法，这种算法是不可预知的，这是非常安全的，并且几乎不可能得到“冲突”（当两个不同的文件具有相同的哈希），并且不可能伪造数据来获得特定的哈希，如果你 OK 的话，不要听我逼逼了，建议你参加最强大脑。

Step 6: ECDSA 方程

那么，它是如何工作的呢？ECDSA是基于下面的一个方程等式：
y^2 = (x^3 + a * x + b) mod p

你首先需要注意的是有一个模（mod），并且 'y' 是平方的（不要忘记这是图上曲线的方程）。这意味着对于任何x坐标（不要忘记，我们只使用整数），您将有两个y值，并且曲线在X轴上是对称的。该模是一个素数，并确保所有的值在160位的范围内，它允许使用“modular square root”和 “modular multiplicative inverse”
的数学，使计算的东西更容易。由于我们有一个模（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。

Step 7: “ 点加法 ”

点加法

关于椭圆曲线你需要知道的另一件事是“点加法”的概念。它被定义为增加一个点 P 到另一个点 Q 将导致一个点 S，使得如果你绘制一条线从 P 到 Q，它将与第三个点 R 上的曲线相交，这是 S 的负值（记住该曲线在X轴上是对称的）。在这种情况下，我们定义了R = -S来表示R在X轴上的对称点。看上面的图来理解。

所以你可以看到一个形式为y ^ 2 = x ^ 3 + ax + b（其中a = -4和b = 0）的曲线，它在 X 轴上是对称的，其中 P + Q 是对称点 R 点是从 P 到 Q 的直线的第三个交点。

Step8:“ 点乘法 ”

点乘法

同样的，如果你做 P + P，它将是 R 的对称点，它是与点 P 相切的线的交点。P + P + P 是所得点之间的相加点由于 P + P + P可以写成（P + P）+ P，这就定义了“点乘法”，其中 k * P 是点 P 到点 K 的相加点。看看上面的两个图像点乘法的例子。

在这里，你可以看到两条椭圆曲线和一条从中画出切线的点 P，它与曲线相交于第三点，其对称点是 2P，然后从那里你从 2P 和 P 画出一条直线，会与曲线相交，对称点为3P。等等...你可以继续做点乘法。现在是否明白了为什么在进行加法时需要取 R 的对称点，因为相同点的多次加法总会给出相同的直线和相同的三个交点。

Step9: 陷阱门函数

点乘法的一个特殊性是，如果你有一个点 R = k * P，那么你知道 R 并且知道 P，但是没有办法找出 'k' 的值是什么。由于没有点减法或点除法，所以不能只求解 k = R / P。另外，由于你可能做了数百万次的增加，你只能在曲线上的另一个点上，你不知道你是怎么到达的。你不能扭转这个操作，而且你找不到与你的点 P 相乘的值 “k”，给你的结果点 R.
即使你知道原始点和终点也不能找到被乘数的东西是ECDSA算法背后安全的基础，这个原理被称为 “陷阱门函数“。

Step 10: 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是曲线参数中的参考点）。

Step 11: 创建签名

那么你如何签署一个文件/消息？

首先，你需要知道签名是 40 个字节，并且用两个 20 字节的值来表示，第一个被称为 R，第二个被称为 S ..所以这个对（R，S）一起是你的 ECDSA 签名..现在这里是如何创建这两个值，以签署一个文件..首先你必须生成一个随机值 'k'（20个），并使用点乘法来计算点 P = k * G。那个点的 x 值将代表 'R'。由于曲线 P 上的点由其坐标（x，y）表示（每个坐标长度为20个字节），因此只需要签名的 “x” 值（20个字节），该值将被称为“R” 。现在你需要的是 “S” 值。

为了计算 S，你必须做一个消息的 SHA1 哈希值，这会给你一个 20 字节的值，你会认为它是一个非常大的整数，我们称它为 'z'。现在你可以用下面的公式计算S：

S = k ^ -1（z + dA * R）mod p

这里注意到k ^ -1是k的 “模乘法逆”，它基本上是 k 的倒数，但由于我们正在处理整数，所以这是不可能的，所以它是一个数字，使得（k ^ -1 * k）mod p等于1.再次提醒，k 是用于生成 R 的随机数，z 是要签名的消息的哈希，dA 是私钥，R 是 k 的 x 坐标 * G（其中G是曲线参数的原点）。

Step 12: 验证签名

现在你已经签名了，你想验证一下，它也很简单，你只需要公钥（当然是曲线参数）就可以做到这一点。你用这个公式来计算一个点P：

P = S ^ -1 * z * G + S ^ -1 * R * Qa

如果点P的x坐标等于R，表示签名有效，否则不是。

很简单，是吧？现在让我们看看为什么..这将需要一些数学来验证：

我们有：

P = S ^ -1 * z * G + S ^ -1 * R * Qa

但是 Qa = dA * G，所以：

P = S ^ -1 * z * G + S ^ -1 * R * dA * G = S ^ -1（z + dA * R）* G

但是P的x坐标必须与R相匹配，而 R 是k * G的 x坐标，这意味着：

k * G = S ^ -1（z + dA * R）* G

我们可以通过删除G来简化：

k = S ^ -1（z + dA * R）

通过反转K和S，我们得到：

S = k ^ -1（z + dA * R）

这就是用来生成签名的公式。所以它是匹配的，这就是为什么你可以用上面第一个方程验证签名的原因。

Step 13: ECDSA 的安全性

你可以注意到，为了计算 S，您需要 'k'（随机数）和 'dA'（私钥），但只需要 R和 Qa（公钥）来验证签名。由于 R = k * G 和 Qa = dA * G，并且由于ECDSA 点乘法中的陷阱门函数（在步骤9中说明），所以我们不能通过知道 Qa 和 R 来计算 dA 或 k，这使得 ECDSA 算法是安全的，找不到私钥，没有办法在不知道私钥的情况下伪造签名。

Step 14: 随机数 K 的重要性

random K func

所以你还记得产生一个签名所需的等式吧。R = k * G和S = k ^ -1（z + dA * R）模 p 这个等式的强度是事实上你有一个等式未知数（k和dA），所以无法确定其中之一。

然而，算法的安全性是基于其实现的，确保“k”是随机生成的，并且没有办法让某人可以猜测，计算或使用计时攻击或任何其他类型的攻击为了找到随机值'k'。但索尼在实现上犯了一个巨大的错误，他们在每个地方都使用相同的“k”值，这意味着如果你有两个相同的k，那么它们将具有相同的R值，这意味着您可以使用两个文件的两个S签名（分别为哈希z和z'以及签名S和S'）来计算k：

S – S’ = k^-1 (z + dA*R) – k^-1 (z’ + da*R) = k^-1 (z + da*R – z’ -dA*R) = k^-1 (z – z’)

So :k = (z – z’) / (S – S’)

一旦你知道了k，那么S的方程就变成了一个方程，其中有一个未知数，然后很容易解析为dA：
dA =（S * k-z）/ R

一旦你知道了私钥dA，你现在就可以签名你的文件，PS3将把它识别为索尼签署的真实文件。这就是为什么确保用于生成签名的随机数实际上是“密码随机”的原因。这也是为什么不可能拥有高于 3.56 的自定义固件的原因，仅仅是因为自从 3.56 版本以来，索尼已经固定了他们的 ECDSA 算法实现并且使用了现在不可能找到私钥的新密钥。

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

这显示了每次签名时使用真正的随机数字的重要性，因为如果（R，S）签名对的R值在两个不同的签名上相同，您将公开私钥。

关于这个的一个笑话在xkcd漫画221（见上图）中显示，这成为了解释这个问题的前景。每当这种算法的执行错误发生时，图像经常被重新使用。

ECDSA算法是非常安全的，不可能找到私钥......只要实现正确完成就行了。如果有办法找到私钥，那么每个计算机，网站，系统的安全性可能会受到影响，因为很多系统都依靠 ECDSA 来保证安全性，这是不可能的。

Step 15: 总结

但愿这能够帮助大家初步理解ECDSA算法，也希望对大家有所帮助。

引用

原文链接：Understanding-how-ECDSA-protects-your-data

本文由 Copernicus团队冉小龙 翻译，转载无需授权。