- y \/ _& i( M- R; t I) O
ECC英文全称"Ellipse Curve Cryptography"8 f1 |7 e* V: S. ~
与传统的基于大质数因子分解困难性的加密方法不同,ECC通过椭圆曲线方程式的性质产生密钥
ECC164位的密钥产生一个安全级,相当于RSA 1024位密钥提供的保密强度,而且计算量较小,处理速度更快,存储空间和传输带宽占用较少。目前我国居民二代身份证正在使用 256 位的椭圆曲线密码,虚拟货币比特币也选择ECC作为加密算法。
+ |3 ?- R( v& x
从射影平面讲起
古希腊数学家欧几里得的《几何原本》提出了五条公设。" S; v/ |4 G, Z7 F( V
/ H# P; A0 w; K" V; Z
1.由任意一点到任意一点可作直线。
2 s( N# d7 S, F( b
2.一条有限直线可以继续延长。. ]% c6 c$ w& A F$ U& X0 y
5 o* i+ D0 K( V: Q3 z
3.以任意点为心及任意的距离可以画圆。9 K4 K5 o! ~" Y1 V
9 L+ f/ a) u4 G( D& k* v2 c9 h
4.凡直角都相等。! x$ H) w* _* C/ R
5.同一平面内一条直线a和另外两条直线b.c相交,若在a某一侧的两个内角的和小于两直角,则b.c两直线经无限延长后在该侧相交。
. M- T) T5 ?" k! l
《几何原本》只有在第29个命题1 u3 Y4 Z; M1 k1 N% a6 H
! i9 e; z6 N. \& s" G1 d
一条直线与两条平行直线相交,则所成的内错角相等,同位角相等,且同旁内角之和等于两直角
, c. L, \# Q0 t7 P& s4 B; s5 f' i
中才用到第五公设,即《几何原本》中可不依靠第五公设而推出前28命题。因此,一些数学家提出,第五公设能不能不作为公设,而作为定理?能不能依靠前四个公设来证明第五公设?这就是几何发展史上最著名的,争论了长达两千多年的关于“平行线理论”的讨论; w' ?$ V3 u# {8 K' t9 V
/ H& A% F$ M; l! Y
1820年代,俄国喀山大学罗巴切夫斯基用“至少可以找到两条相异的直线,且都通过P点,并不与直线R相交”代替第五公设,然后与欧氏几何的前四个公设结合成一个公理系统,他经过细致深入的推理过程中,得出了一个又一个在直觉上匪夷所思,但在逻辑上毫无矛盾的几何体系。3 X& U( q7 r" E
这种几何学被称为罗巴切夫斯基几何,简称罗氏几何。从罗氏几何学中,可以得出这样一个结论:逻辑上不矛盾的一些公理都有可能提供一种几何学。现存非欧几何的类型可以概括如下:4 P+ ?4 t* V# {, h3 a
1.坚持第五公设,引出欧几里得几何。
2.“可以引最少两条平行线”为公设,罗氏几何(双曲几何)。
7 ^/ |, X! e! H8 P7 y
3.“一条平行线也不能引”为公设,黎曼几何(椭圆几何)' y# d% f# M, \$ Z4 I* O
% E, w0 T4 Z2 C5 I1 _4 {" m$ q! s2 g
左:双曲几何,即罗氏几何;中:欧几里德几何;右:椭圆几何,即黎曼几何
2 u; `! w# m: W8 A& u
了解非欧式几何,就可以理解平行线的交点。
定义平行线相交于无穷远点P∞,使平面上所有直线都统一为有唯一的交点
性质:) n8 a! v! H5 ~4 o% O( u
1.一条直线只有一个无穷远点;一对平行线有公共的无穷远点* m* ]$ P+ o- j) P/ H+ M. R
+ x; O6 W$ Z+ I1 b
2.任何两条不平行的直线有不同的无穷远点(否则会造成有两个交点)2 y" T: j+ `& n U8 y
3.平面上全体无穷远点构成一条无穷远直线
射影平面:平面上全体无穷远点与全体平常点构成射影平面, f0 ]) J5 L r8 T" _
7 J8 G" q9 k# v# ]$ D) p! Q3 _
射影平面点的定义
W0 W* x! u, G- h4 f( |
对普通平面上点(x,y),令x=X/Z,y=Y/Z,Z≠0,则投影为射影平面上的点(X:Y:Z)3 ^! ~/ K: O; D' ?
% T4 y: C- f% l5 Y4 ^8 O
求点(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)在新的坐标体系下的坐标- X9 a: p- i: u+ u
(2) 求平行线L1:X+2Y+3Z=0 与L2:X+2Y+Z=0 相交的无穷远点
∵ L1∥L2 所以有Z=0, X+2Y=0
∴坐标为(-2Y:Y:0),Y≠08 p2 B. C4 E/ `
5 ~# D- U! u# H' z( i# A# Y2 P
即(-2:1:0)(-4:2:0)(-2.4:1.2:0)等形如(-2Y:Y:0),Y≠0
N# [& d+ ]9 n6 `) x$ j
椭圆曲线
一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程(Weierstrass)所有点的集合
/ k6 {$ y$ Y- V6 C
Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3
1椭圆曲线方程是一个齐次方程* P3 e' ]- q |/ y5 C
8 j7 h5 W0 ^/ y3 J0 v! v' s7 {
2曲线上的每个点都必须是非奇异的(光滑的),偏导数FX(X,Y,Z)、FY(X,Y,Z)、FZ(X,Y,Z)不同为04 s4 \2 ?# t7 O) E1 ?$ H; c
3圆曲线的形状,并不是椭圆的。只是因为椭圆曲线的描述方程,类似于计算一个椭圆周长的方程故得名 F- \" v# k; o+ b
椭圆曲线示例8 v! S1 r0 k0 Z% P9 I
8 m% [! t" A, G& j8 ?" [9 L
非椭圆曲线示例8 J8 p" A6 t; v+ g8 S
; I+ U. l5 e5 r. R `+ v4 ^
这两个方程都不是椭圆曲线,因为他们在(0:0:1)点处(即原点)没有切线,不满足椭圆曲线每个点都必须是非奇异的(光滑的),
椭圆曲线普通方程
椭圆曲线普通方程:
无穷远点 (0, Y, 0)
: G3 g; @4 C( b' k
平常点(x,y)斜率k:
- u8 E3 I! c: F P8 I, N
椭圆曲线阿贝尔群/ R' Z- U- Y1 g6 v9 h& q3 H
我们已经看到了椭圆曲线的图象,但点与点之间好象没有什么联系。我们能不能建立一个类似于在实数轴上加法的运算法则呢?这就要定义椭圆曲线的加法群,这里需要用到近世代数中阿贝尔群。
- N' {7 ]3 `7 M4 p
在数学中,群是一种代数结构,由一个集合以及一个二元运算所组成。已知集合和运算(G,*)如果是群则必须满足如下要求
封闭性:?a,b∈G,a*b ∈ G7 x6 {( C+ Z$ r6 ~7 A( ~( ^
( M" i* Q4 U8 Y* ]2 T
结合性: ?a,b,c∈G ,有 (ab)c = a* (b*c)) T! F- e/ P7 z2 g+ N/ k
; z, t1 {9 Q7 u
单位元:ョe∈G, ?a ∈G,有ea = ae = a
逆元: ?a ∈G ,ョb∈G 使得 ab = ba = e
阿贝尔群除了上面的性质还满足交换律公理a * b = b * a
0 H& L/ ]8 \6 h7 n# g% T
同样在椭圆曲线也可以定义阿贝尔群。( @2 N$ A# A* C D( R0 P. y/ o
任意取椭圆曲线上两点P、Q(若P、Q两点重合,则作P点的切线),作直线交于椭圆曲线的另一点R’,过R’做y轴的平行线交于R,定义P+Q=R。这样,加法的和也在椭圆曲线上,并同样具备加法的交换律、结合律
同点加法
若有k个相同的点P相加,记作kP
P+P+P=2P+P=3P
有限域椭圆曲线( {0 @, \5 r. Z% {5 y- z
( T' I, k/ R9 f% N
椭圆曲线是连续的,并不适合用于加密;所以,我们必须把椭圆曲线变成离散的点,我们要把椭圆曲线定义在有限域上。
我们给出一个有限域Fp
1 L% [8 r7 U" N% U
Fp中有p(p为质数)个元素0,1,2,…, p-2,p-1
5 x' N9 F" l3 _+ {
Fp的加法是a+b≡c(mod p)8 r# v/ d% Z) P6 U9 z; ^" T
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)1 i+ T7 Q! h; W0 D/ p, z) O( b
. v9 Y" D* p. c$ O# I" @
Fp的单位元是1,零元是 0
Fp域内运算满足交换律、结合律、分配律
5 q9 Z6 O; |* b( h& q9 s! ^
椭圆曲线Ep(a,b),p为质数,x,y∈[0,p-1]
选择两个满足下列约束条件的小于p的非负整数a、b# Q) j$ x8 y: v* J
Fp上的椭圆曲线同样有加法# I l' R% l( p I& M$ ^ P
1.无穷远点 O∞是零元,有O∞+ O∞= O∞,O∞+P=P9 H# @) G" K: `* Z
2.P(x,y)的负元是 (x,-y mod p)= (x,p-y) ,有P+(-P)= O∞$ ]6 j9 ^9 p4 R+ [7 I7 o, ]
3.P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下关系:; O1 c; I& P5 M2 U U8 w4 E# L
8 B1 q- `" R# Q$ m
x3≡k2-x1-x2(mod p)
y3≡k(x1-x3)-y1(mod p)/ K2 |" x5 ?. e( m' A" b
若P=Q 则 k=(3x2+a)/2y1mod p" a0 w$ r- u2 ^: i
f; c% g {% [0 A( B7 {
若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; q3 ^) j0 c. Q3 X% c1 U
0 u& D) C/ C% O% Z
补充:) `* K; `, g- u- E0 U w0 V
-2^(-1) mod 23 进行两部分计算
(1) 先算 2^(-1) 对应的数A, 在这里2^(-1)不是2的-1次方,而是2的逆元
(2) 再算-A mod 23) z) P K( o. r/ ]) S9 y' p3 X1 \
1 t$ w9 |! c: h' x6 M
(1) 计算第一步
1 ]- ?6 s% |* G7 B3 D2 t0 d
根据有限域除法规则 2 * 2^(-1) = 1 mod 23" f5 O1 i% a) \
即 2A = 1 mod 23 ==> 2A = 23 + 1 == > A = 120 o6 [/ H, t* ^7 i U3 A M
(2) 计算第二步0 I$ Q# a/ I- p' E0 J! M
-A mod 23 ==> -12 mod 23 即 23 -12 = 11
' s4 B. N6 k% n8 W2 g. @1 ?( A' A
所以有
-2^(-1) mod 23 = 119 p7 r+ U- @/ a
9 C/ \+ }7 s4 a. e% D) Q9 N3 K& O8 H
有限域椭圆曲线点的阶
, x& T, Q" Z" o" J
如果椭圆曲线上一点P,存在最小的正整数n使得数乘nP=O∞ ,则将n称为P的阶( Q D4 ^( A0 A* P' a, ^! ^) k% k
3 D% i l! N# H( N
若n不存在,则P是无限阶的$ ]# O/ J8 R) Y0 }% b" g) l
/ A, X. ~$ r0 C- @1 Z
计算可得27P=-P=(3,13)3 a9 ~, P$ q0 k! K
所以28P=O ∞ P的阶为28
这些点做成了一个循环阿贝尔群,其中生成元为P,阶数为29。显然点的分布与顺序都是杂乱无章9 T W' J5 x0 m* c
椭圆曲线加密6 s- \+ l, O; z& n \8 L- w
' T1 n# d8 D6 w7 f7 C/ U
考虑K=kG ,其中K、G为椭圆曲线Ep(a,b)上的点,n为G的阶(nG=O∞ ),k为小于n的整数。则给定k和G,根据加法法则,计算K很容易但反过来,给定K和G,求k就非常困难。因为实际使用中的ECC原则上把p取得相当大,n也相当大,要把n个解点逐一算出来列成上表是不可能的。这就是椭圆曲线加密算法的数学依据6 L* z, l4 J8 @+ k# {! K n
) [/ i* T8 e6 m& s
点G称为基点(base point)) b6 K- @3 l" o f
; E. p; _5 L' V
k(k
K为公开密钥(public key), z+ }' i( O" Y' p! O) w
6 N' O, |2 B; r
ECC保密通信算法
1.Alice选定一条椭圆曲线E,并取椭圆曲线上一点作为基点G 假设选定E29(4,20),基点G(13,23) , 基点G的阶数n=37# H# M* o# D4 N, y( l: Z. H
3 Z4 N4 _8 C- B/ v
2.Alice选择一个私有密钥k(k
3.Alice将E和点K、G传给Bob
( G$ @0 p) c' i
4.Bob收到信息后,将待传输的明文编码到上的一点M(编码方法略),并产生一个随机整数r(r: d/ I0 `1 i5 l. X/ H6 I
5.Bob计算点C1=M+rK和C2=rG C1= M+6K= M+625G=M+2G=(3,28)+(27,27)=(6,12) C2=6G=(5,7) d3 }- S+ c0 X! R, Y9 V
6.Bob将C1、C2传给Alice
3 ]( q, i; a& M
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)
% d1 x$ K" u: i9 E- {2 G- s
数学原来上能解密是因为:C1-kC2=M+rK-krG=M+rkG-krG-M" b7 g' u! M7 M1 ~
& {4 }( l0 b. V" A' ^& l
ECC技术要求5 u% z5 e" X% I6 l
通常将Fp上的一条椭圆曲线描述为T=(p,a,b,G,n,h)p、a、b确定一条椭圆曲线(p为质数,(mod p)运算)G为基点,n为点G的阶,h是椭圆曲线上所有点的个数m与n相除的商的整数部分, i t: c- L( ~. N0 Q
+ k( b! U7 @0 B d: k5 y
参量选择要求:
) C* s) I6 D: n7 k2 `+ |% ^0 h' a
p越大安全性越好,但会导致计算速度变慢200-bit左右可满足一般安全要求n应为质数h≤4;p≠n×h ;pt≠1(mod n) (1≤t<20)4a3+27b2≠0 (mod p)
ECC的应用0 F1 J5 D7 J2 e: e7 H+ q4 g# x
比特币系统选用的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' m, q5 E3 p2 s* R/ B4 [4 ?+ m
a = 0, b = 7& d4 R! w* z' H' f7 ]; m
/ n8 L' p3 m* R! R
G=(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)$ [8 F- @) i8 s% z
' D# t3 f) r( v/ N3 H" ~
n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D03641410 @3 M% |5 p; @/ z. ^! }7 O1 m
% c0 ]8 i( P J/ i3 Y" B: m( i/ T
h = 017 w* N' z* c" G
+ S+ M4 M! k8 Z% }
ECC vs. RSA - 优缺点
+ r% p* z" E" Q/ ?& }
优点+ m6 C9 T0 V& V/ b
0 Z T+ ?. f, H# |- e2 h$ C
安全性能更高6 D+ E1 E: Z! k# l3 H5 V
160位ECC与1024位RSA、DSA有相同的安全强度% u* N) L' Q: v+ H7 r) S1 H
- w8 y$ s! n% K9 T' M7 u, V
处理速度更快
在私钥的处理速度上,ECC远 比RSA、DSA快得多
9 z! h' I. K" r7 ^) G
带宽要求更低. o0 \9 y: f& D
' g& C7 I$ r/ b- J, q# R: l
存储空间更小
ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多% t6 Q8 `+ r5 J
缺点9 |7 _+ A: S% h& Q2 O3 c8 \
+ l. a$ N# e: \ J, a& Q
设计困难,实现复杂
如果序列号设计过短,那么安全性并没有想象中的完善
: ~: Y; Y5 o0 R( v1 }; j
成为第一个吐槽的人