ECC椭圆曲线详解(有具体实例)

  • 时间:
  • 浏览:0
  • 来源:大发快三_快三最新版_大发快三最新版

前言

ECC英文全称"Ellipse Curve Cryptography"

与传统的基于大质数因子分解困难性的加密土措施不同,ECC通过椭圆曲线方程式的性质产生密钥

ECC164位的密钥产生有2个 安全级,为宜RSA 1024位密钥提供的保密速率单位单位 ,怎么让计算量较小,解决速率单位单位 快一点 ,存储空间和传输速率单位单位 占用较少。目前我国居民二代身份证正在使用 256 位的椭圆曲线密码,虚拟货币比特币也选折 ECC作为加密算法。

从射影平面讲起

古希腊数学家欧几里得的《几何原先》提出了五条公设。

  • 1.由任意其他到任意其他可作直线。

  • 2.一根有限直线可不都要继续延长。

  • 3.以任意点为心及任意的距离可不都要画圆。

  • 4.凡直角都相等。

  • 5.同一平面内一根直线a和另外两条直线b.c相交,若在a某一侧的有2个 内角的和小于两直角,则b.c两直线经无限延长后在该侧相交。

《几何原先》越来越在第29个命题

一根直线与两条平行直线相交,则所成的内错角相等,同位角相等,且同旁内角之和等于两直角

中才用到第五公设,即《几何原先》中可不依靠第五公设而推出前28命题。怎么让,其他数学家提出,第五公设可不都要不作为公设,而作为定理?可不都要依靠前兩个公设来证明第五公设?这其他其他几何发展史上最著名的,争论了长达两千多年的关于“平行线理论”的讨论

1820年代,俄国喀山大学罗巴切夫斯基用“为宜可不都要找到两条相异的直线,且都通过P点,并非 与直线R相交”代替第五公设,怎么让与欧氏几何的前兩个公设结合成有2个 公理系统,他经过细致深入的推理过程中,得出了有2个 又有2个 在直觉上匪夷所思,但在逻辑上毫无矛盾的几何体系。

你这俩几何学被称为罗巴切夫斯基几何,简称罗氏几何。从罗氏几何学中,可不都要得出原先有2个 结论:逻辑上不矛盾的其他公理都要肯能提供本身几何学。现存非欧几何的类型可不都要概括如下:

1.坚持第五公设,引出欧几里得几何。

2.“可不都要引为宜两条平行线”为公设,罗氏几何(双曲几何)。

3.“一根平行线其他其他能引”为公设,黎曼几何(椭圆几何)

左:双曲几何,即罗氏几何;中:欧几里德几何;右:椭圆几何,即黎曼几何

了解非欧式几何,就可不都要理解平行线的交点。

定义平行线相交于无穷远点P∞,使平面上所有直线都统一为有唯一的交点

性质:

  • 1.一根直线越来越有2个 无穷远点;一对平行线有公共的无穷远点

  • 2.任何两条不平行的直线有不同的无穷远点(怎么让会造成有有2个 交点)

  • 3.平面上全体无穷远点构成一根无穷远直线

射影平面:平面上全体无穷远点与全体平常点构成射影平面

射影平面点的定义

对普通平面上点(x,y),令x=X/Z,y=Y/Z,Z≠0,则投影为射影平面上的点(X:Y:Z)

求点(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)在新的坐标体系下的坐标

(2) 求平行线L1:X+2Y+3Z=0 与L2:X+2Y+Z=0 相交的无穷远点

∵ L1∥L2 其他其他有Z=0, X+2Y=0

∴坐标为(-2Y:Y:0),Y≠0

即(-2:1:0)(-4:2:0)(-2.4:1.2:0)等形如(-2Y:Y:0),Y≠0

椭圆曲线

一根椭圆曲线是在射影平面上满足威尔斯特拉斯方程(Weierstrass)所不得劲的集合

\[ {Y^2}Z + {a_1}XYZ + {a_3}Y{Z^2} = {X^3} + {a_2}{X^2}Z + {a_4}X{Z^2} + {a_6}{Z^3} \]

  • 1椭圆曲线方程是有2个 齐次方程

  • 2曲线上的每个点都都只是 非奇异的(光滑的),偏导数FX(X,Y,Z)、FY(X,Y,Z)、FZ(X,Y,Z)不同为0

  • 3圆曲线的形状,并非 是椭圆的。其他其他肯能椭圆曲线的描述方程,累似 于计算有2个 椭圆周长的方程故得名

