( u' j" O5 X6 c1 o/ C2 n" k4 L, o# a" z
ECC英文全称"Ellipse Curve Cryptography". u/ H. o I+ X1 A9 @
与传统的基于大质数因子分解困难性的加密方法不同,ECC通过椭圆曲线方程式的性质产生密钥
ECC164位的密钥产生一个安全级,相当于RSA 1024位密钥提供的保密强度,而且计算量较小,处理速度更快,存储空间和传输带宽占用较少。目前我国居民二代身份证正在使用 256 位的椭圆曲线密码,虚拟货币比特币也选择ECC作为加密算法。
/ l m g& z6 j- m
从射影平面讲起) T, x* e1 i! w8 l, ?4 y
古希腊数学家欧几里得的《几何原本》提出了五条公设。( [* S1 e, A8 j/ C/ _
1.由任意一点到任意一点可作直线。+ N: i0 G" g3 M# |
( E/ c* a8 G* m! H' F3 D9 d( S
2.一条有限直线可以继续延长。
3 H' f7 T6 {* B5 f C
3.以任意点为心及任意的距离可以画圆。3 T+ W ]" i& k( V+ Q/ s/ x( p; Z
4.凡直角都相等。
5.同一平面内一条直线a和另外两条直线b.c相交,若在a某一侧的两个内角的和小于两直角,则b.c两直线经无限延长后在该侧相交。, T7 R, }4 i4 {. V+ n
《几何原本》只有在第29个命题* S, n- y, f% H; k7 ]
t: | H, S, ^; {
一条直线与两条平行直线相交,则所成的内错角相等,同位角相等,且同旁内角之和等于两直角
中才用到第五公设,即《几何原本》中可不依靠第五公设而推出前28命题。因此,一些数学家提出,第五公设能不能不作为公设,而作为定理?能不能依靠前四个公设来证明第五公设?这就是几何发展史上最著名的,争论了长达两千多年的关于“平行线理论”的讨论
( p: Z1 B1 O9 @& Z0 D ]
1820年代,俄国喀山大学罗巴切夫斯基用“至少可以找到两条相异的直线,且都通过P点,并不与直线R相交”代替第五公设,然后与欧氏几何的前四个公设结合成一个公理系统,他经过细致深入的推理过程中,得出了一个又一个在直觉上匪夷所思,但在逻辑上毫无矛盾的几何体系。, [$ H( k5 l5 w& J0 r2 b
. k7 o- K, {' o0 l
这种几何学被称为罗巴切夫斯基几何,简称罗氏几何。从罗氏几何学中,可以得出这样一个结论:逻辑上不矛盾的一些公理都有可能提供一种几何学。现存非欧几何的类型可以概括如下:$ m8 |% z/ f! h6 [2 C: ^
8 T" C0 |! T/ ~9 ?7 W: X! b- k
1.坚持第五公设,引出欧几里得几何。
2.“可以引最少两条平行线”为公设,罗氏几何(双曲几何)。
G# R6 W4 V8 ?
3.“一条平行线也不能引”为公设,黎曼几何(椭圆几何)
左:双曲几何,即罗氏几何;中:欧几里德几何;右:椭圆几何,即黎曼几何" x# ?4 \( a% {% A2 `: c# R( n
了解非欧式几何,就可以理解平行线的交点。$ ]4 ?7 K# Z6 P1 R% |% k
& y6 r$ H2 R$ Z# x6 e* o% c
定义平行线相交于无穷远点P∞,使平面上所有直线都统一为有唯一的交点
性质:& C9 z& q5 _/ M* r" W' m, ?& f- j! u+ |
1.一条直线只有一个无穷远点;一对平行线有公共的无穷远点
$ N2 G3 |# j7 Z
2.任何两条不平行的直线有不同的无穷远点(否则会造成有两个交点)0 o2 I5 ]; u. ]' ^
- J) y' L$ t4 }
3.平面上全体无穷远点构成一条无穷远直线/ @$ ~* ~: v6 x. T
, l$ E8 k" | n# u3 J; a
射影平面:平面上全体无穷远点与全体平常点构成射影平面% B, G( n9 b v- |8 x
0 |% y. N; y+ y1 d. W
射影平面点的定义
对普通平面上点(x,y),令x=X/Z,y=Y/Z,Z≠0,则投影为射影平面上的点(X:Y:Z). ?' @# j5 e! f. T2 S3 y0 z7 k/ M
: @8 k3 v/ H7 {: N# [% B
求点(1,2)在新的坐标体系下的坐标
∵X/Z=1 ,Y/Z=2(Z≠0)+ b A+ }0 A' y/ e9 f1 Q
# Y. Y7 w, o5 a4 x1 \; B( R0 r4 m/ d
∴X=Z,Y=2Z ∴坐标为(Z:2Z:Z),Z≠0" D* d/ t1 r& d* T" x. {
4 M Y1 B0 t2 M# _; A: x
即(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 相交的无穷远点5 m+ W- u$ k- Z8 P4 h
; ~. r1 g0 L. j( ]% }6 a
∵ L1∥L2 所以有Z=0, X+2Y=0
8 K' m! ]0 s" `+ `; ~' I- n4 }
∴坐标为(-2Y:Y:0),Y≠0
即(-2:1:0)(-4:2:0)(-2.4:1.2:0)等形如(-2Y:Y:0),Y≠0* G$ a9 j) p$ Q+ f
椭圆曲线
一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程(Weierstrass)所有点的集合0 k' d9 E9 V: u4 b( L0 N6 J
Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3
) A; M: `; {, ]$ |$ f7 T
1椭圆曲线方程是一个齐次方程) |$ z! \& m+ y. p, H, S
' W8 m: c9 h+ u7 N" r, {* F7 T
2曲线上的每个点都必须是非奇异的(光滑的),偏导数FX(X,Y,Z)、FY(X,Y,Z)、FZ(X,Y,Z)不同为0" u/ G' ~ [( C0 W# V0 Q9 j
3圆曲线的形状,并不是椭圆的。只是因为椭圆曲线的描述方程,类似于计算一个椭圆周长的方程故得名
5 n! Q0 j" F( g6 w V; S. }' i6 t0 y- {9 ]
椭圆曲线示例" M7 t) F& d% K/ f
6 Y' a6 C" x, F
非椭圆曲线示例: x# u+ K8 z+ _) W+ X; u6 T
: Q. C1 J8 h) T, w
这两个方程都不是椭圆曲线,因为他们在(0:0:1)点处(即原点)没有切线,不满足椭圆曲线每个点都必须是非奇异的(光滑的),
5 E* r6 I: X* a* b/ V) R1 V
椭圆曲线普通方程' q% L( t- n- ?0 h/ a$ X
椭圆曲线普通方程:( ~2 m2 x* ^( D0 o7 t- m& S: O
无穷远点 (0, Y, 0)
平常点(x,y)斜率k:$ x# l9 z# D& V0 f5 a
% h/ p! i! O5 U
椭圆曲线阿贝尔群' o3 z# F& R1 \/ v' I L
我们已经看到了椭圆曲线的图象,但点与点之间好象没有什么联系。我们能不能建立一个类似于在实数轴上加法的运算法则呢?这就要定义椭圆曲线的加法群,这里需要用到近世代数中阿贝尔群。
" {! {% @" f: V4 w4 D2 U0 s
在数学中,群是一种代数结构,由一个集合以及一个二元运算所组成。已知集合和运算(G,*)如果是群则必须满足如下要求
~8 }) v Z2 w
封闭性:?a,b∈G,a*b ∈ G Y4 ~( K9 I" \3 G: Y; Q
结合性: ?a,b,c∈G ,有 (ab)c = a* (b*c): h2 w2 w% o" b) T5 J- ^
# _( N$ P G$ g0 d! @+ t+ W* w
单位元:ョe∈G, ?a ∈G,有ea = ae = a6 K" Z: S# B: K0 p1 I7 G4 P. `% h
& V, }. z* `; f
逆元: ?a ∈G ,ョb∈G 使得 ab = ba = e
$ N6 W% \, z( I- D
阿贝尔群除了上面的性质还满足交换律公理a * b = b * a# K# F* h- S/ A) D G
同样在椭圆曲线也可以定义阿贝尔群。: h- ^" f% p5 s$ U0 Q4 E+ z
任意取椭圆曲线上两点P、Q(若P、Q两点重合,则作P点的切线),作直线交于椭圆曲线的另一点R’,过R’做y轴的平行线交于R,定义P+Q=R。这样,加法的和也在椭圆曲线上,并同样具备加法的交换律、结合律
% e& ?5 J! |* X7 e; u- ]# l i& {
同点加法
8 o& ] ~, z5 t! A' O9 R W3 p
若有k个相同的点P相加,记作kP
) U" K B$ I6 T( ?: S
P+P+P=2P+P=3P! c/ W; d. F |" u
有限域椭圆曲线
/ d1 w: v/ J% k1 g" Y! ^. w
椭圆曲线是连续的,并不适合用于加密;所以,我们必须把椭圆曲线变成离散的点,我们要把椭圆曲线定义在有限域上。
我们给出一个有限域Fp
Fp中有p(p为质数)个元素0,1,2,…, p-2,p-1
" y1 b6 ?, x/ h S0 \
Fp的加法是a+b≡c(mod p)
* ]* _. Z7 T( _2 p! v3 ]& i
Fp的乘法是a×b≡c(mod p); z! X/ q4 D6 t; \4 R
Fp的除法是a÷b≡c(mod p),即 a×b^(-1)≡c (mod p),b-1也是一个0到p-1之间的整数,但满足b×b-1≡1 (mod p)
7 f: d/ ~3 @1 U, f/ d4 ~
Fp的单位元是1,零元是 03 \, B# c( {5 a
Fp域内运算满足交换律、结合律、分配律
椭圆曲线Ep(a,b),p为质数,x,y∈[0,p-1]
. o& X: y' H9 k5 D# `% ]. c: M, _
选择两个满足下列约束条件的小于p的非负整数a、b
+ {; q4 }) Q: d. c0 s
Fp上的椭圆曲线同样有加法! b8 X/ I e: t+ i, }/ \" @3 T
1.无穷远点 O∞是零元,有O∞+ O∞= O∞,O∞+P=P
2.P(x,y)的负元是 (x,-y mod p)= (x,p-y) ,有P+(-P)= O∞
6 c% O8 k* z! m, k3 w3 I
3.P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下关系:- z% Y$ `& c0 D3 ~& J( m5 B
' `! m; T+ x# P/ [$ `$ P
x3≡k2-x1-x2(mod p)
8 W' v& m) t b: f; G( I
y3≡k(x1-x3)-y1(mod p)
若P=Q 则 k=(3x2+a)/2y1mod p
$ E+ J: c9 H4 Y/ \& Q, E5 Z
若P≠Q,则k=(y2-y1)/(x2-x1) mod p: ~4 n# m: S+ t" x6 y, Z$ [* S
6 Q. p6 @5 g6 i7 J2 f
例题椭圆曲线已知E23(1,1)上两点P(3,10),Q(9,7),求(1)-P,(2)P+Q,(3) 2P
9 V% Y0 v( W8 n- N4 t Q: }9 b
补充:; p$ U& z0 q# N* K. k) y
" I! p+ R) ~; D
-2^(-1) mod 23 进行两部分计算3 Z$ k% Y; W' H3 ~2 `; S) K/ k3 B
3 B6 b: \7 i' E% p# z4 K; b8 G
(1) 先算 2^(-1) 对应的数A, 在这里2^(-1)不是2的-1次方,而是2的逆元
/ e7 b+ P7 ~# U& ^* ^; S
(2) 再算-A mod 23
3 b0 ?) y0 N3 ^/ O3 m
(1) 计算第一步# ?# ?! N. @# R) M" I/ d! T
根据有限域除法规则 2 * 2^(-1) = 1 mod 23
8 g0 S; J. D9 r( u9 f( ]9 }7 E1 O
即 2A = 1 mod 23 ==> 2A = 23 + 1 == > A = 12/ N1 l1 S: s2 |
(2) 计算第二步
! T! M: T$ D* M/ z
-A mod 23 ==> -12 mod 23 即 23 -12 = 11
) y, c% M: w- w' F/ o [/ X! g5 z
所以有
4 V4 \0 }, v$ X: X2 h
-2^(-1) mod 23 = 11
有限域椭圆曲线点的阶! C# X, J' Y* W7 E% ?) S
2 P; Q X" }7 x2 @8 x" g
如果椭圆曲线上一点P,存在最小的正整数n使得数乘nP=O∞ ,则将n称为P的阶7 p. t! G6 o; _) a7 q+ i
若n不存在,则P是无限阶的
. T( ?8 s3 _- w' j
计算可得27P=-P=(3,13)
# s) s1 O$ `. Y: G" t: ?
所以28P=O ∞ P的阶为28$ W( G2 I+ I: j. `$ y
这些点做成了一个循环阿贝尔群,其中生成元为P,阶数为29。显然点的分布与顺序都是杂乱无章
1 V- w" s3 g' x) D
椭圆曲线加密: g+ ^+ i: L$ i2 i# W2 u
7 e$ c# _& j$ }; @* O6 i: V6 E) E' z
考虑K=kG ,其中K、G为椭圆曲线Ep(a,b)上的点,n为G的阶(nG=O∞ ),k为小于n的整数。则给定k和G,根据加法法则,计算K很容易但反过来,给定K和G,求k就非常困难。因为实际使用中的ECC原则上把p取得相当大,n也相当大,要把n个解点逐一算出来列成上表是不可能的。这就是椭圆曲线加密算法的数学依据
1 N1 d) x5 p* f8 |$ |$ s' F+ H+ { Z
点G称为基点(base point): r" s f# M) q$ ]
k(k" O+ Q+ h. }& G
. _- h, o- z7 r' r6 o8 U8 R$ f+ `3 t
K为公开密钥(public key)
ECC保密通信算法& i5 }; B4 P+ ] G9 o0 s+ y- h
4 D" q' }9 }! I5 z' Z' k! [
1.Alice选定一条椭圆曲线E,并取椭圆曲线上一点作为基点G 假设选定E29(4,20),基点G(13,23) , 基点G的阶数n=37* F0 V' ^5 x/ |' x' ]# } U
2.Alice选择一个私有密钥k(k% M0 E# D: L" u4 d# a9 E
9 [0 }9 N6 N! b& `4 l9 i3 Y& Q
3.Alice将E和点K、G传给Bob
/ M# C' b, S4 g4 v! B
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)
* u, U% y! D/ r& P2 M0 E9 f
6.Bob将C1、C2传给Alice
0 {8 Z1 O* j" [+ [" R
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 c. b# @% N( l& Y1 C, Y
& v' [6 A& O- V- F# Q! V2 C7 s
ECC技术要求
' a2 @2 ?0 L( K
通常将Fp上的一条椭圆曲线描述为T=(p,a,b,G,n,h)p、a、b确定一条椭圆曲线(p为质数,(mod p)运算)G为基点,n为点G的阶,h是椭圆曲线上所有点的个数m与n相除的商的整数部分1 v2 n# n' v: R( ?2 ~: Q/ i
4 I* H5 Z7 d6 }: k2 u- j2 j7 k
参量选择要求:; L- B, |6 l. j& t3 P4 @- [ g
4 }2 z; B# E j
p越大安全性越好,但会导致计算速度变慢200-bit左右可满足一般安全要求n应为质数h≤4;p≠n×h ;pt≠1(mod n) (1≤t<20)4a3+27b2≠0 (mod p)' a; P, r2 D4 Z2 N5 }
ECC的应用& y% r: Y9 [9 ^! x5 j
比特币系统选用的secp256k1中,参数为
2 g' z- d0 b% t' N
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 = 76 i) s @/ c/ B1 E& a( b
G=(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
9 T! V _$ \9 ^
n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141* |' y9 v1 t% ~1 P; z6 I
4 [: E! O9 V! B# @+ T
h = 01
1 R. W3 s4 l4 K% `& Y0 r% H1 H
ECC vs. RSA - 优缺点
- ~" V* O' O: J0 i! ?- f1 S4 S
优点
! O- U6 a6 y: ~' Y! Z6 E
安全性能更高
; y/ }! l$ L( T3 C9 ~
160位ECC与1024位RSA、DSA有相同的安全强度
处理速度更快
! T' ?7 T4 c k$ _5 O6 e
在私钥的处理速度上,ECC远 比RSA、DSA快得多* A3 I+ l4 ~8 E
/ t, k) Y- b8 s
带宽要求更低
2 j& [) l( S3 s
存储空间更小
, Y- k: m: @6 B2 F1 u
ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多6 i* g1 d: G# y
. ?, b" G" ]" c# I2 `* W
缺点7 z- m: I) ^$ t, ~
' O5 ]9 L# X( G k1 C( D$ b+ _; i+ V
设计困难,实现复杂7 Z. @( X: ?: K' h
0 ?0 K: R3 o& `
如果序列号设计过短,那么安全性并没有想象中的完善" v, q; w3 Y' w' S
成为第一个吐槽的人