椭圆曲线
Weierstrass 定义
椭圆曲线的一种定义是,在
要求
运算
在椭圆曲线上,可以定义点之间的加法运算,满足:
- 单位元
为无穷远点 - 对于曲线上两点
和 ,取经过 和 的直线,这条直线与椭圆曲线相交于最多三个点(因为方程是三次的),其中两个点是 和 ,如果第三个点存在且不和 、 重合,记第三个点为 ,那么满足 ,也就是 - 对一点
,其相反数 ,也就是沿 X 轴对称的点
下面来推导一下
带入椭圆曲线方程,得到
因为
两个方程的系数相同,则
即
如果
- 如果
,也就是 ,此时 连的直线是椭圆曲线在 点的切线,切线上的斜率的计算方法是,对椭圆曲线方程两侧对 求导,得到 ,因此斜率 ,剩下的计算过程和上面一样。 - 如果
,根据椭圆曲线的对称性,那么 ,此时 。
这部分推导参考了 Wikipedia。
除了加法以外,还可以定义数乘:整数
有限域上的椭圆曲线
从上面的观察可以发现,在计算两点间的加法运算的时候,对 X Y 坐标的计算只涉及到了加减乘除。因此,可以把椭圆曲线的坐标换到其他域上,而不局限于上面使用的
例如在椭圆曲线密码学中常用的 secp192r1 曲线,就是在素数域上定义的椭圆曲线:
此时除法运算定义为在素数域上乘以乘法逆元的运算。
Montgomery curve
在椭圆曲线密码学中,有时候会用 Montgomery curve 来描述椭圆曲线,而不是上面的 Weierstrass form。它的形式如下:
满足
例如 Curve25519 就是一个在素数域上的 Montgomery curve:
使用 Montgomery curve 的好处是能够实现更快的运算。
Montgomery 曲线可以转换为 Weierstrass 曲线,下面给出转换过程:
考虑到 Montgomery 相比 Weierstrass 左侧多了一个
此时距离 Weierstrass form 就差等式右边的
此时
这部分推导参考了 Wikipedia。
Twisted Edwards curve
第三种椭圆曲线的描述方法是 Twisted Edwards curve,定义如下:
Twisted Edwards curve 的点的加法如下:
点可以用齐次坐标表示:
Twisted Edwards curve 可以用在 EdDSA 签名算法中。