椭圆加密简介
椭圆加密算法
区块链入门时候最难理解的应该就时候这个椭圆加密算法,椭圆加密算法用于生成公钥生成,现在国密SM2算法的也是基于椭圆机密算法的非对称算法,这里对椭圆加密算法做个最简单的介绍,深奥的数学定理笔者也不懂。
参考:http://www.pediy.com/kssd/pediy06/pediy6014.htm
有理解不当的地方请及时指正。
椭圆加密算法是一种公钥加密体制,最初由Koblitz和Miller两人于1985年提出,其数学基础是利用椭圆曲线上的有理点构成Abel加法群上椭圆离散对数的计算困难性。
有理点:一个n维空间中的几何物体,它的每一点的坐标可以用(x_1,x_2,...,x_n)表示。如果所有x_i都是有理数,则称该点为有理点。
平行线和射影平面:初中数学中有个定理,两条平行线永不相交。那么这里我们换一种思考方式,两条平行线在无穷远处会相交,有一个交点。(不要和之前学的数学去较真)然后根据这个理解,出来下面几个无穷远处点的性质:
1.一条直线,无穷远处点就一个。(一条线你还能要求它有几个点)
2.在平面上一组互相平行的平行线在无穷远处有公共的无穷远处点。
3.平面上相交的两条线在无穷远处有不同的无穷远处点。
4.平面上所有无穷远处点构成一条直线,叫无穷远处直线,那平面上的无穷远处点和正常点构成一个射影平面。
引入一个射影平面坐标系,联系下之前初中数学学的平面直角坐标系:
那么把坐标系的任意点(x,y),改变成x=X/Z ,y=Y/Z(Z≠0)则坐标系内点可以表示为(X:Y:Z)。有三个参量的坐标就建立了新的坐标体系。例:平面(4,8),射影平面坐标(4Z,8Z,Z),那么Z不等于0,(4,8,1)(8,16,2)(6,12,1.5)这些都是(4,8)在射影平面坐标下的点。再根据初中的坐标直线方程求解,aX+bY+c1Z =0; aX+bY+c2Z =0 (c1≠c2),方程联立求解,c2Z= c1Z= -(aX+bY)且c1≠c2,aX+bY=0,那么解得(X,Y,0)来表示无穷远点。那么表示这类型的坐标体系为射影平面坐标系。
根据上述的方程式,在射影平面坐标系中的椭圆曲线的定义:
该方程名为维尔维斯特拉斯方程,椭圆曲线的形状不是椭圆,只是因为其描述的方程类似于计算一个椭圆周长的方程。到这里才明白这个名字的来历。
加法法则 :任意取椭圆曲线上两点P、Q (若P、Q两点重合,则做P点的切线)做直线交于椭圆曲线的另一点R’,过R’做y轴的平行线交于R。我们规定P+Q=R。
曲线上三个点A,B,C处于一条直线上,则A+B+C=O∞ 下面,我们利用P、Q点的坐标(x1,y1),(x2,y2),求出R=P+Q的坐标(x4,y4)。 P,Q,R'共线,设为y=kx+b, 若P≠Q,k=(y1-y2)/(x1-x2) 若P=Q,k=(3x2+2a2x+a4 -a1y) /(2y+a1x+a3) 解方程组得到: x4=k2+ka1-a2-x1-x2; y4=k(x1-x4)-y1-a1x4-a3;
到这里说椭圆曲线在密码学中的应用,其实之前把整个函数理解成一个曲线光滑的连续曲线,结合笔者之前文章讲加密中质数分解的说明,加密必须是离散的,那么把椭圆曲线定义在一个有限域上。
给出一个有限域Fp,这个域只有有限个元素。
Fp中只有p(p为素数)个元素0,1,2 …… p-2,p-1;
Fp 的加法(a+b)法则是 a+b≡c (mod p);即,(a+c)÷p的余数 和c÷p的余数相同。
Fp 的乘法(a×b)法则是 a×b≡c (mod p);
Fp 的除法(a÷b)法则是 a/b≡c (mod p);即 a×b-1≡c (mod p);(b-1也是一个0到p-1之间的整数,但满足b×b-1≡1 (mod p);)。
Fp 的单位元是1,零元是 0。
同时,并不是所有的椭圆曲线都适合加密。y2=x3+ax+b是一类可以用来加密的椭圆曲线,也是最为简单的一类。下面我们就把y2=x3+ax+b 这条曲线定义在Fp上:
选择两个满足下列条件的小于p(p为素数)的非负整数a、b
4a3+27b2≠0 (mod p)
则满足下列方程的所有点(x,y),再加上 无穷远点O∞ ,构成一条椭圆曲线。
y2=x3+ax+b (mod p)
其中 x,y属于0到p-1间的整数,并将这条椭圆曲线记为Ep(a,b)。
我们看一下y2=x3+x+1 (mod 23)的图像
椭圆曲线这里成为了离散的点。
接下来就是加密解密:
定义个等式:K=kG [其中 K,G为Ep(a,b)上的点,k为小于n(n是点G的阶)的整数]
根据加法法则,计算K很容易;但给定K和G,求k就相对困难了。 我们把点G称为基点(base point),k(k
整个加密通信过程:
1、用户A选定一条椭圆曲线Ep(a,b),并取椭圆曲线上一点,作为基点G。
2、用户A选择一个私有密钥k,并生成公开密钥K=kG。
3、用户A将Ep(a,b)和点K,G传给用户B。
4、用户B接到信息后 ,将待传输的明文编码到Ep(a,b)上一点M(编码方法很多,这里不作讨论),并产生一个随机整数r(r
5、用户B计算点C1=M+rK;C2=rG。
6、用户B将C1、C2传给用户A。
7、用户A接到信息后,计算C1-kC2,结果就是点M。
因为C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M 再对点M进行解码就可以得到明文。
最后说下椭圆曲线优点:与经典的RSA,DSA等公钥密码体制相比安全性高,160位的椭圆密钥与1024位的RSA密钥安全性相同。处理速度快。在私钥的加密解密速度上,ecc算法比RSA、DSA速度更快。存储空间占用小。带宽要求低。
大致说些椭圆加密算法,这个算法需要相当的数学基础,笔者第二次看了,也没有完全琢磨透,希望有不对的地方能及时指正,有对椭圆加密算法更简单的理解介绍的也请分享。
群内工作
磨链(mochain)社区输出计划
招募条件:
1.需要一定的区块链基础。
2.对上述任何一方面有较为深入理解。
3.每周能保证一定的空余时间来折腾。
4.了解github相关
5.人员进行筛选,时间周期比较长。
有意向联系我。
磨链在线课程
对自己擅长方面有一定的沉淀,愿意开设在线课程,会考虑和一些专业培训机构合作,要求有一定的一线经验,实实在在分享课程。有兴趣的联系,有偿工作。
磨链(mochain)社区内容输出计划
磨链社区内容输出计划,社区内划分6个模块,针对各模块细化分解,社区成员领取任务进行写作内容输出。审核通过后发布,整个过程中即是自己的一个学习提高,同时也有交流分享,模块如下:
1.区块链基础(包括密码学、共识机制、分布式、P2P网络等)
2.以太坊(入门到精通,循序渐进学习以太坊)
3.比特币(入门到精通,比特币相关内容深入琢磨)
4.超级账本(架构、运行原理、共识机制、环境搭建配置开发相关)
5.EOS(概念介绍,由浅入深,持续学习)
6.DAG(DAG的概念、原理机制、项目技术解读)
PS:想加入磨链的,或者具体参与到磨链社区内容输出计划的,请加磨链组织者微信(jackyjin09)。欢迎每一位区块链技术爱好者加入磨链,一块琢磨区块链技术。
关于磨链和相关合作
磨链”---取磨炼之意,旨在普及区块链技术,磨炼技术,更好投身区块链行业。有兴趣一块琢磨区块链技术,联系笔者微信(jackyjin09)。
磨链社区是一个纯粹的技术社区,欢迎相关技术合作,在不违反原则的前提下,积极参与合作。
你可以在这里找到我们:
磨链社区公众号:
1. 磨链社区:http://mochain.info
2. Github : https://github.com/mochain
3. Gitter 聊天: https://gitter.im/mochain
4. 知识星球: https://t.zsxq.com/M3BMVZN
5. 知乎:https://www.zhihu.com/people/mochain
(持续更新中)
合作社区