椭圆曲线密码学(ECC)原理

1.椭圆曲线的定义

满足以下形式二元三次方程的点集

y 2 + a x y + b y = x 3 + c x 2 + d x + e ( 其 中 a , b , c , d 是 实 数 ) y^2+axy+by=x^3+cx^2+dx+e (其中a,b,c,d是实数) y2+axy+by=x3+cx2+dx+e(其中a,b,c,d是实数)

称为椭圆曲线。
ECC中最常用的椭圆曲线方程是：

y 2 = x 3 + a x + b ( a , b ∈ G F ( p ) , 4 a 3 + 27 b 2 ≠ 0 ) y^2=x^3+ax+b(a,b \in GF(p), 4a^3+27b^2 \ne 0) y2=x3+ax+b(a,b∈GF(p),4a3+27b2​=0)

以下是两个椭圆曲线的例子。

2.有限域上的椭圆曲线

密码学专注于离散的数学，而上面介绍的椭圆曲线是连续的。我们想把椭圆曲线及其加法应用于密码学，需要在整数集上讨论椭圆曲线 的点集。
设 E p ( a , b ) E_p(a, b) Ep​(a,b)表示椭圆曲线 y 2 = x 3 + a x + b y^2=x^3+ax+b y2=x3+ax+b上的点集，则求解 E p ( a , b ) E_p(a,b) Ep​(a,b)上的点集的步骤如下：
(1) 对区间 [ 0 , p ) [0,p) [0,p)中的每个正整数 x x x，计算 x 3 + a x + b   ( mod  p ) x^3+ax+b\ (\text{mod} \ p) x3+ax+b (mod p)
(2) 对区间 [ 0 , p ) [0,p) [0,p)中的每个正整数 y y y，计算 y 2   ( mod  p ) y^2 \ (\text{mod} \ p) y2 (mod p)
(3) 看以上两个计算结果是否相等(即 x 3 + a x + b ≡ y 2  mod  p x^3+ax+b\equiv y^2 \ \text{mod} \ p x3+ax+b≡y2 mod p)，如果相等(存在同余关系)，则 ( x , y ) (x,y) (x,y)是椭圆曲线上的点，否则不是。、
例. E 11 ( 1 , 6 ) E_{11}(1,6) E11​(1,6)表示椭圆曲线 y 2 = x 3 + x + 6 y^2=x^3+x+6 y2=x3+x+6，则点集 E 11 ( 1 , 6 ) E_{11}(1,6) E11​(1,6)如下表：

(2,4)	(2,7)	(3,5)	(3,6)	(5,2)	(5,9)
(7,2)	(7,9)	(8,3)	(8,8)	(10,2)	(10,9)

说明：
2 3 + 2 + 6 ( mod  11 ) = 5 2^3+2+6(\text{mod} \ 11)=5 23+2+6(mod 11)=5
4 2 ( mod  11 ) = 5 4^2(\text{mod} \ 11)=5 42(mod 11)=5
7 2 ( mod  11 ) = 5 7^2(\text{mod} \ 11)=5 72(mod 11)=5

3.椭圆曲线上的加法法则

在椭圆曲线 E E E上定义"加"的运算：假设有两个点 P P P, Q Q Q则 P P P与 Q Q Q的和 P ⊕ Q P\oplus Q P⊕Q由如下步骤得到：
连接 P Q PQ PQ两点形成直线，这条直线交椭圆曲线 E E E于 R R R点，则 R R R点关于 x x x轴的对称点 R ′ R' R′就是 P ⊕ Q P\oplus Q P⊕Q的运算结果。

当 P P P、 Q Q Q两点重合时，微积分的知识告诉我们，此时直线 P Q PQ PQ成为椭圆曲线 E E E的切线，亦即作曲线在 P P P点的切线交曲线于另一点 R R R， R R R关于 x x x轴的对称点 R ′ R' R′即为 P ⊕ P P\oplus P P⊕P的值。

