5 y# f" p% p. y" z! A0 _. ~
ECC英文全称"Ellipse Curve Cryptography"6 e, y. s. ]8 B, J3 X: d ?6 Q
与传统的基于大质数因子分解困难性的加密方法不同,ECC通过椭圆曲线方程式的性质产生密钥! Z6 r% e5 V- F; P+ M
+ O( ?" w. Z6 i. ]6 f( \
ECC164位的密钥产生一个安全级,相当于RSA 1024位密钥提供的保密强度,而且计算量较小,处理速度更快,存储空间和传输带宽占用较少。目前我国居民二代身份证正在使用 256 位的椭圆曲线密码,虚拟货币比特币也选择ECC作为加密算法。8 f- T" m1 S% V- l- z8 O
从射影平面讲起; Z+ U- B3 J- v3 ]; | G
) d3 p/ s! P! x0 q
古希腊数学家欧几里得的《几何原本》提出了五条公设。
1.由任意一点到任意一点可作直线。, u' V, z* r6 O! q1 H
7 x, J$ g) z& d! ?5 q' h
2.一条有限直线可以继续延长。
2 Y, p" U7 Y5 L6 W$ p+ B5 {5 M
3.以任意点为心及任意的距离可以画圆。+ g( A* D& T# x. y: U# H
# e% o0 n* n+ e( ~6 w% q
4.凡直角都相等。
5.同一平面内一条直线a和另外两条直线b.c相交,若在a某一侧的两个内角的和小于两直角,则b.c两直线经无限延长后在该侧相交。
/ B$ r6 z8 J& O7 _5 ?4 s% w
《几何原本》只有在第29个命题- W' U _, q% [1 }! E' i( [2 i
一条直线与两条平行直线相交,则所成的内错角相等,同位角相等,且同旁内角之和等于两直角1 k9 r2 k( H- Z/ U& H4 \- S: Z# d
4 ]$ A/ t. p( C/ ?# N- R3 ]# j
中才用到第五公设,即《几何原本》中可不依靠第五公设而推出前28命题。因此,一些数学家提出,第五公设能不能不作为公设,而作为定理?能不能依靠前四个公设来证明第五公设?这就是几何发展史上最著名的,争论了长达两千多年的关于“平行线理论”的讨论, Y- l/ @: r! O+ ?! Z. Z6 Y
1820年代,俄国喀山大学罗巴切夫斯基用“至少可以找到两条相异的直线,且都通过P点,并不与直线R相交”代替第五公设,然后与欧氏几何的前四个公设结合成一个公理系统,他经过细致深入的推理过程中,得出了一个又一个在直觉上匪夷所思,但在逻辑上毫无矛盾的几何体系。
/ n) R; X+ u9 H9 @0 Q+ p
这种几何学被称为罗巴切夫斯基几何,简称罗氏几何。从罗氏几何学中,可以得出这样一个结论:逻辑上不矛盾的一些公理都有可能提供一种几何学。现存非欧几何的类型可以概括如下:
/ g0 `! s- s) n# {
1.坚持第五公设,引出欧几里得几何。$ j5 a8 o6 y7 h6 K9 n( q8 [( |# O
" {; o ^; b& P: _
2.“可以引最少两条平行线”为公设,罗氏几何(双曲几何)。( U: {8 _; {+ ?3 f* D1 q4 e
3.“一条平行线也不能引”为公设,黎曼几何(椭圆几何)
左:双曲几何,即罗氏几何;中:欧几里德几何;右:椭圆几何,即黎曼几何4 _' t7 a* E$ W( y+ ?( k; Q
了解非欧式几何,就可以理解平行线的交点。
; A( d& Q, U1 s
定义平行线相交于无穷远点P∞,使平面上所有直线都统一为有唯一的交点
性质:
1.一条直线只有一个无穷远点;一对平行线有公共的无穷远点/ I% C2 q# ?+ L" \) y# o' H( u
2.任何两条不平行的直线有不同的无穷远点(否则会造成有两个交点)4 H7 O* }1 m! C, d
: ]: {/ z9 a9 D
3.平面上全体无穷远点构成一条无穷远直线, W, e4 t( U/ B* r- Z9 H
射影平面:平面上全体无穷远点与全体平常点构成射影平面/ s+ g5 c% S. Q2 C# \5 [" Q9 n
1 r; | e, p# \6 z7 s
射影平面点的定义3 f; a' k# `& _' V6 ~
对普通平面上点(x,y),令x=X/Z,y=Y/Z,Z≠0,则投影为射影平面上的点(X:Y:Z)
求点(1,2)在新的坐标体系下的坐标, r4 j C8 L) I/ j+ `, B6 v7 |
3 T) \# P7 q9 P# r* K/ T
∵X/Z=1 ,Y/Z=2(Z≠0)5 x8 d) x A6 Z0 H8 b4 U. e1 Z
∴X=Z,Y=2Z ∴坐标为(Z:2Z:Z),Z≠0
4 R/ Y. y1 y' ^+ H( X7 L* u! L
即(1:2:1)(2:4:2)(1.2:2.4:1.2)等形如(Z:2Z:Z),Z≠0的坐标都是(1,2)在新的坐标体系下的坐标) D8 B9 C8 p+ e; z" y
+ m1 Z2 G. T8 U
(2) 求平行线L1:X+2Y+3Z=0 与L2:X+2Y+Z=0 相交的无穷远点
∵ L1∥L2 所以有Z=0, X+2Y=0
∴坐标为(-2Y:Y:0),Y≠0) l) M, m/ {& Z3 H/ z' Y
8 K9 ] E! w, m
即(-2:1:0)(-4:2:0)(-2.4:1.2:0)等形如(-2Y:Y:0),Y≠0- t4 m- e) J2 v3 |) U
/ \- L+ _, ?& z0 ?, \" Q: s7 P
椭圆曲线0 Q" }/ K, q) R
一条椭圆曲线是在射影平面上满足威尔斯特拉斯方程(Weierstrass)所有点的集合+ p& s% B$ K# o& Z k
Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z39 ]3 y4 n* K7 w& u. c; Q
9 C& D7 d, r0 D- ~1 Q" U9 ^: |
1椭圆曲线方程是一个齐次方程+ |- y( [" |: T+ H8 s' {% y
2曲线上的每个点都必须是非奇异的(光滑的),偏导数FX(X,Y,Z)、FY(X,Y,Z)、FZ(X,Y,Z)不同为0
3 K/ H& D7 N" v( H. o& N( \
3圆曲线的形状,并不是椭圆的。只是因为椭圆曲线的描述方程,类似于计算一个椭圆周长的方程故得名* n5 {" j) ?: N$ E# H' K D) N
椭圆曲线示例
7 |& A9 w3 j4 a
非椭圆曲线示例
这两个方程都不是椭圆曲线,因为他们在(0:0:1)点处(即原点)没有切线,不满足椭圆曲线每个点都必须是非奇异的(光滑的),
椭圆曲线普通方程/ \: @: i3 t2 x5 \# M2 C
椭圆曲线普通方程:& n- `: z, T; L" [2 r5 d* V
无穷远点 (0, Y, 0)- _: {% i# u% \$ r# f
. K3 N# Z/ S9 m! o3 C5 B
平常点(x,y)斜率k:# \; u6 W2 G4 x/ M b
椭圆曲线阿贝尔群+ ~& S3 {8 W; U$ {6 b/ P% l" O O9 k
* s0 V4 w/ P( G& _( `8 O: g+ q
我们已经看到了椭圆曲线的图象,但点与点之间好象没有什么联系。我们能不能建立一个类似于在实数轴上加法的运算法则呢?这就要定义椭圆曲线的加法群,这里需要用到近世代数中阿贝尔群。
" j( k }$ B" a) ?
在数学中,群是一种代数结构,由一个集合以及一个二元运算所组成。已知集合和运算(G,*)如果是群则必须满足如下要求4 ~) s* j( E! L6 Y
封闭性:?a,b∈G,a*b ∈ G$ R. n9 ?# }$ E
结合性: ?a,b,c∈G ,有 (ab)c = a* (b*c)% h1 c& {) n% p
1 r+ x4 R G3 j0 M
单位元:ョe∈G, ?a ∈G,有ea = ae = a' r. r! \3 E( b7 ^: b# k1 X) c# W
7 b7 b) K# v, b
逆元: ?a ∈G ,ョb∈G 使得 ab = ba = e
阿贝尔群除了上面的性质还满足交换律公理a * b = b * a
8 }6 w% E5 E5 _0 p8 ^# q0 {4 z
同样在椭圆曲线也可以定义阿贝尔群。
任意取椭圆曲线上两点P、Q(若P、Q两点重合,则作P点的切线),作直线交于椭圆曲线的另一点R’,过R’做y轴的平行线交于R,定义P+Q=R。这样,加法的和也在椭圆曲线上,并同样具备加法的交换律、结合律( _( s/ v/ [& ~+ M6 x5 u$ N8 J8 @) k- D3 C
同点加法
2 b9 a- b' x! b- ^
若有k个相同的点P相加,记作kP
4 \5 I& b) \' \8 q3 }# b' t M
P+P+P=2P+P=3P
3 w- X7 x# ~) o7 W1 E
有限域椭圆曲线! R$ P) a& K5 f
6 {4 u7 u( {7 n$ D/ t, U* e0 O) C
椭圆曲线是连续的,并不适合用于加密;所以,我们必须把椭圆曲线变成离散的点,我们要把椭圆曲线定义在有限域上。
我们给出一个有限域Fp
- V1 J# s8 ^1 _$ H. R# o
Fp中有p(p为质数)个元素0,1,2,…, p-2,p-1
7 V1 t' e0 Y% f
Fp的加法是a+b≡c(mod p)' M2 x8 C/ |: U$ ^9 b9 ?( c
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,零元是 02 N( u6 q7 v _5 f0 z4 r& S- o/ V
& q2 ]7 r$ y3 p1 ]! l- H
Fp域内运算满足交换律、结合律、分配律
( I/ x( D4 a G; l2 B$ Z4 r* q
椭圆曲线Ep(a,b),p为质数,x,y∈[0,p-1]
" U) @, {8 J+ l3 z' t; q
选择两个满足下列约束条件的小于p的非负整数a、b
Fp上的椭圆曲线同样有加法
c; d" f9 Z- |
1.无穷远点 O∞是零元,有O∞+ O∞= O∞,O∞+P=P' F, l8 ~ \; o6 X4 u" t+ e" K( P$ h! \
/ d" t. G% F" }" D" {- E/ w3 |& v
2.P(x,y)的负元是 (x,-y mod p)= (x,p-y) ,有P+(-P)= O∞- T/ b3 P. A# o* M
3.P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下关系:
x3≡k2-x1-x2(mod p)9 g# i* L+ V7 X0 O2 Y" z7 m
y3≡k(x1-x3)-y1(mod p)
' D- | Q! \4 U+ f, K. W/ k2 Y
若P=Q 则 k=(3x2+a)/2y1mod p
9 y4 R: p1 s9 }8 x% V# k5 ?
若P≠Q,则k=(y2-y1)/(x2-x1) mod p- }9 E/ H4 I+ N, ~9 \) v
: z/ }% N: ~4 j$ `: N
例题椭圆曲线已知E23(1,1)上两点P(3,10),Q(9,7),求(1)-P,(2)P+Q,(3) 2P
补充:
0 p( R, j+ r6 b! L2 h! E8 p
-2^(-1) mod 23 进行两部分计算
(1) 先算 2^(-1) 对应的数A, 在这里2^(-1)不是2的-1次方,而是2的逆元$ E% `! \: e5 E1 W3 R
(2) 再算-A mod 23# p2 X( L+ Q# R0 j! C! Y3 j* ^! q
8 ^9 P! v! h# P$ K+ e
(1) 计算第一步9 O: t& C& n! f! O- B; I
& @& Z0 {- d- `$ y6 b
根据有限域除法规则 2 * 2^(-1) = 1 mod 233 `; d* q' J g) |* Y6 S4 c
即 2A = 1 mod 23 ==> 2A = 23 + 1 == > A = 12
(2) 计算第二步
1 f) ^4 E% U& A" ?# m, R0 T
-A mod 23 ==> -12 mod 23 即 23 -12 = 11
所以有
7 [8 Q6 \ [9 D/ X
-2^(-1) mod 23 = 11
, T9 [, E2 f, p# m+ t! Y- v, p
有限域椭圆曲线点的阶
如果椭圆曲线上一点P,存在最小的正整数n使得数乘nP=O∞ ,则将n称为P的阶
若n不存在,则P是无限阶的
计算可得27P=-P=(3,13)
所以28P=O ∞ P的阶为28
这些点做成了一个循环阿贝尔群,其中生成元为P,阶数为29。显然点的分布与顺序都是杂乱无章. Y/ `$ U. n; Z# i! C) _$ F) f9 R
! L i/ M' v: g1 h$ G
椭圆曲线加密
! Z5 F1 {5 Y2 e
考虑K=kG ,其中K、G为椭圆曲线Ep(a,b)上的点,n为G的阶(nG=O∞ ),k为小于n的整数。则给定k和G,根据加法法则,计算K很容易但反过来,给定K和G,求k就非常困难。因为实际使用中的ECC原则上把p取得相当大,n也相当大,要把n个解点逐一算出来列成上表是不可能的。这就是椭圆曲线加密算法的数学依据4 H7 D/ v h) }: ~& V
& ^; ]! J6 d1 ^0 S3 r, W
点G称为基点(base point)! _# z N$ @4 M% r( ]2 Y% B
1 ~8 p" Q, C( l* ]2 T6 R. `' v2 Q) P
k(k
8 \3 U- q' i% C7 g$ S
K为公开密钥(public key)
ECC保密通信算法: H @! g% W. n; k6 i' \
& l1 v8 q k1 J# N
1.Alice选定一条椭圆曲线E,并取椭圆曲线上一点作为基点G 假设选定E29(4,20),基点G(13,23) , 基点G的阶数n=37
& N! @0 f8 a- p2 o0 D* r z5 p6 O
2.Alice选择一个私有密钥k(k/ \$ {$ t, [" ^' S1 h( }
' S, H3 z7 y6 J- w; K c5 Q
3.Alice将E和点K、G传给Bob
) D2 {4 ?1 _; \4 T7 t& w
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)
& v9 r8 l; f; U$ z0 }
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)& k2 c& W5 E2 J0 _% C
/ F. v, A8 ]) w, x8 h; d' L
数学原来上能解密是因为:C1-kC2=M+rK-krG=M+rkG-krG-M
ECC技术要求% w8 q0 Q3 d* @# A: l6 m' [* W
通常将Fp上的一条椭圆曲线描述为T=(p,a,b,G,n,h)p、a、b确定一条椭圆曲线(p为质数,(mod p)运算)G为基点,n为点G的阶,h是椭圆曲线上所有点的个数m与n相除的商的整数部分3 ^) i4 ^& j7 l F1 z8 c
参量选择要求:
p越大安全性越好,但会导致计算速度变慢200-bit左右可满足一般安全要求n应为质数h≤4;p≠n×h ;pt≠1(mod n) (1≤t<20)4a3+27b2≠0 (mod p)
% Z2 B% o5 P. X( Q
ECC的应用: R+ ?7 M X# I# _: L. v9 n
比特币系统选用的secp256k1中,参数为7 f# t% b7 k( }3 c$ p& q
9 t, ~2 H0 t9 Y5 k8 `, l+ u
p = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F= 2^256 ? 2^32 ? 2^9 ? 2^8 ? 2^7 ? 2^6 ? 2^4 ? 14 K+ |- `1 U* `; W! ^$ L6 D' ^
& k+ I2 q" [1 \( |# V
a = 0, b = 7
G=(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)) N( \1 i3 }! _" @7 w
. v8 g, |1 G" X* k- @
n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141& f a; f. X+ P1 C; T, w$ Q0 [; G
+ |) U- [2 s( C. K" x/ R4 o" \0 `. C* ]
h = 01; \% i, N: A! s |1 w
' I( w* x4 f; T# Y& ]4 Y
ECC vs. RSA - 优缺点+ T/ c. h2 ?& p3 ^- H1 \1 P* }& V x
) k9 b( n) s5 K% p% J: p
优点5 L" ?$ x3 d: E1 i7 }6 c; ~# [
安全性能更高: o+ S; M! | p5 F
' q$ l* Y( v _# W5 r5 N
160位ECC与1024位RSA、DSA有相同的安全强度
) T! l0 c1 I" ?/ Q- r( X$ _
处理速度更快* r% u5 B/ @/ N1 I' x' Y
9 B1 G) I3 b+ d# U- O: x i Z
在私钥的处理速度上,ECC远 比RSA、DSA快得多
带宽要求更低
' G! r5 d5 N+ \) R! j/ n% P* F
存储空间更小+ a3 G* O& O% l1 h- I
4 H9 T% y' U. F9 O' ]. @+ J
ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多9 @ _: W. h, f* k
缺点
设计困难,实现复杂/ e! m: q3 ?) t2 Y. z
+ A+ q, _, R8 m, z& D
如果序列号设计过短,那么安全性并没有想象中的完善
) W( X4 C8 t E1 J! o6 v, `
成为第一个吐槽的人