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

admin
admin
admin
75799
文章
59
评论
2023年3月31日18:23:46评论16 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为不同类型有限域设计的另一种计数算法。

       

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究，若将其信息做其他用途，由用户承担全部法律及连带责任，本站不承担任何法律及连带责任，请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2023年3月31日18:23:46
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出)：
                  密码学 ｜ 6.2 有限域上的椭圆曲线 https://cn-sec.com/archives/1642306.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: