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

admin 2023年3月31日18:23:46评论37 views字数 2437阅读8分7秒阅读模式

6.2 Elliptic Curves over Finite Fields

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

椭圆曲线在 𝕡 下的点集(坐标集合)表示为

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

例 6.8

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

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

总共有九个元素。
现在假设  和  是 𝕡 中的两个点,并且我们想把点  和  加起来。一种可能是使用 𝕡 而不是  来拓展几何理论。然后我们可以模仿我们以前的构造来定义 。这就产生了一个迷人的数学领域,称为代数几何。然而,为了简洁起见,我们使用定理 6.6 中给出的显式公式来对 𝕡 中的点进行求和。但我们注意到,如果想要对椭圆曲线的理论有更深入的理解,那么就需要使用代数几何的一些机制和形式。
设 和 =, 是  中的点。我们将和  定义为通过应用椭圆曲线加法算法(定理6.6)获得的点 。注意,在该算法中,使用的唯一操作是加法、减法、乘法和除法,涉及  的系数以及  和  的坐标。由于这些系数和坐标在 𝕡 中,我们最终得到一个坐标在 𝕡 下的点。当然,我们还并不清楚点  是否真的在 𝕡 中。
定理 6.9  设  为 𝕡 下的椭圆曲线,具有点 
  1. 使用定理 6.6 的算法对点  进行求和会得到 𝕡 下的一个点,该点定义为 
  2. 在 𝕡 下的加法也满足定理 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为不同类型有限域设计的另一种计数算法。

       

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2023年3月31日18:23:46
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   密码学 | 6.2 有限域上的椭圆曲线https://cn-sec.com/archives/1642306.html

发表评论

匿名网友 填写信息