转载：
https://www.cnblogs.com/Kalafinaian/p/7392505.html
前言
ECC英文全称”Ellipse Curve Cryptography”
与传统的基于大质数因子分解困难性的加密方法不同，ECC通过椭圆曲线方程式的性质产生密钥ECC164位的密钥产生一个安全级，相当于RSA 1024位密钥提供的保密强度，而且计算量较小，处理速度更快，存储空间和传输带宽占用较少。目前我国居民二代身份证正在使用 256 位的椭圆曲线密码，虚拟货币比特币也选择ECC作为加密算法。
从射影平面讲起
古希腊数学家欧几里得的《几何原本》提出了五条公设。
1.由任意一点到任意一点可作直线。
2.一条有限直线可以继续延长。
3.以任意点为心及任意的距离可以画圆。
4.凡直角都相等。
5.同一平面内一条直线a和另外两条直线b.c相交，若在a某一侧的两个内角的和小于两直角，则b.c两直线经无限延长后在该侧相交。
《几何原本》只有在第29个命题：“一条直线与两条平行直线相交,则所成的内错角相等,同位角相等,且同旁内角之和等于两直角”中才用到第五公设，即《几何原本》中可不依靠第五公设而推出前28命题。因此，一些数学家提出，第五公设能不能不作为公设，而作为定理？能不能依靠前四个公设来证明第五公设？这就是几何发展史上最著名的，争论了长达两千多年的关于“平行线理论”的讨论
1820年代，俄国喀山大学罗巴切夫斯基用“至少可以找到两条相异的直线，且都通过P点，并不与直线R相交”代替第五公设，然后与欧氏几何的前四个公设结合成一个公理系统，他经过细致深入的推理过程中，得出了一个又一个在直觉上匪夷所思，但在逻辑上毫无矛盾的几何体系。
这种几何学被称为罗巴切夫斯基几何，简称罗氏几何。从罗氏几何学中，可以得出这样一个结论：逻辑上不矛盾的一些公理都有可能提供一种几何学。现存非欧几何的类型可以概括如下：
1.坚持第五公设，引出欧几里得几何。
2.“可以引最少两条平行线”为公设，罗氏几何（双曲几何）。
3.“一条平行线也不能引”为公设，黎曼几何（椭圆几何）
左：双曲几何，即罗氏几何；中：欧几里德几何；右：椭圆几何，即黎曼几何
了解非欧式几何，就可以理解平行线的交点。
定义平行线相交于无穷远点P∞，使平面上所有直线都统一为有唯一的交点
性质：
1.一条直线只有一个无穷远点；一对平行线有公共的无穷远点
2.任何两条不平行的直线有不同的无穷远点（否则会造成有两个交点）
3.平面上全体无穷远点构成一条无穷远直线
射影平面：平面上全体无穷远点与全体平常点构成射影平面
射影平面点的定义
对普通平面上点(x,y)，令x=X/Z，y=Y/Z，Z≠0，则投影为射影平面上的点(X:Y:Z)
(1)求点（1,2）在新的坐标体系下的坐标
∵X/Z=1 ，Y/Z=2（Z≠0）
∴X=Z，Y=2Z ∴坐标为（Z:2Z:Z），Z≠0
即（1:2:1）（2:4:2）（1.2:2.4:1.2）等形如（Z:2Z:Z），Z≠0的坐标都是（1,2）在新的坐标体系下的坐标
(2) 求平行线L1：X+2Y+3Z=0 与L2：X+2Y+Z=0 相交的无穷远点
∵ L1∥L2 所以有Z=0， X+2Y=0
∴坐标为（-2Y:Y:0），Y≠0
即（-2:1:0）（-4:2:0）（-2.4:1.2:0）等形如（-2Y:Y:0），Y≠0
椭圆曲线
一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程（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^{2}Z+a_1XYZ+a_3YZ^{2} = X^{3}+a_2X^{2}Z+a_4XZ^{2}+a_6Z^{3}
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
1椭圆曲线方程是一个齐次方程
2曲线上的每个点都必须是非奇异的（光滑的），偏导数FX(X,Y,Z)、FY(X,Y,Z)、FZ(X,Y,Z)不同为0
3椭圆曲线的形状并不是椭圆的。只是因为椭圆曲线的描述方程，类似于计算一个椭圆周长的方程故得名
椭圆曲线示例
非椭圆曲线示例
这两个方程都不是椭圆曲线,因为他们在（0:0:1）点处（即原点）没有切线，不满足椭圆曲线每个点都必须是非奇异的（光滑的）
椭圆曲线普通方程
椭圆曲线普通方程：
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
y
2
+
a
1
x
y
+
a
3
y
=
x
3
+
a
2
x
2
+
a
4
x
+
a
6
无穷远点 (0, Y, 0)
平常点(x,y)斜率k：
F
x
(
x
,
y
)
=
a
1
y
−
3
x
2
−
2
a
2
x
−
a
4
F_x(x,y)=a_1y−3x^{2}−2a_2x−a_4
F
x
(
x
,
y
)
=
a
1
y
−
3
x
2
−
2
a
2
x
−
a
4
F
y
(
x
,
y
)
=
2
y
+
a
1
x
+
a
3
F_y(x,y)=2y+a_1x+a_3
F
y
(
x
,
y
)
=
2
y
+
a
1
x
+
a
3
k
=
−
F
x
(
x
,
y
)
F
y
(
x
,
y
)
=
3
x
2
+
2
a
2
x
+
a
4
−
a
1
y
2
y
+
a
1
x
+
a
3
k=−\frac{Fx(x,y)}{Fy(x,y)}=\frac{3x^{2}+2a_2x+a_4−a_1y}{2y+a_1x+a3}
k
=
−
F
y
(
x
,
y
)
F
x
(
x
,
y
)
=
2
y
+
a
1
x
+
a
3
3
x
2
+
2
a
2
x
+
a
4
−
a
1
y
椭圆曲线阿贝尔群
我们已经看到了椭圆曲线的图象，但点与点之间好象没有什么联系。我们能不能建立一个类似于在实数轴上加法的运算法则呢？这就要定义椭圆曲线的加法群，这里需要用到近世代数中阿贝尔群。
在数学中，群是一种代数结构，由一个集合以及一个二元运算所组成。已知集合和运算(G,*)如果是群则必须满足如下要求
1.封闭性：∀a,b∈G，a
b ∈ G
2.结合性： ∀a,b,c∈G ，有 (ab)c = a
(b*c)
3.单位元：ョe∈G， ∀a ∈G，有ea = ae = a
4.逆元： ∀a ∈G ，ョb∈G 使得 ab = ba = e
阿贝尔群除了上面的性质还满足交换律公理a * b = b * a
同样在椭圆曲线也可以定义阿贝尔群。
任意取椭圆曲线上两点P、Q（若P、Q两点重合，则作P点的切线），作直线交于椭圆曲线的另一点R’，过R’做y轴的平行线交于R，定义P+Q=R。这样，加法的和也在椭圆曲线上，并同样具备加法的交换律、结合律
同点加法：
若有k个相同的点P相加，记作kP
P+P+P=2P+P=3P
有限域椭圆曲线
椭圆曲线是连续的，并不适合用于加密；所以，我们必须把椭圆曲线变成离散的点，我们要把椭圆曲线定义在有限域上。我们给出一个有限域Fp
- Fp中有p（p为质数）个元素0,1,2,…, p-2,p-1
- Fp的加法是a+b≡c(mod p)
- Fp的乘法是a×b≡c(mod p)
- Fp的除法是a÷b≡c(mod p)，即 a×b^(-1)≡c (mod p)，b-1也是一个0到p-1之间的整数，但满足b×b-1≡1 (mod p)
- 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(mod \quad p)
y
2
=
x
3
+
a
x
+
b
(
m
o
d
p
)
选择两个满足下列约束条件的小于p的非负整数a、b
4
a
3
+
27
b
2
≠
0
(
m
o
d
p
)
4a^3+27b^2≠0(mod\quad p)
4
a
3
+
2
7
b
2
=
0
(
m
o
d
p
)
Fp上的椭圆曲线同样有加法
1.无穷远点 O∞是零元，有O∞+ O∞= O∞，O∞+P=P
2.P(x,y)的负元是 (x,-y mod p)= (x,p-y) ，有P+(-P)= O∞
3.P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下关系：
x3≡k2-x1-x2(mod p)
y3≡k(x1-x3)-y1(mod p)
若P=Q 则 k=(3×2+a)/2y1mod p
若P≠Q，则k=(y2-y1)/(x2-x1) mod p
例题椭圆曲线已知E23(1,1)上两点P(3,10)，Q(9,7)，求(1)-P，(2)P+Q，(3) 2P
(
1
)
−
P
=
(
3
,
−
10
m
o
d
23
)
=
(
3
,
13
)
(1)−P=(3,−10mod23)=(3,13)
(
1
)
−
P
=
(
3
,
−
1
0
m
o
d
2
3
)
=
(
3
,
1
3
)
(
2
)
k
=
7
−
10
9
−
3
=
−
2
−
1
m
o
d
23
(2)k=\frac{7−10}{9−3}=−2^{−1}mod23
(
2
)
k
=
9
−
3
7
−
1
0
=
−
2
−
1
m
o
d
2
3
2
⋅
2
−
1
=
1
m
o
d
23
⇒
2
−
1
=
12
\quad\quad2⋅2^{−1}=1mod23⇒2^{−1}=12
2
⋅
2
−
1
=
1
m
o
d
2
3
⇒
2
−
1
=
1
2
k
=
−
12
m
o
d
23
=
11
\quad\quad k=−12mod23=11
k
=
−
1
2
m
o
d
2
3
=
1
1
P
+
Q
=
(
1
1
2
−
3
−
9
m
o
d
23
,
11
×
(
3
−
(
−
6
)
)
m
o
d
23
)
=
(
17
,
20
)
\quad\quad P+Q=(11^2−3−9mod23,11×(3−(−6))mod23)=(17,20)
P
+
Q
=
(
1
1
2
−
3
−
9
m
o
d
2
3
,
1
1
×
(
3
−
(
−
6
)
)
m
o
d
2
3
)
=
(
1
7
,
2
0
)
(
3
)
k
=
3
×
3
2
+
1
2
×
10
m
o
d
23
=
7
⋅
5
−
1
m
o
d
23
(3)k=\frac{3×3^2+1}{2×10}mod23=7⋅5^{−1}mod23
(
3
)
k
=
2
×
1
0
3
×
3
2
+
1
m
o
d
2
3
=
7
⋅
5
−
1
m
o
d
2
3
5
⋅
5
−
1
=
1
m
o
d
23
⇒
5
−
1
=
14
\quad\quad 5⋅5^{−1}=1mod23⇒5^{−1}=14
5
⋅
5
−
1
=
1
m
o
d
2
3
⇒
5
−
1
=
1
4
k
=
7
⋅
14
m
o
d
23
=
6
\quad\quad k=7⋅14mod23=6
k
=
7
⋅
1
4
m
o
d
2
3
=
6
2
P
=
(
6
2
−
3
−
3
m
o
d
23
,
6
×
(
3
−
7
)
−
10
m
o
d
23
)
=
(
7
,
12
)
\quad\quad 2P=(6^2−3−3mod23,6×(3−7)−10mod23)=(7,12)
2
P
=
(
6
2
−
3
−
3
m
o
d
2
3
,
6
×
(
3
−
7
)
−
1
0
m
o
d
2
3
)
=
(
7
,
1
2
)
补充:
-2^(-1) mod 23 进行两部分计算
(1) 先算 2^(-1) 对应的数A, 在这里2^(-1)不是2的-1次方，而是2的逆元
(2) 再算-A mod 23
(1) 计算第一步
根据有限域除法规则 2 * 2^(-1) = 1 mod 23
即 2A = 1 mod 23 ==> 2A = 23 + 1 == > A = 12
(2) 计算第二步
-A mod 23 ==> -12 mod 23 即 23 -12 = 11
所以有
-2^(-1) mod 23 = 11
有限域椭圆曲线点的阶
如果椭圆曲线上一点P，存在最小的正整数n使得数乘nP=O∞ ,则将n称为P的阶
若n不存在，则P是无限阶的
计算可得27P=-P=(3,13)
所以28P=O ∞ P的阶为28
这些点做成了一个循环阿贝尔群，其中生成元为P，阶数为29。显然点的分布与顺序都是杂乱无章
椭圆曲线加密
考虑K=kG ，其中K、G为椭圆曲线Ep(a,b)上的点，n为G的阶（nG=O∞ ），k为小于n的整数。则给定k和G，根据加法法则，计算K很容易但反过来，给定K和G，求k就非常困难。因为实际使用中的ECC原则上把p取得相当大，n也相当大，要把n个解点逐一算出来列成上表是不可能的。这就是椭圆曲线加密算法的数学依据
点G称为基点（base point）
k（k<n）为私有密钥（privte key）
K为公开密钥（public key)
ECC保密通信算法
1.Alice选定一条椭圆曲线E，并取椭圆曲线上一点作为基点G 假设选定E29(4,20)，基点G(13,23) , 基点G的阶数n=37
2.Alice选择一个私有密钥p（p<n），并生成公开密钥K=pG 比如25, K= pG = 25G = (14,6）
3.Alice将E和点K、G传给Bob
4.Bob收到信息后，将待传输的明文编码到上的一点M（编码方法略），并产生一个随机整数r（r<n,n为G的阶数） 假设r=6 要加密的信息为3,因为M也要在E29(4,20) 所以M=(3,28)
5.Bob计算点C1=M+rK和C2=rG C1= M+6K = (3,28)+6*(14,6)=(3,28)+(27,27)=(6,12) C2= 6G =(5,7)
6.Bob将C1、C2传给Alice
7.Alice收到信息后，计算C1-kC2，结果就应该是点M C1-kC2 =(6,12)-25C2 =(6,12)-25*6G =(6,12)-2G =(6,12)-(27,27) =(6,12)+(27,2) =(3,28)
数学原来上能解密是因为:C1-kC2=M+rK-krG=M+rkG-krG-M
ECC技术要求
通常将Fp上的一条椭圆曲线描述为T=(p,a,b,G,n,h)p、a、b确定一条椭圆曲线（p为质数，(mod p)运算）G为基点，n为点G的阶，h是椭圆曲线上所有点的个数m与n相除的商的整数部分
参量选择要求：
- p越大安全性越好，但会导致计算速度变慢
- 200-bit左右可满足一般安全要求
- n应为质数
- h≤4；p≠n×h ；pt≠1(mod n) (1≤t＜20)
- 4a3＋27b2≠0 (mod p)
ECC的应用
比特币系统选用的secp256k1中，参数为
p = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F= 2^256 − 2^32 − 2^9 − 2^8 − 2^7 − 2^6 − 2^4 − 1
a = 0， b = 7
G=(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
h = 01
ECC vs. RSA – 优缺点
优点
- 安全性能更高
- 160位ECC与1024位RSA、DSA有相同的安全强度
- 处理速度更快
- 在私钥的处理速度上，ECC远 比RSA、DSA快得多
- 带宽要求更低
- 存储空间更小
- ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多
缺点
- 设计困难，实现复杂
- 如果序列号设计过短，那么安全性并没有想象中的完善