【密码学】一文读懂EdDSA

在之前，我们已经聊过了不少有关于椭圆曲线的知识了，其实，对于椭圆曲线来说，除了我们之前非常熟悉的魏尔斯特拉斯形式，其实，还有别的形式，本文来聊得呢，就是其他的形式，那么我们先来回顾一下，有关于椭圆曲线的知识。

前置知识

魏尔斯特拉斯曲线

魏尔斯特拉斯椭圆曲线是椭圆曲线的一种标准形式，通常用于数学和密码学中。椭圆曲线是一个平面代数曲线，具有很多有趣的数学性质，广泛应用于数论、代数几何以及信息安全，这也是我们熟知的形式，具体标准形式如下

这里，，其中是一个域，对于密码学来说，一般我们取素数域，或者的域，并且，这个要想成为一个椭圆曲线，这里需要满足

否则，曲线会有奇点，简单理解，就是曲线自身存在相交的点，这个其实不属于本文的内容，我们不过多讨论，感兴趣的读者，可以自行了解下。

蒙特卡罗曲线(Montgomery Curves)

除了，上面，我们常见的 魏尔斯特拉斯形式的曲线呢，在密码学当中，还经常用到另一种曲线形式，也就是蒙特卡罗曲线，具体的标准形式如下

这一种形式是由Peter Montgomery在1987年引入，特别适用于高效实现椭圆曲线离散对数问题（ECDLP）的算法，例如用于Diffie-Hellman密钥交换。

这个曲线，我们其实是可以把他转换为魏尔斯特拉斯形式的，这里，简单推导一下吧[1]。

这里，我们需要首先，把B给消除掉，这里，我们需要做一个换元，令

之后，我们带入蒙特卡罗曲线，可以得到

然后，观察到，这里我们需要降低次数，因为魏尔斯特拉斯曲线，没有二次项，因此我们需要再做一次换元，也就是

然后，带入，可以得到

然后，化简一下，可以得到

也就是，对应魏尔斯特拉斯当中，我们令

这样，就可以了。

爱德华曲线(Edwards Curves)

对于，爱德华曲线呢，他的标准形式是

或者，有他的简化形式，也就是

这种曲线由Harold Edwards在2007年首次提出。

Curve25519[3]

Curve25519 是一种在椭圆曲线密码学（ECC）中使用的椭圆曲线，提供 128 位的安全性（256 位密钥大小），并设计用于椭圆曲线迪菲－赫尔曼（ECDH）密钥协商方案。最初的 Curve25519 论文将其定义为一种迪菲－赫尔曼（DH）函数。丹尼尔·J·伯恩斯坦（Daniel J. Bernstein）随后提出将 Curve25519 作为基础曲线的名称，而将 X25519 作为 DH 函数的名称。

这个曲线，具体的形式是

然后，对于素数域，所选择的素数为

注意到，红色的部分，也就是25519的由来，如果我们令基点的x=9，我们可以得到一个阶为

的循环子群。

EdDSA

终于到了，本篇文章的主题了，对于EdDSA的签名算法，我们采用的是爱德华曲线，具体形式如下

这个q和curve25519是一个q， 也是，这个曲线，和我们之前提到的curve25519是双有理等价的，具体代换是[2]

对于这个签名算法呢，其实也包含三个部分，分别是密钥生成，签名算法和验签算法。

密钥生成

首先，随机均匀的选择一个k(这个作为种子)，然后计算H(k), 这里H是哈希函数，然后将H(k)的最后b有效比特，转换成为一个整数，作为, 这里s是私钥，然后对于公钥

其中，B是椭圆曲线的基点。

签名算法

这里，我们先计算r，具体如下

然后，和其他椭圆曲线签名方案类似，我们计算。

之后，我们需要计算签名

其中是椭圆曲线的阶。

验签算法

我们收到签名(R, S)，首先判断S的范围，是否在之内，如果不在，验签失败。

然后，我们验证

是否相等，如果相等，则验签成功。

这里，我们简单验证一下正确性吧，我们有

所以，这个是正确的。

总结

我们只是改了椭圆曲线对应的曲线，就得到了不同的结果，当然，曲线的选择还有很多，后面我们有机会再聊。快乐的时光过得特别快，又到了说再见的时候了，咱们下次再见。

参考资料

1. https://en.wikipedia.org/wiki/Montgomery_curve
2. https://en.wikipedia.org/wiki/EdDSA
3. https://en.wikipedia.org/wiki/Curve25519