例. 假设椭圆曲线 E E E方程为 y 2 = x 3 − 15 x + 8 y^2=x^3-15x+8 y2=x3−15x+8， P P P点坐标为 ( 7 , 16 ) (7,16) (7,16)， Q Q Q点坐标 ( 1 , 2 ) (1,2) (1,2)，在这条曲线上计算 ( 7 , 16 ) ⊕ ( 1 , 2 ) (7,16) \oplus (1,2) (7,16)⊕(1,2)。
首先获取这条直线 P Q PQ PQ斜率为

λ = y P − y Q x P − x Q = 7 3 \lambda=\frac{y_P-y_Q}{x_P-x_Q}=\frac{7}{3} λ=xP​−xQ​yP​−yQ​​=37​

从而得到直线 P Q PQ PQ的表达式：

P Q : y = 7 3 x − 1 3 PQ:y= \frac{7}{3}x-\frac{1}{3} PQ:y=37​x−31​

将其与曲线方程 y 2 = x 3 − 15 x + 8 y^2=x^3-15x+8 y2=x3−15x+8联立消去 y y y可得关于x的方程：

x 3 − 49 9 x 2 − 121 9 x + 161 9 = 0 x^3-\frac{49}{9}x^2-\frac{121}{9}x+\frac{161}{9}=0 x3−949​x2−9121​x+9161​=0

不需要硬解该方程，因为我们知道这个方程必有两根 x 1 = 7 x_1=7 x1​=7, x 2 = 1 x_2=1 x2​=1，因此该方程等价于

( x − 1 ) ( x − 7 ) ( x − x 3 ) = 0 (x-1)(x-7)(x-x_3)=0 (x−1)(x−7)(x−x3​)=0

观察两式一次项不难得到

− 7 x 3 = 161 9 -7x_3=\frac{161}{9} −7x3​=9161​

因此

x 3 = − 23 9 x_3=-\frac{23}{9} x3​=−923​

再将 x 3 x_3 x3​代入直线方程可得 y 3 = − 170 27 y_3=-\frac{170}{27} y3​=−27170​
即 ( 7 , 16 ) (7,16) (7,16)与 ( 1 , 2 ) (1,2) (1,2)的连线与曲线交点为 R ( − 23 9 , − 170 27 ) R(-\frac{23}{9},-\frac{170}{27}) R(−923​,−27170​)，因此

P ⊕ Q = R ′ = ( − 23 9 , 170 27 ) P \oplus Q=R'= (-\frac{23}{9},\frac{170}{27}) P⊕Q=R′=(−923​,27170​)

无穷远点
如果 P 、 Q P、Q P、Q两点本身关于 x x x轴对称，那么直线 P Q PQ PQ就不与曲线有第三个交点，此时规定 P ⊕ Q = 0 P \oplus Q=0 P⊕Q=0，即 P 、 Q P、Q P、Q在无穷远处相交，这里的" 0 0 0"就算无穷远点。
显然有 P + 0 = P P+0=P P+0=P，亦即无穷远点 0 0 0是加法运算的单位元。
同时注意到：
如果 P = ( x , y ) P=(x,y) P=(x,y)，那么 ( x , y ) ⊕ ( x , − y ) = 0 (x,y) \oplus (x,-y)=0 (x,y)⊕(x,−y)=0，即(x,-y)是 P P P的加法逆元，即 − P -P −P。

因此，对于一般情况，求椭圆曲线 E p ( a , b ) E_p(a,b) Ep​(a,b)上任意两点 P ( x 1 , y 1 ) , Q ( x 2 , y 2 ) P(x_1,y_1),Q(x_2,y_2) P(x1​,y1​),Q(x2​,y2​)之和 P ⊕ Q P \oplus Q P⊕Q的方法如下：
如果 y 1 + y 2 = 0 y_1+y_2=0 y1​+y2​=0则 P + Q = 0 ( 无 穷 远 点 ) P+Q=0(无穷远点) P+Q=0(无穷远点)
如果 y 1 + y 2 ≠ 0 y_1+y_2\ne 0 y1​+y2​​=0，则 P + Q = ( x 3 , y 3 ) P+Q=(x_3,y_3) P+Q=(x3​,y3​)由以下规则确定：

