第九章椭圆曲线优秀课件.ppt

《第九章椭圆曲线优秀课件.ppt》由会员分享，可在线阅读，更多相关《第九章椭圆曲线优秀课件.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第九章椭圆曲线第1页，本讲稿共23页9.0 简介 1985 年N.Koblitz及V.S.Miller分別提出 用于加密、数字签名、密钥交换、大数分解、之树判断等 相同安全强度下，密钥比其他公钥系统（如RSA）小，且快第2页，本讲稿共23页9.1 射影几何无穷远点 射影几何与透视学 十七世纪真正成为几何学的重要分支n 非欧几何：欧几里得第五公设开普勒引入无穷远点n 把直线的平行与相交统一 经过同一无穷远点的所有直线平行一条直线的无穷远点只有一个，相交直线的无穷远点不同n 平面上全体无穷远点构成一条无穷远直线。n 平面上全体无穷远点与全体平常点构成射影平面。第3页，本讲稿共23页9.1 射影几何

2、无穷远点 十七世纪真正成为几何学的重要分支n 中心射影和平行射影两者就可以统一了n 凡是利用中心投影或者平行投影把一个图形映成另一个图形的映射，就叫做射影变换。概括的说，射影几何学是几何学的一个重要分支学科，它是专门研究图形的位置关系的，也是专门用来讨论在把点投影到直线或者平面上的时候，图形的不变性质的科学。第4页，本讲稿共23页9.1 射影几何齐次坐标 射影平面坐标系n 笛卡儿平面直角坐标系的扩展 问题：如何表示无穷远点？n 引入参数，区分无穷远点和平常点第5页，本讲稿共23页9.1 射影几何齐次坐标 欧氏坐标n 表示一个点P=(x,y)Tn 表示一条直线l:ax+by+c=0 l=(a,b

3、,c)T 引入t axz+byz+cz=0 齐次坐标：P=(xz,yz,z)T；l=(a,b,c)T 注意：n P=sPn l=sl第6页，本讲稿共23页9.1 射影几何齐次坐标 齐次坐标表示无穷远点 n 平行直线方程：aX+bY+c1Z=0；aX+bY+c2Z=0n 有c2Z=c1Z=-（aX+bY），c1c2 Z=0 n 所以无穷远点：（X：Y：0）第7页，本讲稿共23页9.2 椭圆曲线定义 射影平面坐标系下建立 一条椭圆曲线是在射影平面上满足方程 的所有点的集合，且曲线上的每个点都是非奇异（或光滑）的。第8页，本讲稿共23页9.2 椭圆曲线定义 注意：n 椭圆曲线的形状，并不是椭圆的 第

4、9页，本讲稿共23页9.2 椭圆曲线定义 注意：n 所谓“非奇异”或“光滑”的，在数学中是指曲线上任意一点的偏导数Fx(x,y,z)，Fy(x,y,z)，Fz(x,y,z)不能同时为0n 可以这样理解这个词，即满足方程的任意一点都存在切线。n 右边不是椭圆曲线第10页，本讲稿共23页9.2 椭圆曲线定义 注意：n 椭圆曲线并不一定关于x轴对称 第11页，本讲稿共23页9.2 椭圆曲线定义 注意n 椭圆曲线上有无穷远点On 可以把椭圆曲线放到普通平面直角坐标系 n 这条光滑曲线加上一个无穷远点O，组成了椭圆曲线 n 威尔斯特拉斯（weierstrass）方程第12页，本讲稿共23页9.3 椭圆曲