椭圆曲线示例

非椭圆曲线示例

这有2个 方程都只要椭圆曲线,肯能让让让我们在(0:0:1)点处(即原点)越来越切线,不满足椭圆曲线每个点都都只是 非奇异的(光滑的),

椭圆曲线普通方程

椭圆曲线普通方程:

\[ {y^2} + {a_1}xy + {a_3}y = {x^3} + {a_2}{x^2} + {a_4}x + {a_6} \]

无穷远点 (0, Y, 0)

平常点(x,y)斜率k:

\[ \begin{array}{l} {F_x}\left( {x,y} \right) = {a_1}y - 3{x^2} - 2{a_2}x - {a_4} \\ {F_y}\left( {x,y} \right) = 2y + {a_1}x + {a_3} \\ \end{array} \]

\[ \begin{array}{l} k = - \frac{{{F_x}\left( {x,y} \right)}}{{{F_y}\left( {x,y} \right)}} = \frac{{3{x^2} + 2{a_2}x + {a_4} - {a_1}y}}{{2y + {a_1}x + {a_3}}} \end{array} \]

椭圆曲线阿贝尔群

让让让我们肯能想看 了椭圆曲线的图象,但点与点之间好象越来越哪几种联系。让让让我们可不都要建立有2个 累似 于在实数轴上加法的运算法则呢?这就要定义椭圆曲线的加法群,这里都要用到近世代数中阿贝尔群。

在数学中,群是本身代数形状,由有2个 集合以及有2个 二元运算所组成。已知集合和运算(G,*)肯能是群则都要满足如下要求

  • 封闭性:∀a,b∈G,a*b ∈ G

  • 结合性: ∀a,b,c∈G ,有 (ab)c = a* (b*c)

  • 单位元:ョe∈G, ∀a ∈G,有ea = ae = a

  • 逆元: ∀a ∈G ,ョb∈G 使得 ab = ba = e

阿贝尔群除了上端的性质还满足交换律公理a * b = b * a

同样在椭圆曲线也可不都要定义阿贝尔群。

任意取椭圆曲线上两点P、Q(若P、Q两点重合,则作P点的切线),作直线交于椭圆曲线的另其他R',过R'做y轴的平行线交于R,定义P+Q=R。原先,加法的和也在椭圆曲线上,并同样具备加法的交换律、结合律

同点加法

若有k个相同的点P相加,记作kP

P+P+P=2P+P=3P

有限域椭圆曲线

椭圆曲线是连续的,并非 适合用于加密;其他其他,让让让让我们要把椭圆曲线变成离散的点,让让让我们要把椭圆曲线定义在有限域上。

让让让我们给出有2个 有限域Fp

  • Fp带有p(p为质数)个元素0,1,2,…, p-2,p-1

  • Fp的加法是a+b≡c(mod p)

  • Fp的乘法是a×b≡c(mod p)

  • Fp的除法是a÷b≡c(mod p),即 a×b^(-1)≡c (mod p),b-1也是有2个 0到p-1之间的整数,但满足b×b-1≡1 (mod p)

  • Fp的单位元是1,零元是 0

  • Fp域内运算满足交换律、结合律、分配律

椭圆曲线Ep(a,b),p为质数,x,y∈[0,p-1]

\[{y^2} = {x^3} + ax + b\left( {\bmod p} \right)\]

选折 有2个 满足下列约束条件的小于p的非负整数a、b

\[4{a^3} + 27{b^2} \ne 0\left( {\bmod p} \right)\]

Fp上的椭圆曲线同样有加法

  • 1.无穷远点 O∞是零元,有O∞+ O∞= O∞,O∞+P=P

  • 2.P(x,y)的负元是 (x,-y mod p)= (x,p-y) ,有P+(-P)= O∞

  • 3.P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下关系:

x3≡k2-x1-x2(mod p)

y3≡k(x1-x3)-y1(mod p)

若P=Q 则 k=(3x2+a)/2y1mod p

若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

