什么是椭圆曲线,想必大家都会首先想到的是高中时学到的标准椭圆曲线方程。
x
2
a
2
+
y
2
b
2
=
1
(
a
>
b
,
焦
点
在
x
轴
,
a
<
b
,
焦
点
在
y
轴
)
\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1 (a>b,焦点在x轴,a<b,焦点在y轴)
a2x2+b2y2=1(a>b,焦点在x轴,a<b,焦点在y轴)
一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程(Weierstrass)所有点的集合,
Y
2
Z
+
a
1
X
Y
Z
+
a
3
Y
Z
2
=
X
3
+
a
2
X
2
Z
+
a
4
X
Z
2
+
a
6
Z
3
Y^2Z+a_1XYZ+a_3YZ^2=X^3+a_2X^2Z+a_4XZ^2+a_6Z^3
Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3 对普通平面上点(x,y),令x=X/Z,y=Y/Z,Z≠0,得到如下方程
y
2
Z
3
+
a
1
x
y
Z
3
+
a
3
y
Z
3
=
x
3
Z
3
+
a
2
x
2
Z
3
+
a
4
x
Z
3
+
a
6
Z
3
y^2Z^3+a_1xyZ^3+a_3yZ^3=x^3Z^3+a_2x^2Z^3+a_4xZ^3+a_6Z^3
y2Z3+a1xyZ3+a3yZ3=x3Z3+a2x2Z3+a4xZ3+a6Z3 约掉
Z
3
Z^3
Z3可以得到:
y
2
+
a
1
x
y
+
a
3
y
=
x
3
+
a
2
x
2
+
a
4
x
+
a
6
y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6
y2+a1xy+a3y=x3+a2x2+a4x+a6
简化版的Weierstrass方程:
E
:
y
2
=
x
3
+
a
x
+
b
E: y^2= x^3+ax+b
E:y2=x3+ax+b 其中, (1)
Δ
=
−
16
(
4
a
3
+
27
b
)
≠
0
\Delta= -16(4a^3+27b) \neq 0
Δ=−16(4a3+27b)=0 ,用来保证曲线是光滑的,即曲线的所有点都没有两个或者两个以上的不同的切线。 (2)
a
,
b
∈
K
,
K
为
E
的
基
础
域
。
a,b\in K, K为E的基础域。
a,b∈K,K为E的基础域。 (3) 点
O
∞
O_\infty
O∞ 是曲线的唯一的无穷远点。
Fp的加法是
a
+
b
≡
c
(
m
o
d
p
)
a+b\equiv c \pmod p
a+b≡c(modp)
Fp的乘法是
a
×
b
≡
c
(
m
o
d
p
)
a×b \equiv c \pmod p
a×b≡c(modp)
Fp的除法是
a
÷
b
≡
c
(
m
o
d
p
)
,
即
a
×
b
−
1
≡
c
(
m
o
d
p
)
,
b
−
1
也
是
一
个
0
到
p
−
1
之
间
的
整
数
,
但
满
足
b
×
b
−
1
≡
1
(
m
o
d
p
)
a÷b \equiv c \pmod p,即 a×b^{-1} \equiv c \pmod p,b^{-1}也是一个0到p-1之间的整数,但满足b×b^{-1}\equiv 1 \pmod p
a÷b≡c(modp),即a×b−1≡c(modp),b−1也是一个0到p−1之间的整数,但满足b×b−1≡1(modp)
Fp的单位元是1,零元是 0
Fp域内运算满足交换律、结合律、分配律
椭圆曲线Ep(a,b),p为质数,x,y∈[0,p-1]
y
2
=
x
3
+
a
x
+
b
(
m
o
d
p
)
y^2=x^3+ax+b \pmod p
y2=x3+ax+b(modp)
选择两个满足下列约束条件的小于p的非负整数a、b :
4
a
3
+
27
b
2
≠
0
(
m
o
d
p
)
4a^3 + 27b^2 \neq 0 \pmod p
4a3+27b2=0(modp)
Fp上的椭圆曲线同样有加法
1.无穷远点
O
∞
是
零
元
,
有
O
∞
+
O
∞
=
O
∞
,
O
∞
+
P
=
P
O_∞是零元,有O_∞+ O_∞= O_∞,O_∞+P=P
O∞是零元,有O∞+O∞=O∞,O∞+P=P 2.P(x,y)的负元是 (x,-y mod p)= (x,p-y) ,有
P
+
(
−
P
)
=
O
∞
P+(-P)= O_∞
P+(−P)=O∞ 3.
P
(
x
1
,
y
1
)
,
Q
(
x
2
,
y
2
)
的
和
R
(
x
3
,
y
3
)
P(x_1,y_1),Q(x_2,y_2)的和R(x_3,y_3)
P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下关系:
x
3
≡
k
2
−
x
1
−
x
2
(
m
o
d
p
)
y
3
≡
k
(
x
1
−
x
3
)
−
y
1
(
m
o
d
p
)
若
P
=
Q
,
则
k
=
3
x
1
2
+
a
2
y
1
(
m
o
d
p
)
若
P
≠
Q
,
则
k
=
y
2
−
y
1
x
2
−
x
1
(
m
o
d
p
)
\begin{aligned} x_3 & \equiv k^2-x_1-x_2 \pmod p \\ y_3 & \equiv k(x_1-x_3)-y_1 \pmod p \\ & 若P=Q, 则k=\frac{3x_1^2+a}{2y_1} \pmod p \\ & 若P≠Q, 则k=\frac{y_2-y_1}{x_2-x_1} \pmod p \end{aligned}
x3y3≡k2−x1−x2(modp)≡k(x1−x3)−y1(modp)若P=Q,则k=2y13x12+a(modp)若P=Q,则k=x2−x1y2−y1(modp)
(1) 计算-P
−
P
=
(
3
,
−
10
(
m
o
d
23
)
)
=
(
3
,
13
)
-P = (3, -10 \pmod {23}) = (3,13)
−P=(3,−10(mod23))=(3,13) (2) 计算P+Q
k
=
7
−
10
9
−
3
=
−
2
−
1
(
m
o
d
23
)
2
×
2
−
1
=
1
(
m
o
d
23
)
⇒
2
−
1
=
12
⇒
k
=
−
12
(
m
o
d
23
)
=
11
∴
P
+
Q
=
(
1
1
2
−
3
−
9
(
m
o
d
23
)
,
11
×
(
3
−
x
3
)
−
10
(
m
o
d
23
)
)
=
(
17
,
11
×
(
3
−
17
)
−
10
(
m
o
d
23
)
)
=
(
17
,
20
)
\begin{aligned} k & =\frac{7-10}{9-3} = - 2^{-1} \pmod {23} \\ & 2\times2^{-1} = 1 \pmod {23} \\ & \Rightarrow 2^{-1} = 12 \\ & \Rightarrow k = -12 \pmod {23} = 11 \\ \therefore P+Q & = (11^2-3-9\pmod {23}, 11\times (3-x_3) - 10 \pmod {23}) \\ & = (17, 11\times(3-17) -10 \pmod {23}) \\ & = (17,20) \end{aligned}
k∴P+Q=9−37−10=−2−1(mod23)2×2−1=1(mod23)⇒2−1=12⇒k=−12(mod23)=11=(112−3−9(mod23),11×(3−x3)−10(mod23))=(17,11×(3−17)−10(mod23))=(17,20) (3) 计算2P
k
=
3
×
3
2
+
1
2
×
10
(
m
o
d
23
)
=
7
×
5
−
1
(
m
o
d
23
)
5
×
5
−
1
=
1
(
m
o
d
23
)
⇒
5
−
1
=
14
⇒
k
=
7
×
14
(
m
o
d
23
)
=
6
∴
2
P
=
(
6
2
−
3
−
3
(
m
o
d
23
)
,
6
×
(
3
−
x
3
)
−
10
(
m
o
d
23
)
)
=
(
7
,
6
×
(
3
−
7
)
−
10
(
m
o
d
23
)
)
=
(
7
,
12
)
\begin{aligned} k & =\frac{3\times3^2 +1}{2\times10} \pmod {23} = 7\times5^{-1} \pmod {23} \\ & 5\times5^{-1} = 1 \pmod {23} \\ & \Rightarrow 5^{-1} = 14 \\ & \Rightarrow k = 7\times14 \pmod {23} = 6 \\ \therefore 2P & = (6^2-3-3\pmod {23}, 6\times (3-x_3) - 10 \pmod {23}) \\ & = (7, 6\times(3-7) -10 \pmod {23}) \\ & = (7,12) \end{aligned}
k∴2P=2×103×32+1(mod23)=7×5−1(mod23)5×5−1=1(mod23)⇒5−1=14⇒k=7×14(mod23)=6=(62−3−3(mod23),6×(3−x3)−10(mod23))=(7,6×(3−7)−10(mod23))=(7,12)
有限域椭圆曲线点的阶
如果椭圆曲线上一点P,存在最小的正整数n使得数乘
n
P
=
O
∞
nP=O_∞
nP=O∞ ,则将n称为P的阶 若n不存在,则P是无限阶的.
计算可得
27
P
=
−
P
=
(
3
,
13
)
27P=-P=(3,13)
27P=−P=(3,13) , 所以
28
P
=
O
∞
28P=O_∞
28P=O∞ P的阶为28 这些点做成了一个循环阿贝尔群,其中生成元为P,阶数为28。显然点的分布与顺序都是杂乱无章。
椭圆曲线加密
考虑
K
=
k
G
K=kG
K=kG ,其中K、G为椭圆曲线Ep(a,b)上的点,n为G的阶(
n
G
=
O
∞
nG=O_∞
nG=O∞ ),k为小于n的整数。则给定k和G,根据加法法则,计算K很容易但反过来,给定K和G,求k就非常困难。因为实际使用中的ECC原则上把p取得相当大,n也相当大,要把n个解点逐一算出来列成上表是不可能的。这就是椭圆曲线加密算法的数学依据 。
点G称为基点(base point)
k
(
k
<
n
)
k(k<n)
k(k<n)为私有密钥(private key)
K为公开密钥(public key)
下面是利用椭圆曲线进行加密通信的过程: 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计算点
C
1
=
M
+
r
K
C_1=M+rK
C1=M+rK和
C
2
=
r
G
C_2=rG
C2=rG。 6、用户B将
C
1
、
C
2
C_1、C_2
C1、C2传给用户A。 7、用户A接到信息后,计算
C
1
−
k
C
2
C_1-kC_2
C1−kC2,结果就是点M。再对点M进行解码就可以得到明文。 因为
C
1
−
k
C
2
=
M
+
r
K
−
k
(
r
G
)
=
M
+
r
k
G
−
k
r
G
=
M
C_1-kC_2=M+rK-k(rG)=M+rkG-krG=M
C1−kC2=M+rK−k(rG)=M+rkG−krG=M
椭圆曲线的名称由来:椭圆周长的计算可以转化为积分
∫
α
β
d
x
x
3
+
a
x
+
b
\int_α^β{\frac{dx}{\sqrt{x^3+ax+b}}}
∫αβx3+ax+bdx,分母的函数项
y
=
x
3
+
a
x
+
b
y=\sqrt{x^3+ax+b}
y=x3+ax+b两边平方即可得到椭圆曲线方程,曲线故而得名椭圆曲线。(请参考椭圆曲线密码体制解释,这个命名深究起来很复杂,了解一下就可以了) ↩︎