5、线的加法原理 运算法则：任意取椭圆曲线E上两点P、Q（若P、Q两点重合，则做P点的切线）做直线交于椭圆曲线的另一点R，过R做y轴的平行线交于R。我们规定P+Q=R 第13页，本讲稿共23页9.3 椭圆曲线的加法原理（E,+）构成交换群n 封闭n 单位元：P+e=P e=O，即零元n 逆元：P+(-P)=e n 交换律：P+Q=Q+Pn 结合律：P+Q+T=P+(Q+T)如果椭圆曲线上的三个点A、B、C，处于同一条直线上，那么他们的和等于零元，即A+B+C=O第14页，本讲稿共23页9.3 椭圆曲线的加法原理 定理9-1 P(x1,y1)，Q(x2,y2)，R=P+Q的坐标？（1）先求点-R(x

6、3,y3)因为P,Q,-R三点共线，故设共线方程为y=kx+b,其中 若PQ(P,Q两点不重合)则直线斜率k=(y1-y2)/(x1-x2)若P=Q(P,Q两点重合)则直线为椭圆曲线的切线，k=(3x2+2a2x+a4-a1y)/(2y+a1x+a3)因为：(kx+b)2+a1x(kx+b)+a3(kx+b)=x3+a2x2+a4x+a6 当三次项系数为1时；-x1x2x3 等于常数项系数，x1x2+x2x3+x3x1等于一次项系数，-(x1+x2+x3)等于二次项系数。所以x3=k2+ka1+a2+x1+x2;y3=y1-k(x1-x3);第15页，本讲稿共23页9.3 椭圆曲线的加法原理

7、定理9-1 P(x1,y1)，Q(x2,y2)，R=P+Q的坐标？（2）利用-R求R 显然有 x4=x3=k2+ka1+a2+x1+x2 y3 y4 为 x=x4 的解 故y4=-y3-(a1x+a3)=k(x1-x4)-y1-(a1x4+a3);第16页，本讲稿共23页 P-P QP+Q9.4 密码学中的椭圆曲线 把椭圆曲线定义在有限域上：离散 并不是所有的椭圆曲线都适合加密 第17页，本讲稿共23页9.4 密码学中的椭圆曲线 Fp上的椭圆曲线的加法1.无穷远点O是零元，有O+O=O，O+P=P2.P(x,y)的负元是(x,-y)，有P+(-P)=O3.P(x1,y1),Q(x2,y2)的和

8、R(x3,y3)有如下关系x3k2-x1-x2(mod p)y3k(x1-x3)-y1(mod p)其中若P=Q 则 k=(3x2+a)/2y1 若PQ，则k=(y2-y1)/(x2-x1)第18页，本讲稿共23页9.4 密码学中的椭圆曲线 椭圆曲线上简单的加密/解密n K=kG 其中 K,G为Ep(a,b)上的点，k为小于n（n是点G的阶）的整数 n 给定k和G，根据加法法则，计算K很容易；但给定K和G，求k就相对困难了。n 这就是椭圆曲线加密算法采用的难题。n 把点G称为基点（base point）n k（kn，n为基点G的阶）为私钥；K称为公钥。第19页，本讲稿共23页9.4 密码学中的

9、椭圆曲线 下面是一个利用椭圆曲线进行加密通信的过程：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（rn）。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)=M8、再对点M进行解码就可以得到明文。第20页，本讲稿共23页9.4 密码学中的椭

10、圆曲线 密码学中，描述一条Fp上的椭圆曲线，常用到六个参量：T=(p,a,b,G,n,h)。p、a、b 用来确定一条椭圆曲线，G为基点，n为点G的阶，h 是椭圆曲线上所有点的个数m与n相除的整数部分 第21页，本讲稿共23页9.4 密码学中的椭圆曲线 参量取值的选择，直接影响了加密的安全性。参量值一般要求满足以下几个条件：1、p 当然越大越安全，但越大，计算速度会变慢，200位左右可以满足一般安全要求；2、pnh；3、pt1(mod n)，1t20；4、4a3+27b20(mod p)；5、n 为素数；6、h4。第22页，本讲稿共23页9.5 超椭圆曲线密码 y2+h(x)y=f(x)如：y2=x5-5x3+4x=x(x+1)(x-1)(x+2)(x-2)不再构成群第23页，本讲稿共23页