从线圈到曲线–椭圆曲线密码学入门

椭圆曲线在现代密码协议中似乎无处不在，并且可能在今年12月下旬再次出现。让我们借此机会深入了解它们是什么以及为什么使用它们。

众所周知，素数对密码学很重要，尽管并非总是如此。素数的出现伴随着将近50年前的几篇开创性论文。引入非对称密码学的先驱Whit Witt Diffie，Martin Hellman，Ron Rivest，Adi Shamir和Leonard Adleman利用数论的结果来构建密钥协议，加密和签名。质数在数论中占有非常特殊的位置，这一直延续到密码学中。

加密协议通常以某些素数p为模。这可以比喻为将数字线变成一个线圈，使得0，p，2p等都在同一位置连接。从那时起，每当我们对数字进行加法或乘积运算以使我们超过p时，我们都可以根据需要简单地删除p的倍数，直到我们再次介于0和p之间。

现在，假设我们改为使用一个复合数字，例如12。那么0和12是相同的。在这种情况下，但这也意味着3乘以4就是... 0！处理普通数字的一种直觉是，如果ab = 0，则a或b必须为0。因此，当使用复合数字时，有些东西将不再像以前那样工作。幸运的是，使用素数（例如7）作为我们的所谓模数时，情况并非如此。

让我们制定一条规则，并称之为m。我们从数字线上取下刚制成的线圈，由于我们总是可以将数字减小到p以下，因此我们将该圆上的点标记为从0到p-1。给定圆上的两个点a和b，我们认为规则m（a，b）的输出应该是乘积ab表示的点，可能是在减少了模p之后。它看起来像是很自然的规则，但这仍然是我们刚刚同意的规则。如果您稍微遵循此规则，则会发现一些属性：

对于任何不等于0的a，b，m（a，b）永远不会为零。因此，如果我们从圆中完全删除0，就不会造成伤害-该规则仍然是明确定义的。

对于任何非零的a，总会有一些b使得m（a，b）= 1。

这些漂亮的属性以及称为“关联性”的属性是我们进行密码计算所需的属性。

现在，将重点放在圆圈上的特定数字上，我们称之为g。如果取m（g，g）或-返回更常用的表示法-g²，我们将在圆上到达新的点。我们可以继续该过程并计算g³，g⁴等。在某个点上，我们将达到1。在此过程中，我们访问的所有点都是g生成的数字集的成员，并且如果coil是一个很大的素数，那么我们有一个很好的候选人来进行加密，例如Diffie-Hellman密钥交换。令h是g生成的该集合中的某个数字。这意味着对于某些指数e，h =gᵉ。如果很容易从g和h中找到这个e，我们将遇到麻烦。幸运的是，事实证明，如果我们使用足够大的素数，那么很难找到这个e。

汇总数字行并不是找到适合密码学的原语的唯一方法。让我们制定一条新规则。与其使用上一节中的圆形，不如考虑以下方程式：

如果我们在通常的坐标系中绘制图形，则它可能看起来像这样的曲线：

现在，我们将就如何组合此曲线上的两个不同点P和Q制定一条规则。商定的表示法是称此规则加法，但是我们必须定义我们的意思。编程语言通常将这种思想概念包括为操作重载。画出P和Q之间的直线。它将在第三点相交，例如R。这可能是P + Q的不错选择，但是由于我们正在制定规则，因此让我们变得更加有趣。在R上画一条垂直线。它将与x轴另一侧的曲线相交，我们将此点定义为P +Q。像以前一样，这是我们现在和现在要决定的规则。但是，这实际上也是一条非常有用的规则，具有与以前相同的属性：

而不是将点1放在圆上，我们想象一个点无限远。 （记住在看铁轨时所看到的：平行线实际上在无限远处相交超出了地平线。）因此，现在与R和P + Q相交的线确实也与第三点相交：无限点。可以很精确地做到这一点，但是需要代数几何进行数学运算，这远远超出了本博客文章的范围。无穷大点具有与上述1相同的所有属性。

对于曲线上的任何点S，总会有一个点T，这样我们就得到了一条与S，T和无穷大点相交的线。这意味着对于任何点S，我们都可以找到可以称为-S的点。

我们只是假设P和Q是不同的。如果P = Q，则我们仅使用点P处的曲线的切线，然后像以前一样进行。

特别是，取一个点G，然后计算2 G = G + G，3 G，4 G等。最终，我们到达无穷大点，然后回到G。我们现在已经花了大约1000个单词来写博客到达这里后，只是要做与我们上面相同的事情，这有什么意义？上面我们说过，如果素数足够大，计算指数是安全的。事实证明，＆＃34;足够大＆＃34;目前大约为3072位，或者是大约925位的数字。即使对于计算机来说，这也有些费劲，但是椭圆曲线版本仅要求我们处理256位或77位数字，效率更高。

Diffie-Hellman密钥交换协议今天已被广泛使用，并且使用椭圆曲线进行实例化已被评为TLS和SSH等现代加密协议中的最佳选择。该协议非常简单。公共信息是椭圆曲线E和该曲线上各点的生成器G。一方爱丽丝（Alice）对一个随机整数a采样并计算点A = aG。另一方鲍勃（Bob）对一个随机整数b进行采样并计算B = bG。然后他们交换值A和B，并计算共享密钥。 K = b A = a B = abG。只要a和b都保持秘密，即使攻击者知道G，A和B，那么密钥也是安全的。

为了获得长期安全性，并在事后泄露某人的秘密密钥的情况下保护先前的消息，Alice和Bob可以在每次通信时进行临时密钥交换。如果a和A是Alice的长期密钥对，而A对所有人都是公共的，而Bob则相似，则他们可以运行以下协议来达成一次性会话密钥。爱丽丝对随机整数c进行采样并计算C = c G，鲍勃对随机整数d进行采样并计算D = dG。然后他们交换C和D，并将共享密钥计算为（a b + c d）G。

有兴趣的读者可以查看一下用Go编写的简单示例。您是否能够代表Alice和Bob将基本协议扩展到临时密钥交换？

最后，我们指出该协议容易受到中间人攻击，并且我们还需要发送对消息计算得出的签名，以确保通信是真实的。不使用签名时，您是否能够如上所述攻击协议？如果您发现这些问题很有趣，我们建议您在cryptohack.org上检查类似的挑战。

并非所有的椭圆曲线都适合加密。选择曲线和可分辨的基点也可能很有用。因此，实现倾向于在少量的众所周知的曲线中进行选择。美国国家标准技术研究院保留了推荐曲线的列表；其中P-256可能是最受欢迎的。

其中，还有Dan Bernstein和Tanja Lange提出的SafeCurves系列。 特别是，他们的Curve25519已被证明是受欢迎的选择。