跳转至

椭圆曲线

Weierstrass 定义

椭圆曲线的一种定义是,在 R2 上的曲线,曲线上每一点 (x,y) 满足:

y2=x3+ax+b

要求 4a3+27b20,这种形式叫做 Weierstrass form。

运算

在椭圆曲线上,可以定义点之间的加法运算,满足:

  • 单位元 O 为无穷远点
  • 对于曲线上两点 PQ,取经过 PQ 的直线,这条直线与椭圆曲线相交于最多三个点(因为方程是三次的),其中两个点是 PQ,如果第三个点存在且不和 PQ 重合,记第三个点为 R,那么满足 P+Q+R=O,也就是 P+Q=R
  • 对一点 R=(xP,yP),其相反数 R=(xP,yP),也就是沿 X 轴对称的点

下面来推导一下 P Q R 三点间的坐标关系。设 P=(xP,yP),Q=(xQ,yQ),R=(xR,yR),首先假设 xPxQ,那么经过 P Q 的直线的方程为

y=kx+b

带入椭圆曲线方程,得到

(kx+b)2=x3+ax+bk2x2+2kbx+b2=x3+ax+bx3k2x22kbx+ax+bb2=0

因为 P Q R 是曲线与直线相交的三点,上式等价于

(xxP)(xxQ)(xxR)=x3(xP+xQ+xR)x2+(xPxQ+xQxR+xRxP)xxPxQxR

两个方程的系数相同,则

k2=xP+xQ+xRxR=k2xPxQk=yPyQxPxQxR=(yPyQxPxQ)2xPxQyR=yP+k(xRxP)

R=((yPyQxPxQ)2xPxQ,yP+yPyQxPxQ((yPyQxPxQ)2xPxQxP))。由于 P+Q=R,所以椭圆曲线上点的加法在 xPxQ 时运算结果为

(xP,yP)+(xQ,yQ)=((yPyQxPxQ)2xPxQ,yPyPyQxPxQ((yPyQxPxQ)2xPxQxP))

如果 xP=xQ,那么分情况讨论:

  1. 如果 yP=yQ,也就是 P+Q,此时 PQ 连的直线是椭圆曲线在 P 点的切线,切线上的斜率的计算方法是,对椭圆曲线方程两侧对 x 求导,得到 2ydydx=3x2+a,因此斜率 k=3xP2+a2yP,剩下的计算过程和上面一样。
  2. 如果 yPyQ,根据椭圆曲线的对称性,那么 yP=yQ,此时 P+Q=O

这部分推导参考了 Wikipedia

除了加法以外,还可以定义数乘:整数 n 乘以点 P,实际上就是求 nP 的和。

有限域上的椭圆曲线

从上面的观察可以发现,在计算两点间的加法运算的时候,对 X Y 坐标的计算只涉及到了加减乘除。因此,可以把椭圆曲线的坐标换到其他域上,而不局限于上面使用的 R。例如在密码学中,通常会使用 Fp 素数域或者 GF(2m)。例如取素数域 Fp 上的椭圆曲线,那么点的坐标满足

y2x3+ax+b(modp)

例如在椭圆曲线密码学中常用的 secp192r1 曲线,就是在素数域上定义的椭圆曲线:

p=6277101735386680763835789423207666416083908700390324961279a=p3b=2455155546008943817740293915197451784769108058161191238065

此时除法运算定义为在素数域上乘以乘法逆元的运算。

Montgomery curve

在椭圆曲线密码学中,有时候会用 Montgomery curve 来描述椭圆曲线,而不是上面的 Weierstrass form。它的形式如下:

By2=x3+Ax2+x

满足 B(A24)0

例如 Curve25519 就是一个在素数域上的 Montgomery curve:

y2x3+486662x2+x(modp)p=225519

使用 Montgomery curve 的好处是能够实现更快的运算。

Montgomery 曲线可以转换为 Weierstrass 曲线,下面给出转换过程:

考虑到 Montgomery 相比 Weierstrass 左侧多了一个 B 的因子,采用变量代换把它消除,

By2=x3+Ax2+xu=xBv=yBB(vB)2=(uB)3+A(uB)2+uBv2=u3+ABu2+1B2u

此时距离 Weierstrass form 就差等式右边的 u 的次数,目标是 x3+ax+b,现在是 x3+ax2+x,因此要把 x2 项消掉,设 u=tA3B,则

v2=u3+ABu2+1B2uu=tA3Bv2=(tA3B)3+AB(tA3B)2+1B2(tA3B)v2=t3+3A23B2t+2A39A27B3

此时 (v,t) 就是符合 Weierstrass form 椭圆曲线上的一点。

这部分推导参考了 Wikipedia

Twisted Edwards curve

第三种椭圆曲线的描述方法是 Twisted Edwards curve,定义如下:

ax2+y2=1+dx2y2

Twisted Edwards curve 的点的加法如下:

(x1,y1)+(x2,y2)=(x1y2+y1x21+dx1x2y1y2,y1y2ax1x21dx1x2y1y2)

点可以用齐次坐标表示:(X,Y,Z,T) 对应 (x,y) 满足 x=X/Z,y=Y/Z,xy=T/Z

Twisted Edwards curve 可以用在 EdDSA 签名算法中。

评论