ECC英文全称"Ellipse Curve Cryptography"
与传统的基于大质数因子分解困难性的加密方法不同,ECC通过椭圆曲线方程式的性质产生密钥
. s$ M; C, f/ Q* B5 a+ O* O
ECC164位的密钥产生一个安全级,相当于RSA 1024位密钥提供的保密强度,而且计算量较小,处理速度更快,存储空间和传输带宽占用较少。目前我国居民二代身份证正在使用 256 位的椭圆曲线密码,虚拟货币比特币也选择ECC作为加密算法。
从射影平面讲起
古希腊数学家欧几里得的《几何原本》提出了五条公设。' Q; \9 u" e3 D; q; J" t
4 e& c. ~% K3 c! H1 s* Y' T
1.由任意一点到任意一点可作直线。$ ^9 _' l- z; i3 t- ~- m
0 B2 R% L! a, ]9 p1 ^
2.一条有限直线可以继续延长。6 M( R1 D' {, k- Z
3.以任意点为心及任意的距离可以画圆。
7 V2 c( X9 _, h9 ~
4.凡直角都相等。
5.同一平面内一条直线a和另外两条直线b.c相交,若在a某一侧的两个内角的和小于两直角,则b.c两直线经无限延长后在该侧相交。5 |0 g! Z1 d! i" _
( r7 Q1 Y, e1 N0 a
《几何原本》只有在第29个命题" |( a G2 I, o! k$ ~
一条直线与两条平行直线相交,则所成的内错角相等,同位角相等,且同旁内角之和等于两直角
5 x8 @9 k. k7 Y; j, f$ m
中才用到第五公设,即《几何原本》中可不依靠第五公设而推出前28命题。因此,一些数学家提出,第五公设能不能不作为公设,而作为定理?能不能依靠前四个公设来证明第五公设?这就是几何发展史上最著名的,争论了长达两千多年的关于“平行线理论”的讨论
; S2 M, r, c- Q
1820年代,俄国喀山大学罗巴切夫斯基用“至少可以找到两条相异的直线,且都通过P点,并不与直线R相交”代替第五公设,然后与欧氏几何的前四个公设结合成一个公理系统,他经过细致深入的推理过程中,得出了一个又一个在直觉上匪夷所思,但在逻辑上毫无矛盾的几何体系。
这种几何学被称为罗巴切夫斯基几何,简称罗氏几何。从罗氏几何学中,可以得出这样一个结论:逻辑上不矛盾的一些公理都有可能提供一种几何学。现存非欧几何的类型可以概括如下:
0 @4 K8 s" z9 [4 g% p8 g
1.坚持第五公设,引出欧几里得几何。# @1 d' E2 B- ~
2.“可以引最少两条平行线”为公设,罗氏几何(双曲几何)。
3.“一条平行线也不能引”为公设,黎曼几何(椭圆几何)
6 K# z' ^! t* b/ B+ K& n
左:双曲几何,即罗氏几何;中:欧几里德几何;右:椭圆几何,即黎曼几何
了解非欧式几何,就可以理解平行线的交点。. w# c2 s6 Q, u- E3 d: I) `
定义平行线相交于无穷远点P∞,使平面上所有直线都统一为有唯一的交点
性质:
1.一条直线只有一个无穷远点;一对平行线有公共的无穷远点! n: I6 D) s _! v9 N
- s# {/ x" {2 s* b2 X. m
2.任何两条不平行的直线有不同的无穷远点(否则会造成有两个交点)# H5 x% i1 Z' D; t' P- M, V
3.平面上全体无穷远点构成一条无穷远直线
射影平面:平面上全体无穷远点与全体平常点构成射影平面
" K# I5 [1 i1 }) M
射影平面点的定义4 t b; O$ I0 g, G
0 H3 U/ U* v9 ]" w: A
对普通平面上点(x,y),令x=X/Z,y=Y/Z,Z≠0,则投影为射影平面上的点(X:Y:Z)/ E& d3 F6 K9 L8 K* H( h# N) V
9 t" ^4 X5 Z$ ?& H# c, z
求点(1,2)在新的坐标体系下的坐标, ]8 k4 d- n0 C" \
∵X/Z=1 ,Y/Z=2(Z≠0)
2 t. \; H+ y! \$ C- d. t
∴X=Z,Y=2Z ∴坐标为(Z:2Z:Z),Z≠0$ ^2 w( i9 M2 L2 h/ F2 f+ H
即(1:2:1)(2:4:2)(1.2:2.4:1.2)等形如(Z:2Z:Z),Z≠0的坐标都是(1,2)在新的坐标体系下的坐标
5 L9 i& o% r$ f
(2) 求平行线L1:X+2Y+3Z=0 与L2:X+2Y+Z=0 相交的无穷远点' g* J4 M; [- L5 a9 W" T
∵ L1∥L2 所以有Z=0, X+2Y=0" W. ?$ Z4 r/ f4 b: z
∴坐标为(-2Y:Y:0),Y≠0
2 ]: f2 G, x! X
即(-2:1:0)(-4:2:0)(-2.4:1.2:0)等形如(-2Y:Y:0),Y≠01 X9 D9 ~- r4 n
; v& x/ U& S5 f7 B7 U) v6 u
椭圆曲线
1 E% H7 K- b- [6 t1 p1 q
一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程(Weierstrass)所有点的集合7 u; ]5 H/ V/ v/ [
Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3& e* d5 n; ~' S
1椭圆曲线方程是一个齐次方程+ O; @) j7 v, l/ h, u; ]$ m G
* y" p e' ^' j/ O k
2曲线上的每个点都必须是非奇异的(光滑的),偏导数FX(X,Y,Z)、FY(X,Y,Z)、FZ(X,Y,Z)不同为0
3圆曲线的形状,并不是椭圆的。只是因为椭圆曲线的描述方程,类似于计算一个椭圆周长的方程故得名5 L7 H7 O4 x4 E9 W }; z, L" I
u" a; g$ W4 K4 Y6 z( @" f
椭圆曲线示例
/ w7 a. p; \! R* }
非椭圆曲线示例
6 u: I* R3 Q! c2 X! o# w2 V
这两个方程都不是椭圆曲线,因为他们在(0:0:1)点处(即原点)没有切线,不满足椭圆曲线每个点都必须是非奇异的(光滑的),
" @# K9 C+ ]$ s2 {/ B Y
椭圆曲线普通方程
+ c6 g: }2 T; z( ^ l
椭圆曲线普通方程:
: x- F$ K: r% v# g& c
无穷远点 (0, Y, 0)
平常点(x,y)斜率k:5 H# O9 @" m0 i3 x0 L& P0 i
* z( R8 ]9 Y- m& b' Z) q
椭圆曲线阿贝尔群
我们已经看到了椭圆曲线的图象,但点与点之间好象没有什么联系。我们能不能建立一个类似于在实数轴上加法的运算法则呢?这就要定义椭圆曲线的加法群,这里需要用到近世代数中阿贝尔群。
在数学中,群是一种代数结构,由一个集合以及一个二元运算所组成。已知集合和运算(G,*)如果是群则必须满足如下要求
* F# }8 y# [3 Q5 z1 E/ s) P
封闭性:?a,b∈G,a*b ∈ G" A8 F3 _$ u+ l/ S& V
结合性: ?a,b,c∈G ,有 (ab)c = a* (b*c)
: b/ S: k% g, e
单位元:ョe∈G, ?a ∈G,有ea = ae = a
逆元: ?a ∈G ,ョb∈G 使得 ab = ba = e
阿贝尔群除了上面的性质还满足交换律公理a * b = b * a" A/ p* H. J* H
# S! C! G% ?: D; }/ A/ z
同样在椭圆曲线也可以定义阿贝尔群。( b' X% J4 u$ R8 e8 U
% ?$ O: r& D) a
任意取椭圆曲线上两点P、Q(若P、Q两点重合,则作P点的切线),作直线交于椭圆曲线的另一点R’,过R’做y轴的平行线交于R,定义P+Q=R。这样,加法的和也在椭圆曲线上,并同样具备加法的交换律、结合律$ Q4 u8 W; r; r0 m3 Y( A1 s( c
" K/ a" W" G% D) G4 P7 `0 {/ }
同点加法+ ?& q3 b1 Z% \+ i9 ^; S9 Z
若有k个相同的点P相加,记作kP# s2 i, R" l3 F% R
% M! D2 m2 O% ] V/ R
P+P+P=2P+P=3P' c% q0 o, F. A- P7 W3 C, B2 |4 ?$ ~3 S3 [
有限域椭圆曲线% ]8 G) }- d% d" t; C# r
椭圆曲线是连续的,并不适合用于加密;所以,我们必须把椭圆曲线变成离散的点,我们要把椭圆曲线定义在有限域上。# x8 k% r# D: z! m/ p
我们给出一个有限域Fp( }$ Z3 p1 i: u `
7 @5 g: z; O1 I" z8 c) D" a# l2 z
Fp中有p(p为质数)个元素0,1,2,…, p-2,p-1
Fp的加法是a+b≡c(mod p)
Fp的乘法是a×b≡c(mod p) @3 l/ X* S7 O: k# h/ N! {
/ Y& h p S9 m7 c2 j( V8 i
Fp的除法是a÷b≡c(mod p),即 a×b^(-1)≡c (mod p),b-1也是一个0到p-1之间的整数,但满足b×b-1≡1 (mod p)
- j6 Y. T2 B$ h$ c7 b( y
Fp的单位元是1,零元是 0
Fp域内运算满足交换律、结合律、分配律
- x, n) ~9 ]9 A2 m
椭圆曲线Ep(a,b),p为质数,x,y∈[0,p-1]
选择两个满足下列约束条件的小于p的非负整数a、b6 G& [& C# }: n- D9 Q8 F7 o2 E
Fp上的椭圆曲线同样有加法
1.无穷远点 O∞是零元,有O∞+ O∞= O∞,O∞+P=P
8 d. u0 E8 t5 g8 K/ U3 j
2.P(x,y)的负元是 (x,-y mod p)= (x,p-y) ,有P+(-P)= O∞
4 _' N: q/ z7 `8 R3 c
3.P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下关系:, a. o3 c" x4 V3 `4 o
: L& O% L7 ]- N- v; t; w
x3≡k2-x1-x2(mod p)
y3≡k(x1-x3)-y1(mod p)/ G8 q6 r6 D3 `) s
" H5 h. |& W! b8 Y7 n
若P=Q 则 k=(3x2+a)/2y1mod p& K w+ F; U: [1 e: c! @, Y0 J7 k/ Q
若P≠Q,则k=(y2-y1)/(x2-x1) mod p6 Q0 E. H k. S, v2 F
例题椭圆曲线已知E23(1,1)上两点P(3,10),Q(9,7),求(1)-P,(2)P+Q,(3) 2P
补充:% F" o* m. g+ e3 P2 w
2 Y: A' [/ p3 f7 q
-2^(-1) mod 23 进行两部分计算
$ A, W5 O; X8 f% ]0 I h
(1) 先算 2^(-1) 对应的数A, 在这里2^(-1)不是2的-1次方,而是2的逆元
7 G# ? ] t: ~2 X2 p$ P) _
(2) 再算-A mod 23
+ s6 u9 O# Q; i" |# i# u& H A
(1) 计算第一步
根据有限域除法规则 2 * 2^(-1) = 1 mod 23
即 2A = 1 mod 23 ==> 2A = 23 + 1 == > A = 12+ K* T) ?$ i6 n A" Y
(2) 计算第二步
2 ^* {. \' o9 O! q, ]9 K( C" Q5 y& D
-A mod 23 ==> -12 mod 23 即 23 -12 = 117 |0 v# Q6 Z( O+ E* G
所以有
, u6 J# [# Z# ^1 [" x b3 e" |
-2^(-1) mod 23 = 115 @8 Z1 I4 J9 \$ {: b/ G) F$ C
9 P D; x. c. t
有限域椭圆曲线点的阶4 Z) _! |/ c1 ]# ?9 }
如果椭圆曲线上一点P,存在最小的正整数n使得数乘nP=O∞ ,则将n称为P的阶8 X/ t% z2 U2 g( b' N
若n不存在,则P是无限阶的
0 u0 B2 c; a6 Z- _9 c9 c
计算可得27P=-P=(3,13)
所以28P=O ∞ P的阶为28. {+ g0 y* S* \ B
这些点做成了一个循环阿贝尔群,其中生成元为P,阶数为29。显然点的分布与顺序都是杂乱无章
椭圆曲线加密
0 N; p2 T: l: i" l
考虑K=kG ,其中K、G为椭圆曲线Ep(a,b)上的点,n为G的阶(nG=O∞ ),k为小于n的整数。则给定k和G,根据加法法则,计算K很容易但反过来,给定K和G,求k就非常困难。因为实际使用中的ECC原则上把p取得相当大,n也相当大,要把n个解点逐一算出来列成上表是不可能的。这就是椭圆曲线加密算法的数学依据
3 n! z$ k. b0 t6 v$ \+ R, F
点G称为基点(base point)
k(k
K为公开密钥(public key)2 N& K6 h& o2 }" k4 N
- @" x/ }1 e9 \5 I0 _
ECC保密通信算法
1.Alice选定一条椭圆曲线E,并取椭圆曲线上一点作为基点G 假设选定E29(4,20),基点G(13,23) , 基点G的阶数n=371 v( {4 {1 w6 h$ m, s1 |
& ~, w q! ?* J* L
2.Alice选择一个私有密钥k(k8 G W9 j% R, O8 u
: x9 i1 t0 x: D
3.Alice将E和点K、G传给Bob
; o8 D4 s7 k+ A
4.Bob收到信息后,将待传输的明文编码到上的一点M(编码方法略),并产生一个随机整数r(r* b, i4 q, {% R" t7 D, ?
5.Bob计算点C1=M+rK和C2=rG C1= M+6K= M+625G=M+2G=(3,28)+(27,27)=(6,12) C2=6G=(5,7)& m1 w3 ]! t0 s% u
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)
+ a- c# U6 b1 G# S2 R: o
数学原来上能解密是因为:C1-kC2=M+rK-krG=M+rkG-krG-M! {, o& g* E$ i j& A! A
ECC技术要求
通常将Fp上的一条椭圆曲线描述为T=(p,a,b,G,n,h)p、a、b确定一条椭圆曲线(p为质数,(mod p)运算)G为基点,n为点G的阶,h是椭圆曲线上所有点的个数m与n相除的商的整数部分: E/ ^- i5 B: ^6 A
参量选择要求:3 r& j5 k5 n2 b- D
p越大安全性越好,但会导致计算速度变慢200-bit左右可满足一般安全要求n应为质数h≤4;p≠n×h ;pt≠1(mod n) (1≤t<20)4a3+27b2≠0 (mod p)- K) w4 h. [0 ]* R2 G
ECC的应用
8 l) ^0 z8 t5 o/ Q/ M" K
比特币系统选用的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+ d9 o3 a7 P) E- G+ O- H. a
5 ]0 ~: h5 W/ ?+ o( D2 F* O7 m
a = 0, b = 7 t* G* O. |+ X. D4 y2 {5 A0 Y( E
G=(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
1 v d, H3 @( a6 ^! s6 @6 g0 W' i
n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141( m& k9 y1 @) l2 z/ C+ {% L3 n
9 Y9 y1 A7 }4 E" H; x: L
h = 01
ECC vs. RSA - 优缺点
优点
8 F7 A4 d: u2 G' p* i
安全性能更高7 m4 T. T" C4 q/ B* W* o1 V, Y9 o5 }
160位ECC与1024位RSA、DSA有相同的安全强度
' @' v+ i3 z/ L
处理速度更快, |; ~8 l3 v5 _+ p0 v
在私钥的处理速度上,ECC远 比RSA、DSA快得多
/ v: H5 l. `' O' _& A' N7 ^
带宽要求更低
; e, B: n- J0 c+ B' P; f
存储空间更小
ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多
缺点' ]- J, W( g4 T$ m _( n. J# W
设计困难,实现复杂
如果序列号设计过短,那么安全性并没有想象中的完善6 N+ R4 d* U8 A( v4 e! R% `
成为第一个吐槽的人