\[\begin{array}{l} \left( 1 \right) - P = \left( {3, - 10\bmod 23} \right) = \left( {3,13} \right) \\ \\ \left( 2 \right)k = \frac{{7 - 10}}{{9 - 3}} = - {2^{ - 1}}\bmod 23 \\ 2 \cdot {2^{ - 1}} = 1\bmod 23 \Rightarrow {2^{ - 1}} = 12 \\ k = - 12\bmod 23 = 11 \\ P + Q = \left( {{{11}^2} - 3 - 9\bmod 23,11 \times \left( {3 - \left( { - 6} \right)} \right)\bmod 23} \right) = \left( {17,20} \right) \\ \\ \left( 3 \right)k = \frac{{3 \times {3^2} + 1}}{{2 \times 10}}\bmod 23 = 7 \cdot {5^{ - 1}}\bmod 23 \\ 5 \cdot {5^{ - 1}} = 1\bmod 23 \Rightarrow {5^{ - 1}} = 14 \\ k = 7 \cdot 14\bmod 23 = 6 \\ 2P = \left( {{6^2} - 3 - 3\bmod 23,6 \times \left( {3 - 7} \right)\bmod 23} \right) = \left( {7,12} \right) \\ \end{array} \]

补充:

-2^(-1) mod 23 进行两要素计算

(1) 先算 2^(-1) 对应的数A, 在这里2^(-1)都要2的-1次方,其他其他2的逆元

(2) 再算-A mod 23

(1) 计算第一步

根据有限域除法规则 2 * 2^(-1) = 1 mod 23

即 2A = 1 mod 23 ==> 2A = 23 + 1 == > A = 12

(2) 计算第二步

-A mod 23 ==> -12 mod 23 即 23 -12 = 11

其他其他有

-2^(-1) mod 23 = 11

有限域椭圆曲线点的阶

肯能椭圆曲线上其他P,趋于稳定最小的正整数n使得数乘nP=O∞ ,则将n称为P的阶

若n不趋于稳定,则P是无限阶的

计算可得27P=-P=(3,13)

其他其他28P=O ∞ P的阶为28

哪几种点做成了有2个 循环阿贝尔群,其中生成元为P,阶数为29。显然点的分布与顺序都要杂乱无章

椭圆曲线加密

考虑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)

k(k<n)为私有密钥(privte key)

K为公开密钥(public key)

ECC保密通信算法

  • 1.Alice选定一根椭圆曲线E,并取椭圆曲线上其他作为基点G 假设选定E29(4,20),基点G(13,23) , 基点G的阶数n=37

  • 2.Alice选折 有2个 私有密钥k(k<n),并生成公开密钥K=kG 比如25, K= kG = 25G = (14,6)

  • 3.Alice将E和点K、G传给Bob

  • 4.Bob收到信息后,将待传输的明文编码到上的其他M(编码土措施略),并产生有2个 随机整数r(r<n,n为G的阶数) 假设r=6 要加密的信息为3,肯能M也要在E29(4,20) 其他其他M=(3,28)

  • 5.Bob计算点C1=M+rK和C2=rG C1= M+6K= M+6*25*G=M+2G=(3,28)+(27,27)=(6,12) C2=6G=(5,7)

  • 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)

数学原先可不都要解密是肯能:C1-kC2=M+rK-krG=M+rkG-krG-M

ECC技术要求

通常将Fp上的一根椭圆曲线描述为T=(p,a,b,G,n,h)p、a、b选折 一根椭圆曲线(p为质数,(mod p)运算)G为基点,n为点G的阶,h是椭圆曲线上所不得劲的个数m与n相除的商的整数要素

参量选折 要求:

  • p越大安全性越好,怎么让愿因计算速率单位单位 快一点
  • 150-bit左右可满足一般安全要求
  • n应为质数
  • h≤4;p≠n×h ;pt≠1(mod n) (1≤t<20)
  • 4a3+27b2≠0 (mod p)

ECC的应用

比特币系统选折 的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

G=(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

h = 01

ECC vs. RSA - 优缺点

优点

  • 安全性能更高

  • 1150位ECC与1024位RSA、DSA有相同的安全速率单位单位

  • 解决速率单位单位 快一点

  • 在私钥的解决速率单位单位 上,ECC远 比RSA、DSA快得多

  • 速率单位单位 要求更低

  • 存储空间更小

  • ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多

缺点

  • 设计困难,实现多样化

  • 肯能序列号设计过短,越来越安全性并越来越想象中的完善