椭圆曲线加密精.ppt

《椭圆曲线加密精.ppt》由会员分享，可在线阅读，更多相关《椭圆曲线加密精.ppt（20页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、椭圆曲线加密椭圆曲线加密第1页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系网络安全椭圆曲线加密2主要内容主要内容椭圆曲线加密概念椭圆曲线加密概念射影平面射影平面椭圆曲线椭圆曲线椭圆曲线加法群椭圆曲线加法群有限域椭圆曲线有限域椭圆曲线椭圆曲线加密方法椭圆曲线加密方法第2页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系网络安全椭圆曲线加密3ECC概念概念ECC椭圆曲线加密椭圆曲线加密 Ellipse Curve Cryptography基于椭圆曲线理论的公钥加密技术（基于椭圆曲线理论的公钥加密技术（1985）与传统的基于大质数因子分解困难性的加密方法不同，与传统的

2、基于大质数因子分解困难性的加密方法不同，ECC通过通过椭圆曲线方程式的性质产生密钥椭圆曲线方程式的性质产生密钥ECC 164位的密钥产生一个安全级，相当于位的密钥产生一个安全级，相当于RSA 1024位密位密钥提供的保密强度，而且计算量较小，处理速度更快，存储钥提供的保密强度，而且计算量较小，处理速度更快，存储空间和传输带宽占用较少空间和传输带宽占用较少第3页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系网络安全椭圆曲线加密4无穷远点无穷远点定义平行线相交于无穷远点定义平行线相交于无穷远点P，使平面上所，使平面上所有直线都统一为有唯一的交点有直线都统一为有唯一的交点性质：性质：

3、一条直线只有一个无穷远点；一对平行线有公共的无穷远点一条直线只有一个无穷远点；一对平行线有公共的无穷远点任何两条不平行的直线有不同的无穷远点（否则会造成有两个交点）任何两条不平行的直线有不同的无穷远点（否则会造成有两个交点）平面上全体无穷远点构成一条无穷远直线平面上全体无穷远点构成一条无穷远直线P第4页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系网络安全椭圆曲线加密5射影平面射影平面平面上全体无穷远点与全体平常点构成射影平面平面上全体无穷远点与全体平常点构成射影平面对普通平面上点对普通平面上点(x,y)，令，令x=X/Z，y=Y/Z，Z0，则投影为射影平面上的点则投影为射影平

4、面上的点(X:Y:Z)例如：点例如：点(1,3)可投影为可投影为(Z:3Z:Z)，可为，可为(1:3:1),(2.3:6.9:2.3)等等对普通平面上的直线对普通平面上的直线ax+by+c=0，同样变换，得到对应于射影平面上的直线为，同样变换，得到对应于射影平面上的直线为aX+bY+cZ=0对平行线对平行线aX+bY+c1Z=0和和aX+bY+c1Z=0，易解得，易解得Z=0，说明无穷远点，说明无穷远点 的的座标为座标为(X:Y:0)第5页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系网络安全椭圆曲线加密6椭圆曲线椭圆曲线一条椭圆曲线是在射影平面上满足威尔斯一条椭圆曲线是在射影

5、平面上满足威尔斯特拉斯方程（特拉斯方程（Weierstrass）所有点的集合：）所有点的集合：椭圆曲线方程是一个齐次方程椭圆曲线方程是一个齐次方程曲线上的每个点都必须是非奇异的（光滑的），偏导数曲线上的每个点都必须是非奇异的（光滑的），偏导数FX(X,Y,Z)、FY(X,Y,Z)、FZ(X,Y,Z)不同为不同为0第6页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系网络安全椭圆曲线加密7椭圆曲线示例椭圆曲线示例第7页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系网络安全椭圆曲线加密8非椭圆曲线示例非椭圆曲线示例第8页，本讲稿共20页复旦大学 信息科学与工程学院 通

6、信科学与工程系网络安全椭圆曲线加密9椭圆曲线普通方程椭圆曲线普通方程椭圆曲线普通方程：椭圆曲线普通方程：无穷远点无穷远点O(0,Y,0)平常点平常点(x,y)斜率斜率k：第9页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系网络安全椭圆曲线加密10椭圆曲线加法群椭圆曲线加法群阿贝尔（阿贝尔（Abel）加法群）加法群任意取椭圆曲线上两点任意取椭圆曲线上两点P、Q（若（若P、Q两点重合，则作两点重合，则作P点的切线），点的切线），作直线交于椭圆曲线的另一点作直线交于椭圆曲线的另一点R，过，过R做做y轴的平行线交于轴的平行线交于R，定义，定义P+Q=R。这样，加法的和也在椭圆曲线上，并

