ECC英文全称"Ellipse Curve Cryptography" `, y6 V- h5 F9 G9 L8 ^, d" N
! i9 k0 [8 P# E0 w
与传统的基于大质数因子分解困难性的加密方法不同,ECC通过椭圆曲线方程式的性质产生密钥
ECC164位的密钥产生一个安全级,相当于RSA 1024位密钥提供的保密强度,而且计算量较小,处理速度更快,存储空间和传输带宽占用较少。目前我国居民二代身份证正在使用 256 位的椭圆曲线密码,虚拟货币比特币也选择ECC作为加密算法。
6 x7 w5 F2 R! @7 @. p
从射影平面讲起$ k& C& ?( o8 N$ D& \# u
古希腊数学家欧几里得的《几何原本》提出了五条公设。& m0 T0 z2 e; {. u7 K# g. [
# ?8 p A. r, Z4 }* Q
1.由任意一点到任意一点可作直线。
2.一条有限直线可以继续延长。! r l9 S' r: S5 [# \
9 R f6 m y* J8 a2 o+ @- A- A7 I
3.以任意点为心及任意的距离可以画圆。6 F# `$ O- v* I! ^- l
1 B8 S' m: T0 y9 ~4 l# M! w2 Q4 b
4.凡直角都相等。
5.同一平面内一条直线a和另外两条直线b.c相交,若在a某一侧的两个内角的和小于两直角,则b.c两直线经无限延长后在该侧相交。 m& Y- K2 d' I. C
3 P, o* H* _7 M" A @ H# @* {
《几何原本》只有在第29个命题% R- z5 ^- Z# P' ?) E/ Y$ i
2 w9 l# d- @8 |" z8 m: f, }6 z
一条直线与两条平行直线相交,则所成的内错角相等,同位角相等,且同旁内角之和等于两直角
/ o- h2 q7 n* d9 r# T- k3 }
中才用到第五公设,即《几何原本》中可不依靠第五公设而推出前28命题。因此,一些数学家提出,第五公设能不能不作为公设,而作为定理?能不能依靠前四个公设来证明第五公设?这就是几何发展史上最著名的,争论了长达两千多年的关于“平行线理论”的讨论
1820年代,俄国喀山大学罗巴切夫斯基用“至少可以找到两条相异的直线,且都通过P点,并不与直线R相交”代替第五公设,然后与欧氏几何的前四个公设结合成一个公理系统,他经过细致深入的推理过程中,得出了一个又一个在直觉上匪夷所思,但在逻辑上毫无矛盾的几何体系。
这种几何学被称为罗巴切夫斯基几何,简称罗氏几何。从罗氏几何学中,可以得出这样一个结论:逻辑上不矛盾的一些公理都有可能提供一种几何学。现存非欧几何的类型可以概括如下:
1.坚持第五公设,引出欧几里得几何。- H9 n. h' E! F2 e* Z0 q' O
2.“可以引最少两条平行线”为公设,罗氏几何(双曲几何)。$ z: Z' C6 ^% {) ?5 o1 S
; E' t( y; n! ]6 i; B' a' K; @
3.“一条平行线也不能引”为公设,黎曼几何(椭圆几何)
+ q- v% K+ b9 k1 W9 `- W
左:双曲几何,即罗氏几何;中:欧几里德几何;右:椭圆几何,即黎曼几何
( k4 h* ` `/ w: x
了解非欧式几何,就可以理解平行线的交点。
# g: f/ U1 h' \6 @* ]. M# W
定义平行线相交于无穷远点P∞,使平面上所有直线都统一为有唯一的交点
性质:
( @* y9 E% N" o g( m) y1 m* u6 z( ^
1.一条直线只有一个无穷远点;一对平行线有公共的无穷远点- u8 e" W$ c7 A7 I* l4 B1 f5 I
3 A1 }- Y" H/ i4 p- Z9 i
2.任何两条不平行的直线有不同的无穷远点(否则会造成有两个交点)# V! i. o* U7 E# X
3.平面上全体无穷远点构成一条无穷远直线
, P3 U4 K! {4 i4 o
射影平面:平面上全体无穷远点与全体平常点构成射影平面
射影平面点的定义
对普通平面上点(x,y),令x=X/Z,y=Y/Z,Z≠0,则投影为射影平面上的点(X:Y:Z)6 a1 o" s( s3 W
求点(1,2)在新的坐标体系下的坐标6 j* @6 }8 D6 S; K5 ^9 D/ Q' b8 B* E
∵X/Z=1 ,Y/Z=2(Z≠0), S; @- n$ b- s4 T* p
∴X=Z,Y=2Z ∴坐标为(Z:2Z:Z),Z≠03 K: O' v% l' _8 k
) V" j- P' Y; k9 t8 s
即(1:2:1)(2:4:2)(1.2:2.4:1.2)等形如(Z:2Z:Z),Z≠0的坐标都是(1,2)在新的坐标体系下的坐标
( t# ]& v* J0 w! C5 [/ Z- O
(2) 求平行线L1:X+2Y+3Z=0 与L2:X+2Y+Z=0 相交的无穷远点
∵ L1∥L2 所以有Z=0, X+2Y=0( p2 d# R% u0 p& G+ `+ S+ c0 h
t8 f) M# H, f+ j9 r
∴坐标为(-2Y:Y:0),Y≠09 o# w' c! W. ?2 y# A
即(-2:1:0)(-4:2:0)(-2.4:1.2:0)等形如(-2Y:Y:0),Y≠0
椭圆曲线
, K" C( E" i* Q
一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程(Weierstrass)所有点的集合
`; m1 E, u2 W) u1 a9 {# v
Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3
1椭圆曲线方程是一个齐次方程: k; A5 X4 X9 E0 |
( m, D8 O, R. M' M
2曲线上的每个点都必须是非奇异的(光滑的),偏导数FX(X,Y,Z)、FY(X,Y,Z)、FZ(X,Y,Z)不同为09 R% Q- X9 g5 s7 i+ \8 c
3圆曲线的形状,并不是椭圆的。只是因为椭圆曲线的描述方程,类似于计算一个椭圆周长的方程故得名* y# R* [! v# D+ s$ X. x* x
椭圆曲线示例
' w) L- G' R+ ?$ G
非椭圆曲线示例5 }& W9 N) |: g! V8 U
这两个方程都不是椭圆曲线,因为他们在(0:0:1)点处(即原点)没有切线,不满足椭圆曲线每个点都必须是非奇异的(光滑的),
- y R# z8 ]/ I1 G9 _% a5 [$ _
椭圆曲线普通方程. h: H+ T7 w& o5 W3 _1 O0 {7 w" D- Z
, W) {% s) m! C9 l
椭圆曲线普通方程:- n8 Y# B3 M s) h
无穷远点 (0, Y, 0)% q& a, n) ~* o% j) m- J) h# E1 R
平常点(x,y)斜率k:
' l& H# x5 h) z8 k
椭圆曲线阿贝尔群' n8 Y/ e) G+ g" ~. S }
我们已经看到了椭圆曲线的图象,但点与点之间好象没有什么联系。我们能不能建立一个类似于在实数轴上加法的运算法则呢?这就要定义椭圆曲线的加法群,这里需要用到近世代数中阿贝尔群。7 h8 i# Y7 @3 j: T, B/ R- k
# h7 g: v$ w+ f2 q
在数学中,群是一种代数结构,由一个集合以及一个二元运算所组成。已知集合和运算(G,*)如果是群则必须满足如下要求
封闭性:?a,b∈G,a*b ∈ G
0 N4 ?2 O* L; _) d" [/ q
结合性: ?a,b,c∈G ,有 (ab)c = a* (b*c)
单位元:ョe∈G, ?a ∈G,有ea = ae = a- u; ?# S$ c5 W
逆元: ?a ∈G ,ョb∈G 使得 ab = ba = e
/ ~7 V( _. {0 G! V
阿贝尔群除了上面的性质还满足交换律公理a * b = b * a
3 f( a. P( }: e" }3 j, P* e
同样在椭圆曲线也可以定义阿贝尔群。( o/ k1 m; m8 P0 \
任意取椭圆曲线上两点P、Q(若P、Q两点重合,则作P点的切线),作直线交于椭圆曲线的另一点R’,过R’做y轴的平行线交于R,定义P+Q=R。这样,加法的和也在椭圆曲线上,并同样具备加法的交换律、结合律. D7 N2 X6 m2 J0 @$ a/ a
5 I! _3 I9 a, k6 S- }% p
同点加法$ q1 [8 h+ y, c& X! y
) W ^% X4 G' K
若有k个相同的点P相加,记作kP
: E& @9 J: a: Y& s0 A$ {1 b3 @
P+P+P=2P+P=3P
7 R7 p3 ~0 Z! p" ?! s% j6 ~
有限域椭圆曲线! h# \/ Z% E+ \3 U
( n$ U* R* A! g$ n
椭圆曲线是连续的,并不适合用于加密;所以,我们必须把椭圆曲线变成离散的点,我们要把椭圆曲线定义在有限域上。 f, U7 l+ S: ]4 |2 @6 A" j o
我们给出一个有限域Fp! E$ T; ^5 {. |: K, R( G( Q
Fp中有p(p为质数)个元素0,1,2,…, p-2,p-11 N }: h5 ]5 u+ m' N( j. J. P
Fp的加法是a+b≡c(mod p)
) N* m% F/ N" w( V( h
Fp的乘法是a×b≡c(mod p)
+ q! l+ ]$ V1 W" d
Fp的除法是a÷b≡c(mod p),即 a×b^(-1)≡c (mod p),b-1也是一个0到p-1之间的整数,但满足b×b-1≡1 (mod p)
" c2 i' _" E: e S% l" f
Fp的单位元是1,零元是 07 X& M) ^+ J8 U, y" ]
Fp域内运算满足交换律、结合律、分配律
椭圆曲线Ep(a,b),p为质数,x,y∈[0,p-1]$ D* n4 W5 M x8 N" c/ P
选择两个满足下列约束条件的小于p的非负整数a、b; E A9 J9 v, [: [
( t, [' M' x) ^; k4 p# H
Fp上的椭圆曲线同样有加法
1.无穷远点 O∞是零元,有O∞+ O∞= O∞,O∞+P=P! F; e( M1 E. n3 m2 n$ S6 d
2.P(x,y)的负元是 (x,-y mod p)= (x,p-y) ,有P+(-P)= O∞0 ?' I% q. s* o
3.P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下关系:
) F$ g+ a, O: ~( n6 P/ H3 Q; t
x3≡k2-x1-x2(mod p)7 p$ }- a9 `9 w9 j7 a2 |
y3≡k(x1-x3)-y1(mod p)
) l! U# ]4 |# b4 [0 o4 P
若P=Q 则 k=(3x2+a)/2y1mod p
$ e/ }: L8 Y' ?; N
若P≠Q,则k=(y2-y1)/(x2-x1) mod p$ s7 u3 h: |# V% j# ^. A A
例题椭圆曲线已知E23(1,1)上两点P(3,10),Q(9,7),求(1)-P,(2)P+Q,(3) 2P$ `3 p2 n1 ~- f
- M% K: f: F3 o' i
补充:% O0 w5 B+ T% l$ Z0 Z
! z K5 R4 ~5 s8 r! H4 ~5 P
-2^(-1) mod 23 进行两部分计算
+ W7 F% F; r# v5 ]$ y6 g- j
(1) 先算 2^(-1) 对应的数A, 在这里2^(-1)不是2的-1次方,而是2的逆元6 B! l: K4 ^' m5 I# T
(2) 再算-A mod 23
(1) 计算第一步
根据有限域除法规则 2 * 2^(-1) = 1 mod 23
即 2A = 1 mod 23 ==> 2A = 23 + 1 == > A = 12
* {, o4 Q2 F. W( Z& g* x- a$ r
(2) 计算第二步# t& ?0 L4 M. Y9 M
-A mod 23 ==> -12 mod 23 即 23 -12 = 11
所以有# o1 X0 W( r. ^1 s
) ], _6 G& \1 Q% u
-2^(-1) mod 23 = 116 C& C1 i$ |/ v- R
/ \" Z1 P, Q, [! m( K
有限域椭圆曲线点的阶
如果椭圆曲线上一点P,存在最小的正整数n使得数乘nP=O∞ ,则将n称为P的阶* {6 Z+ T; v6 ~5 h. J3 p) j
若n不存在,则P是无限阶的
计算可得27P=-P=(3,13)
7 [& |6 n3 S, [: x) G! v' q
所以28P=O ∞ P的阶为281 ^ C! h6 f/ a7 l( W2 b4 I
这些点做成了一个循环阿贝尔群,其中生成元为P,阶数为29。显然点的分布与顺序都是杂乱无章
椭圆曲线加密
! W/ v& k7 w$ J+ W$ Q% N, C$ O
考虑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)9 _3 n7 c2 J1 T# J0 K5 k% c
k(k/ i# g& l8 q5 e+ o7 j! t$ K& @8 A
( N' t2 A0 r0 Y& o9 E( O. w- }6 S
K为公开密钥(public key)# O0 R" V/ b, B3 l5 a8 h
ECC保密通信算法
~# [& ~2 G: H# z+ g
1.Alice选定一条椭圆曲线E,并取椭圆曲线上一点作为基点G 假设选定E29(4,20),基点G(13,23) , 基点G的阶数n=37
2.Alice选择一个私有密钥k(k
3.Alice将E和点K、G传给Bob6 F' q" U* z5 W+ Z# A: W
: B! Y1 w1 _, ?! R# X) G, K
4.Bob收到信息后,将待传输的明文编码到上的一点M(编码方法略),并产生一个随机整数r(r
5.Bob计算点C1=M+rK和C2=rG C1= M+6K= M+625G=M+2G=(3,28)+(27,27)=(6,12) C2=6G=(5,7); R0 |8 v# ^2 v5 k; N$ b& W5 C
8 Z3 M9 {+ z: O# w
6.Bob将C1、C2传给Alice H g5 v, p6 A$ R9 _3 Q9 I
1 _( B* ~7 c- f3 ~2 U. U( c
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- b) P$ I8 L& C" I! I
( @9 L+ w, N# Y! [; p9 K+ v
ECC技术要求
通常将Fp上的一条椭圆曲线描述为T=(p,a,b,G,n,h)p、a、b确定一条椭圆曲线(p为质数,(mod p)运算)G为基点,n为点G的阶,h是椭圆曲线上所有点的个数m与n相除的商的整数部分9 A6 F% H Z1 [0 y* c3 R5 g$ X
参量选择要求:; m1 E2 p) X2 N1 R4 O+ T
* H, K+ e9 m" n7 f+ o* a
p越大安全性越好,但会导致计算速度变慢200-bit左右可满足一般安全要求n应为质数h≤4;p≠n×h ;pt≠1(mod n) (1≤t<20)4a3+27b2≠0 (mod p)
. V3 S. g, O' _% L/ C) g" a
ECC的应用3 ?8 H% P0 [3 L5 o$ P* H
比特币系统选用的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
1 X* O5 w) [& v, @
G=(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)' M, C9 E" p8 F' r
n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
h = 01
ECC vs. RSA - 优缺点
# e9 y! F6 V ~1 Y$ d; x" }7 ?' J$ {# Z
优点3 ?$ P: \/ q- H& U8 C& t
安全性能更高
1 L9 I7 n% n7 C0 @1 Y6 `' x
160位ECC与1024位RSA、DSA有相同的安全强度2 |1 _& I/ i9 |9 O. U, Q% G: S
5 d1 C0 k# l( a7 L7 D- q& R/ [
处理速度更快0 F8 }0 X5 U; }' j7 q' U0 _
在私钥的处理速度上,ECC远 比RSA、DSA快得多1 v$ w2 ~! R z- v! I& }6 {
& T7 q* W3 ~; Z0 |0 E, \/ u
带宽要求更低
- S4 Z8 ~4 p7 o
存储空间更小
ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多
缺点
设计困难,实现复杂4 C- F% n: B& T! j" u5 I
如果序列号设计过短,那么安全性并没有想象中的完善7 C. e0 p7 z- M6 [4 I4 A
& n- Q! p' u( [6 C
成为第一个吐槽的人