椭圆曲线定义
椭圆曲线加密算法(Elliptic curve cryptography)简称 ECC, 是一种非对称加密算法。方程式为
y2=x3+ax+b, 4a3+27b2=0
不同的参数 a 和 b 会产生不同的曲线,如下图所示
从图中可以看出,椭圆曲线关于 X 轴对称。
需要注意的是 a 和 b 须满足条件 4a3+27b2=0, 这个条件确保了曲线的光滑, 即曲线中不存在尖点,自相交点和孤立点, 从而保证曲线上的点都有切线。
加法运算
椭圆曲线的加法运算指曲线上的两个点相加得到第三个点的过程。有几种不同的情况:
点加
已知椭圆曲线上的点 P 和点 Q, 过这两点做直线,与椭圆曲线相交于第三个点 R, R 关于 X 轴的对称点 R′ 就是 P 和 Q 相加的结果, 即 P+Q=R′
假设 P=(x1,y1), Q=(x2,y2), 点 P 和 Q 所在直线的斜率是 m=x2−x1y2−y1,
根据点斜式方程 y−y1=m(x−x1), 得到直线方程 y=m(x−x1)+y1
椭圆曲线方程与直线方程联立:
(m(x−x1)+y1)2=x3+ax+bm2(x−x1)2+2y1m(x−x1)+y12=x3+ax+bm2(x2−2xx1+x12)+2y1m(x−x1)+y12=x3+ax+bm2x2−2xx1m2+m2x12+2y1mx−2y1mx1+y12=x3+ax+bx3+ax+b−m2x2+2xx1m2−m2x12−2y1mx+2y1mx1−y12=0x3−m2x2+(a+2x1m2−2y1m)x+(b−m2x12+2y1mx1−y12)=0
对于三次方程x3+px2+qx+r=0, 根据韦达定理,其根 x1,x2,x3 满足 x1+x2+x3=−p
根据推导 p=m2, 故 x3=m2−x1−x2, 代入得到 y3=m(x3−x1)+y1
最终 R′=(x3,−y3)=(m2−x1−x2,m(x1−x3)−y1)
点倍乘
当 P=Q 时,相当于过点 P 做曲线的切线,相交于点R, R 关于 X 轴的对称点 R′ 就是相加得到的点。 P+P=2P=R′
应用隐函数求导计算切线斜率 m=2y13x12+a, 其余部分的计算同上。
逆元
当 Q=−P 时,即 Q 是 P 在椭圆曲线上关于 X 轴的对称点,此时过这两点做直线。没有相交的第三个点。则 P+Q=P+(−P)=O
点 O 是一个无穷远点,也叫加法的单位元。曲线上任意点与单位元相加都等于其自身。 P+O=P
有限域椭圆曲线
在实数域上的椭圆曲线具有连续性的, 这种连续性并不适用于安全加密。采用取模的方式将椭圆曲线的运算结果固定在一个范围内变成离散的点。
椭圆曲线上的坐标 x 和 y 都是整数, 取值在包含有限个元素的有限域中, 记作GF(p) 或 Fp, 其中 p 是素数。
例如 F5={0,1,2,3,4}, 表示 x 和 y 坐标的值只能是 {0,1,2,3,4} 中的一个。
取模 p 的有限域椭圆曲线方程为 y2=x3+ax+bmodp, 记作 Ep(a,b)。例如: E5(1,1):y2=x3+x+1mod 5
计算有限域椭圆曲线上的点时, 首先是确定 p 的值。然后通过 x 的值计算 y 的值,如果 y 的值不在 0 到 p−1 之间, 则为无效点。
例如 E5(1,1):y2=x3+x+1mod 5,F5={0,1,2,3,4},
由于 x 和 y 的取值是在有限域中整数,因此对于上式中有多个可组合的点:
- x=0,y=1, 等式两边值为 y2=1 和 x3+x+1=1, 各对 5 取模结果都为 1, 该点有效
- x=0,y=2, 等式左边对 5 取模结果为 4, 等式右边对 5 取模结果为 1, 该点无效
- x=0,y=4, 等式两边对 5 取模结果都为 1, 该点有效
如此遍历下去,便能确定最终的有效点为(0,1) (0,4) (2,1) (2,4), (3,1) (3,4) (4,2) (4,3)
从图中可以看出, 相同 x 坐标, 会有一个关于 2p 的对称点。并且相同 x 坐标的 y 坐标值一个是奇数一个是偶数。
点加
有限域椭圆曲线的点加是椭圆曲线密码学的核心。
已知点 P(x1,y1) 和点 Q(x2,y2) 是有限域椭圆曲线上的两个点, 计算这两个点的和 P+Q 的步骤如下:
计算斜率 m=x2−x1y2−y1mod p, 如果 P=Q,则 m=2y13x12+amod p
在实数域上的椭圆曲线加法, 需要计算 P 和 Q 连接的直线与椭圆曲线的交点 R, 在有限域椭圆曲线上同理。
假设有限域椭圆曲线E127(−1,3):y2=x3−x+3mod 127
点P=(16,20), 点Q=(41,120) 求 P+Q 的坐标点R′(x′,y′)
首先计算连接P 和 Q 直线的斜率m=xP−xQyP−yQmod p=16−4120−120mod 127=4mod 127=4
接着计算直线和曲线相交的第三个点的坐标R(x,y), 按照之前推导的公式:
xR=m2−xP−xQmod p=16−16−41mod 127=−41mod 127=86
yR=m(xR−xP)+yPmod p=4(86−16)+20mod 127=300mod 127=46
R′ 是 R 关于 X 轴的对称点,所以
xR′=xR=86, yR′=−yRmodp=−46mod127=81
所以 P+Q=(86,81)
点倍乘
在实数域中的乘法定义为:nP=P+P+⋯+P, 对P逐次累加计算。在有限域中同样可以这样计算。
但在有限域中椭圆曲线中的乘法会存在一个循环。
例如: 有限域椭圆曲线E97(2,3):y2=x3+2x+3mod 97 和点P(3,6)
- 1P=(3,6)
- 2P=P+P=(80,10)
- 3P=2P+P=(80,87)
- 4P=3P+P(3,91)
- 5P=4P+P=O
- 6P=5P+P=(3,6)
- 7P=6P+P=(80,10)
- ⋯
点P(3,6) 的循环次数为 5, 以及循环计算得到的点集称循环子群。该点集的数量就叫做阶。即 5 是点P(3,6)的阶。
另一种更简单的计算方式是:
- 计算椭圆曲线的阶 N (N 是有限域上椭圆曲线的有效点的数量)
- 找出 N 的所有因子
- 对每个因子计算 nP
- 找到最小的且满足 nP=O 的 n, n 就是该点的阶
对于椭圆曲线E37(−1,3):y2=x3−x+3mod 37
共有 42 个点,因此 N=42。42 的因子有 1,2,3,6,7,14,21,42 依次与点P(2,3) 相乘
1P=O,2P=O,⋯,7P=O, 因此 P 的阶是 7。
公私钥
在椭圆曲线加密算法中,给定椭圆曲线 E 和 曲线上的基点 G。 计算出 G 的阶为 n, 之后在{1,⋯,n−1} 中随机选择一个整数 k 作为私钥,公钥H=kG。H 为曲线上的一个有效点。
在已知 H 和 G 的情况下,计算 k 是非常困难的。因为计算 k 并不能用简单的线性运算 k=GH 求出结果。
H 是 k 个 G 相加的结果, 这种加法的计算并不是简单的代数运算。如果直接给出一个点 H, 无法直接计算是由多少 k 个 G 点相加的结果。只能从 1G,2G,3G,... 如此不断地尝试, 直到结果等于 H, 才能得到 k。
当 k 是一个很大的数时, 这个过程的难度将变的非常大, 即使以现在最快的计算机, 尝试所有可能的 k 值也需要远超过宇宙年龄的时间。 这也是为什么 ECC
安全性高的原因。