7、同样具备加法的交换律、。这样，加法的和也在椭圆曲线上，并同样具备加法的交换律、结合律结合律第10页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系网络安全椭圆曲线加密11零元与负元零元与负元O与与-P如果椭圆曲线上的三个点A、B、C处于同一直线上，那么其和等于零元，即A+B+C=O第11页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系网络安全椭圆曲线加密12同点加法同点加法若有若有k个相同的点个相同的点P相加，记作相加，记作kP第12页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系网络安全椭圆曲线加密13有限域椭圆曲线有限域椭圆曲线有限域有限域Fp

8、Fp中有中有p（p为质数）个元素为质数）个元素0,1,2,p-2,p-1Fp的加法是的加法是a+bc(mod p)Fp的乘法是的乘法是abc(mod p)Fp的除法是的除法是abc(mod p)Fp的单位元是的单位元是1，零元是，零元是 0Fp域内运算满足交换律、结合律、分配律域内运算满足交换律、结合律、分配律第13页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系网络安全椭圆曲线加密14有限域椭圆曲线示例有限域椭圆曲线示例椭圆曲线椭圆曲线Ep(a,b)，p为质数，为质数，x,y0,p-1选择两个满足下列约束条件的小于选择两个满足下列约束条件的小于p的非负整数的非负整数a、b当当

9、p=23，a=b=1时，椭圆曲线时，椭圆曲线:第14页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系网络安全椭圆曲线加密15第15页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系网络安全椭圆曲线加密16椭圆曲线点的阶椭圆曲线点的阶如果椭圆曲线上一点如果椭圆曲线上一点P，存在最小的正整数，存在最小的正整数n，使得数乘，使得数乘nP=O（显然（显然(n-1)P=-P），），则将则将n称为称为P的阶的阶若若n不存在，则不存在，则P是是无限阶无限阶的的在有限域上定义的椭圆曲线上所有的点的阶n都是存在的第16页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系

10、网络安全椭圆曲线加密17椭圆曲线加密椭圆曲线加密考虑考虑K=kG，其中，其中K、G为椭圆曲线为椭圆曲线Ep(a,b)上的点，上的点，n为为G的阶（的阶（nG=O），），k为小于为小于n的整数的整数则给定则给定k和和G，根据加法法则，计算，根据加法法则，计算K很容易很容易但反过来，给定但反过来，给定K和和G，求，求k就非常困难就非常困难这就是椭圆曲线加密算法的数学依据这就是椭圆曲线加密算法的数学依据点点G称为称为基点基点（base point）k（kn）为）为私有密钥私有密钥（privte key）K为为公开密钥公开密钥（public key)第17页，本讲稿共20页复旦大学 信息科学与工程学院

11、 通信科学与工程系网络安全椭圆曲线加密18ECC保密通信算法保密通信算法公钥加密私钥解密公钥加密私钥解密Alice选定一条椭圆曲线选定一条椭圆曲线E，并取椭圆曲线上一点作为基点，并取椭圆曲线上一点作为基点GAlice选择一个私有密钥选择一个私有密钥k（kn），并生成公开密钥），并生成公开密钥K=kGAlice将将E和点和点K、G传给传给BobBob收到信息后，将待传输的明文编码到上的一点收到信息后，将待传输的明文编码到上的一点M（编码方法略），（编码方法略），并产生一个并产生一个随机整数随机整数r（rn）Bob计算点计算点C1=M+rK和和C2=rGBob将将C1、C2传给传给AliceAli

12、ce收到信息后，计算收到信息后，计算C1-kC2，结果就应该是点，结果就应该是点M，因为：，因为：第18页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系网络安全椭圆曲线加密19ECC密钥互换算法密钥互换算法类似类似Diffie-Hellman密钥互换方法密钥互换方法双方公开选定有限域双方公开选定有限域GF(2k)上的椭圆曲线上的椭圆曲线E、基点、基点PE(GF(2k)，n为为P的阶，的阶，k为二进制位数为二进制位数Alice随机选取随机选取x，0 xnAlice发送发送kA=xPBob随机选取随机选取y，0ynBob发送发送kB=yPAlice计算：计算：kAB=yKA=xyP

13、Bob计算：计算：kAB=xKB=xyP第19页，本讲稿共20页复旦大学 信息科学与工程学院 通信科学与工程系网络安全椭圆曲线加密20ECC技术要求技术要求通常将通常将Fp上的一条椭圆曲线描述为上的一条椭圆曲线描述为T=(p,a,b,G,n,h)p、a、b确定一条椭圆曲线（确定一条椭圆曲线（p为质数，为质数，(mod p)运算）运算）G为基点，为基点，n为点为点G的阶的阶h是椭圆曲线上所有点的个数是椭圆曲线上所有点的个数m与与n相除的商的整数部分相除的商的整数部分参量选择要求：参量选择要求：p越大安全性越好，但会导致计算速度变慢，越大安全性越好，但会导致计算速度变慢，200-bit左右可左右可满足一般安全要求满足一般安全要求n应为质数应为质数h4；pnh；pt1(mod n)(1t20)4a327b20(mod p)第20页，本讲稿共20页