密码学｜ 6.2 有限域上的椭圆曲线

密码学 1年前 (2023) admin

352 0 0

6.2 Elliptic Curves over Finite Fields

在上一节中，我们研究了椭圆曲线的几何理论。例如，椭圆曲线上两个不同点、的和是通过绘制连接、的直线，然后找到和相交的第三点来定义的，如图6.2 所示。然而，为了将椭圆曲线理论应用于密码学，我们需要研究在有限域中具有坐标的椭圆曲线。这并不复杂。

定义设为一个素数，在中的椭圆曲线满足如下等式

椭圆曲线在下的点集（坐标集合）表示为

注 6.7 实际上上的椭圆曲线在密码学中非常重要，但它们需要更复杂的方程，因此我们将其推迟到 6.7 一节再进行讨论。

例 6.8

考虑在上的椭圆曲线，通过遍历，然后判断数值在模下是否为一个二次剩余来确定的所有坐标。例如，设，我们得到，在模下不是一个二次剩余，于是我们继续尝试，我们得到，而在模下是一个二次剩余，实际上它有两个根

因此我们得到的两个坐标。继续计算我们就能够获得整个集合

总共有九个元素。

现在假设和是中的两个点，并且我们想把点和加起来。一种可能是使用而不是来拓展几何理论。然后我们可以模仿我们以前的构造来定义。这就产生了一个迷人的数学领域，称为代数几何。然而，为了简洁起见，我们使用定理 6.6 中给出的显式公式来对中的点进行求和。但我们注意到，如果想要对椭圆曲线的理论有更深入的理解，那么就需要使用代数几何的一些机制和形式。

设和是中的点。我们将和定义为通过应用椭圆曲线加法算法（定理6.6）获得的点。注意，在该算法中，使用的唯一操作是加法、减法、乘法和除法，涉及的系数以及和的坐标。由于这些系数和坐标在中，我们最终得到一个坐标在下的点。当然，我们还并不清楚点是否真的在中。

定理 6.9 设为下的椭圆曲线，具有点

使用定理 6.6 的算法对点进行求和会得到下的一个点，该点定义为
在下的加法也满足定理 6.5 列出的所有性质。换句话说，加法法则使得成为一个有限群。

证明

定理中的公式是通过将一条直线的方程式代入的方程式并求解而导出的，因此所得的点自然为上的一个点，即，它是定义的方程式的解。这说明了为什么是正确的，尽管当时，需要一个小的附加参数来说明为什么所得的三次多项式具有两个根。

对于，同一律则来自加法算法步骤和；求逆运算法则来自加法运算步骤，并且交换律也很容易得到，因为根据加法算法，切换两个点的位置并不影响计算结果。不幸的是，结合律并不那么明确。虽然有许多特殊情况需要考虑，但可以直接使用加法算法公式来验证结合律。另一种方法是发展更多椭圆曲线的一般理论，如定理 6.5 证明中引用的参考文献所述。

例 6.10 继续使用上的椭圆曲线，如例 6.8，我们使用对运用加法算法（定理6.6），根据步骤 5，我们首先计算

（所用的运算都是在下进行的），然后我们计算

最后，根据加法法则，我们有

于是我们得到

同样的，我是使用加法运算对加上自己，（记住所有的运算都是在下的，我们首先计算

然后

所以，所有的可能计算结果都列在了表 6.1 中。

密码学｜ 6.2 有限域上的椭圆曲线

table 6.1 Addition table for E over Y^2 = X^3 +3X + 8 over F_13

很显然椭圆曲线的点组成一个有限集合，因为在有限域下，椭圆曲线只有有限种坐标和坐标。更准确的是，对于只有种可能，并且对于，式子表明最多有两个可能的，因此，再额外加上一个无穷远点，椭圆曲线最多有个点。但这个估计的点的数量，显然要比实际上点的数量要多。

当我们给赋值，对于有三种可能，首先，它可能是模下的一个二次剩余，即可以找到两个二次根，我们也就得到了下的两个点。该事件有 50% 的发生概率。第二，它不是模下的一个二次剩余，于是我们就要放弃这样的一个，这个事件发生的概率也是 50%。第三，它可能是 0，于是我们可以得到一个下的点，但这个事件发生的概率非常的小。因此我们对椭圆曲线的点的数量的期望是

这是Hasse的一个著名定理，后来被Weil和Deligne广泛推广，说这对随机波动是正确的。

定理 6.11 （Hasse） 设为定义在上的椭圆曲线，那么有

定义

定理 6.11 中的，我们定义其为的 trace of Frobenius，这里我们就不解释这个名称的由来了，只是说是某个的矩阵的迹，该矩阵在与相关的某个二维向量空间上充当线性变换。

例 6.12 设有椭圆曲线，对于不同的有限域，我们可以将视为上的椭圆曲线，并计算中的点数。表6.2 列出了前几个素数的结果，以及的值，为了进行比较，还列出了的值。

密码学｜ 6.2 有限域上的椭圆曲线

Table 6.2: Number of points and trace of Frobenius for E : Y 2 = X3 + 4X + 6

注 Hasse定理（定理6.11）给出了的界，但它没有提供计算这个量的方法。原则上，可以遍历的值，并检查的值是否为二次剩余，但这需要时间，因此效率很低。Schoof 在《Elliptic curves over finite fields and the computation of square roots mod p. Math.》描述了一种时间的算法，即，他找到了多项式时间算法。后来，Schof 算法得到了 Elkies和 Atkin 的改进，因此它现在被称为SEA算法。这里我们暂且不对SEA继续介绍，它使用了椭圆曲线理论中的先进技术，感兴趣的读者可参阅《Counting points on elliptic curves over finite fields》。另见第 6.7 节的注6.32，了解Satoh为不同类型有限域设计的另一种计数算法。