x 3 ≡ λ 2 − x 1 − x 2 ( mod  p ) x_3\equiv \lambda^2-x_1-x_2(\text{mod}\ p) x3​≡λ2−x1​−x2​(mod p)

y 3 = λ ( x 1 − x 3 ) − y 1 ( mod  p ) y_3=\lambda (x_1-x_3)-y_1(\text{mod}\ p) y3​=λ(x1​−x3​)−y1​(mod p)

其中

λ = { y 2 − y 1 x 2 − x 1 , P ≠ Q 3 x 1 2 + a 2 y 1 , P = Q \lambda=\left\{ \begin{aligned} \frac{y_2-y_1}{x_2-x_1}, P \ne Q \\ \frac{3x_1^2+a}{2y_1}, P=Q \end{aligned} \right. λ=⎩⎪⎪⎨⎪⎪⎧​x2​−x1​y2​−y1​​,P​=Q2y1​3x12​+a​,P=Q​

具体证明如下：
设直线 P Q PQ PQ为 y − y 1 = λ ( x − x 1 ) y-y_1=\lambda(x-x_1) y−y1​=λ(x−x1​)。将直线方程与曲线方程联立并消去 y y y得到

( λ x + y 1 − λ x 1 ) 2 = x 3 + a x + b (\lambda x+y_1-\lambda x_1)^2=x^3+ax+b (λx+y1​−λx1​)2=x3+ax+b

整理可得

x 3 − λ 2 x 2 + ( a + 2 λ 2 x 1 − 2 λ y 1 ) x + b − ( y 1 − λ x 1 ) 2 = 0 x^3-\lambda^2x^2+(a+2\lambda^2x_1-2\lambda y_1)x+b-(y_1-\lambda x_1)^2=0 x3−λ2x2+(a+2λ2x1​−2λy1​)x+b−(y1​−λx1​)2=0

由于直线和椭圆曲线已有两交点 ( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1),(x_2,y_2) (x1​,y1​),(x2​,y2​)，因此上式必有两根 x = x 1 , x = x 2 x=x_1,x=x_2 x=x1​,x=x2​，设第3根为 e 3 e_3 e3​，则上方程等价于

( x − x 1 ) ( x − x 2 ) ( x − e 3 ) = 0 (x-x_1)(x-x_2)(x-e_3)=0 (x−x1​)(x−x2​)(x−e3​)=0

由常数项相等可得

e 3 = ( y 1 − λ x 1 ) 2 − b x 1 x 1 e_3=\frac{(y_1-\lambda x_1)^2-b}{x_1x_1} e3​=x1​x1​(y1​−λx1​)2−b​

即

e 3 = y 1 2 − 2 λ x 1 y 1 + λ 2 x 1 2 − b x 1 x 2 e_3=\frac{y_1^2-2\lambda x_1y_1+\lambda^2x_1^2-b}{x_1x_2} e3​=x1​x2​y12​−2λx1​y1​+λ2x12​−b​

由于 y 1 2 = x 1 3 + a x 1 + b y_1^2=x_1^3+ax_1+b y12​=x13​+ax1​+b，即 b = y 1 2 − x 1 3 − a x 1 b=y_1^2-x_1^3-ax_1 b=y12​−x13​−ax1​，代入上式得

e 3 = x 1 3 + a x 1 − 2 λ x 1 y 1 + λ 2 x 1 2 x 1 x 2 = x 1 2 + a − 2 λ y 1 + λ 2 x 1 x 2 ( ∗ ) e_3=\frac{x_1^3+ax_1 -2\lambda x_1y_1+\lambda^2x_1^2}{x_1x_2}=\frac{x_1^2+a -2\lambda y_1+\lambda^2x_1}{x_2} (*) e3​=x1​x2​x13​+ax1​−2λx1​y1​+λ2x12​​=x2​x12​+a−2λy1​+λ2x1​​(∗)

而又有

y 1 2 = x 1 3 + a x 1 + b y_1^2=x_1^3+ax_1+b y12​=x13​+ax1​+b

y 2 2 = x 2 3 + a x 2 + b y_2^2=x_2^3+ax_2+b y22​=x23​+ax2​+b

两式相减得

y 1 2 − y 2 2 = x 1 3 − x 2 3 + a ( x 1 − x 2 ) y_1^2-y_2^2=x_1^3-x_2^3+a(x_1-x_2) y12​−y22​=x13​−x23​+a(x1​−x2​)

即

( y 1 + y 2 ) λ = x 1 2 + x 1 x 2 + x 2 2 + a (y_1+y_2)\lambda=x_1^2+x_1x_2+x_2^2+a (y1​+y2​)λ=x12​+x1​x2​+x22​+a

将该式中的 a a a代入 ( ∗ ) (*) (∗)式可得

e 3 = ( y 2 − y 1 ) λ − x 1 x 2 − x 2 2 + λ 2 x 1 x 2 ( ∗ ∗ ) e_3=\frac{(y_2-y_1)\lambda-x_1x_2-x_2^2+\lambda^2x_1}{x_2} (**) e3​=x2​(y2​−y1​)λ−x1​x2​−x22​+λ2x1​​(∗∗)

其中有 y 2 − y 1 = λ ( x 2 − x 1 ) y_2-y_1=\lambda(x_2-x_1) y2​−y1​=λ(x2​−x1​)，将其代入 ( ∗ ) (*) (∗)式得

e 3 = λ 2 x 2 − x 1 x 2 − x 2 2 x 2 = λ 2 − x 1 − x 2 e_3=\frac{\lambda^2x_2-x_1x_2-x_2^2}{x_2}=\lambda^2-x_1-x_2 e3​=x2​λ2x2​−x1​x2​−x22​​=λ2−x1​−x2​

即直线 P Q PQ PQ与椭圆曲线的第3个交点横坐标

x 3 = λ 2 − x 1 − x 2 x_3=\lambda^2-x_1-x_2 x3​=λ2−x1​−x2​

纵坐标为 λ ( x 3 − x 1 ) + y 1 \lambda(x_3-x_1)+y_1 λ(x3​−x1​)+y1​，而 P ⊕ Q P\oplus Q P⊕Q仍需作第3个交点关于 x x x轴的对称点，因此

y 3 = λ ( x 1 − x 3 ) − y 1 y_3=\lambda(x_1-x_3)-y_1 y3​=λ(x1​−x3​)−y1​

这不依赖于 P 、 Q P、Q P、Q两点是否重合。且上述运算都是在mod p的意义下进行。

4.椭圆曲线离散对数问题

椭圆曲线上的两个点P和Q，k为整数，Q=kP；
点P称为基点（base point）
k为私有密钥（private key）
Q为公开密钥（public key)

5. 椭圆曲线加解密

1、用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。
2、用户A选择一个私有密钥k，并生成公开密钥K=kG。
3、用户A将Ep(a,b)和点K，G传给用户B。
4、用户B接到信息后 ，将待传输的明文编码到Ep(a,b)上一点M（编码方法很多，这里不作讨论），并产生一个随机整数r（r<n)。
5、用户B计算点C1=M+rK；C2=rG。
6、用户B将C1、C2传给用户A。
7、用户A接到信息后，计算C1-kC2，结果就是点M。因为 C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M；再对点M进行解码就可以得到明文。

6. 拓展

椭圆曲线在Fp域上的加密（python实现）
ECC椭圆曲线密码学的原理、公式推导、例子、Python实现和应用
ECC椭圆曲线详解(有具体实例)
什么是椭圆曲线加密（ECC）？