椭圆曲线(Elliptic Curve,EC) 的方程通常以 Weierstrass 形式表示为:

一些函数图像:

其中 满足 ,这是为了排除特殊曲线 1

椭圆曲线上的点加法可以通过几何构造来实现,也可以通过特定的算法来计算。

几何构造点加法 2

简单来说,如果直线与曲线交于 三点,定义

设有两个点 ,它们都在椭圆曲线上。要计算它们的和 ,可以按照以下步骤进行:

  1. 将直线通过点 和点 ,并延长直线,直到它与椭圆曲线相交于第三个点 。这条直线被称为割线。
  2. 在点 处,将割线与椭圆曲线相切。这条切线与椭圆曲线的交点被定义为点

通过这个几何构造,我们可以将点 和点 的加法转化为在椭圆曲线上的点的相交和切线的构造。

特殊情况:例如当点 和点 重合或者它们的切线与椭圆曲线相交于无穷远点 。在这种情况下,我们有

递推:这种方法可以用于计算多个点的和,从而实现椭圆曲线上的多倍点运算。通过重复应用点加法,我们可以计算出点的多倍点,例如 等。

时间复杂度太高,因为涉及到曲线和直线的相交计算。因此 ECC 中通常使用基于有限域上的数学运算的算法来实现点加法。

事实上,椭圆曲线与直线的交点可能不止三个,可能有两个,一个或者没有。

相切,则与给定的点 相交的直线有两个交点。视作三个点其二重合的情况。

没有交点,视作直线与曲线相交于无穷远点

不会出现四个交点的情况。

EC 上的 DLP

除了点加法之外,椭圆曲线还具有其他重要的性质,如离散对数问题的困难性。基于椭圆曲线的离散对数问题是指在椭圆曲线上找到满足 的整数 的计算困难性,其中 是已知点, 是待求点。

椭圆曲线展开了传统整数基础的公钥密码学的可能性,提供了更高效和安全的解决方案。它在现代密码学中被广泛应用,为许多安全协议和应用提供了强大的安全性和高效性。

EC 上的群

在椭圆曲线密码学中,椭圆曲线上的是通过曲线上的点以及无穷远点(记为 ,也称为“单位元”或“群的零元”)来定义的。这个群的操作通常被称为“点加”,定义如下:

  1. 单位元

    • 无穷远点 是群的单位元,对于任何曲线上的点
  2. 逆元

    • 每个点 都有一个逆元,即 (在仿射坐标中)。这意味着
  3. 点加

    • 给定曲线上的两个点 ,如果 ,则可以找到第三个点 ,使得 。这是通过找到过 的直线,该直线将与曲线相交于第三个点 ,然后通过关于 轴的对称变换得到
  4. 点倍乘

    • 如果 ,则该操作称为点倍乘。这是通过找到点 处曲线的切线来完成的,该切线将与曲线再次相交于另一点 ,然后通过关于 轴的对称变换得到

这些操作遵循以下几何构造:

  • 相异点相加:对于曲线上的两个相异点 ,过这两点作一直线,该直线与椭圆曲线相交于第三点 。点 是点 关于 轴的对称点,定义
  • 点的加倍:对于曲线上的一个点 ,作该点的切线,该切线与椭圆曲线相交于一点 。点 是点 关于 轴的对称点,定义
  • 加法逆元:对于曲线上的点 ,其加法逆元是 。这意味着 ,其中 是无穷远点。

在实际应用中,如椭圆曲线密码学,通常使用的是椭圆曲线上的点的有限域上的群。在有限域上,所有的运算(包括点的加法和乘法)都是模一个质数 进行的,这意味着所有的坐标都是在这个有限域内,并且所有的算术运算(加、减、乘、乘方和求逆)都是模 的。

Footnotes

  1. 参考 https://code.wandoer.com/note/eccelliptic-curves-cryptography-%E6%A4%AD%E5%9C%86%E6%9B%B2%E7%BA%BF%E5%8A%A0%E5%AF%86%E5%8E%9F%E7%90%86.htm

  2. 参考 https://www.cnblogs.com/cbkj-xd/p/13384713.html