《应用密码学》课件第5章 非对称密码(3).ppt
《《应用密码学》课件第5章 非对称密码(3).ppt》由会员分享,可在线阅读,更多相关《《应用密码学》课件第5章 非对称密码(3).ppt(47页珍藏版)》请在文库网上搜索。
1、12024/3/192024/3/1912024/3/192024/3/1912024/3/192024/3/191 15.4.1 椭圆曲线密码体制简介5.4 椭圆曲线密码体制(略)椭圆曲线密码体制(略)在1985年,由Neal Koblitz和Victor Miller分别独立的提出了可以在低要求的计算环境里做到高强度加密的公钥算法,即椭圆曲线密码体制(ECC)。从1998年起,一些国际标准化组织开始了对椭圆曲线密码的标准化工作。椭圆曲线密码算法在与RSA算法相同安全性的情况下,其密钥短较短,160比特长的密钥相当于RSA算法密钥长1024比特的安全性,因而有利于容量受限的存储设备如智能卡等
2、在安全领域的使用。加拿大的Certicom公司是一家ECC密码技术公司,Certicom已经对上百家企业应用ECC密码技术进行授权,包括知名企业Cisco、摩托罗拉等。22024/3/192024/3/1922024/3/192024/3/192在我国,国家密码管理局2010年12月提出了SM2椭圆曲线公钥密码算法,同时,还要求升级并重新修改已有的RSA算法的电子认证系统和应用系统等。中国国家密码管理局发布了SM2椭圆曲线公钥密码算法标准。为满足电子认证服务系统等应用需求,该标准推荐了一条256位的随机椭圆曲线。NIST在标准FIPS 186-2中,推荐了美国政府使用的15个不同安全级别的椭圆
3、曲线。其包括5条二进制域上的随机椭圆曲线、5条二进制域上的Koblitz曲线和5条素域上的随机椭圆曲线。FIPS 186-3中,对于椭圆曲线的参数选择有进一步的介绍.32024/3/192024/3/1932024/3/192024/3/193ECCECC和和和和RSARSA安全性能比较安全性能比较安全性能比较安全性能比较42024/3/192024/3/1942024/3/192024/3/1942024/3/192024/3/194 45.4.2 椭圆曲线(选讲)椭圆曲线是指由Weierstrass方程:y y2 2+a+a1 1xy+axy+a3 3y=xy=x3 3+a+a2 2x x
4、2 2+a+a4 4x+ax+a6 6 所确定的曲所确定的曲所确定的曲所确定的曲线线线线。在公钥密码学中,主要用到两种椭圆曲线:(1)素域Fp(p3)上的椭圆曲线,可以表示为:y y2 2=x=x3 3+ax+b(modp)+ax+b(modp)其中a,b为整数,其判别式4a3+27b20 (2)域F(2n)(n1)上的椭圆曲线,可以表示为:y y2 2+xy=x+xy=x3 3+ax+ax2 2+b+b1.椭圆曲线的定义椭圆曲线的定义52024/3/192024/3/1952024/3/192024/3/1952024/3/192024/3/195 5图图5-1 y2x3+x+6所表示的曲线
5、所表示的曲线 本章的介绍以第一种椭圆曲线为主,本章的介绍以第一种椭圆曲线为主,如图5-1是y2x3+x+6所表示的曲线,该图可以用matlab实现。显然该曲线关于x轴对称。62024/3/192024/3/1962024/3/192024/3/1962024/3/192024/3/196 62椭圆曲线的加法椭圆曲线的加法 在在在在椭椭椭椭圆圆圆圆曲曲曲曲线线线线所所所所在在在在的的的的平平平平面面面面上上上上,定定定定义义义义一一一一个个个个称称称称为为为为无无无无穷穷穷穷远远远远点点点点的的的的元元元元素素素素,记记记记为为为为O O,把它定义为加法的单位元。把它定义为加法的单位元。把它定义
6、为加法的单位元。把它定义为加法的单位元。也即椭圆曲线上的点也即椭圆曲线上的点也即椭圆曲线上的点也即椭圆曲线上的点P P和它相加:和它相加:和它相加:和它相加:P+O=PP+O=P。椭圆曲线的加法定义如下:如如如如果果果果椭椭椭椭圆圆圆圆曲曲曲曲线线线线上上上上的的的的3 3个个个个点点点点位位位位于于于于同同同同一一一一直直直直线线线线上上上上,则者三个点的和为则者三个点的和为则者三个点的和为则者三个点的和为OO。设P1,P2为两个关于x轴对称的椭圆曲线上的点即P1=(x,y),P2=(x,-y),则它们互为加法逆元。由由由由上上上上面面面面的的的的加加加加法法法法定定定定义义义义,P P1
7、1P P2 2的的的的连连连连线线线线的的的的延延延延长长长长线线线线为为为为无无无无穷穷穷穷远远远远,故故故故P P1 1,P P2 2,OO三三三三点共线,由加法定义容易得:点共线,由加法定义容易得:点共线,由加法定义容易得:点共线,由加法定义容易得:P P1 1+P+P2 2+O=O+O=O,P P1 1=-P=-P2 2。72024/3/192024/3/1972024/3/192024/3/1972024/3/192024/3/197 7 设P和Q是椭圆曲线上x坐标不同的两个点,R=P+QR=P+Q定义为:画一条通定义为:画一条通定义为:画一条通定义为:画一条通过过过过P,QP,Q的
8、直线与椭圆曲线交于的直线与椭圆曲线交于的直线与椭圆曲线交于的直线与椭圆曲线交于P1P1,由加法的定义:P+Q+R1=OP+Q+R1=O。则P+Q=-R1=R,如图5-2。图图5-2 R=P+Q示意图示意图82024/3/192024/3/1982024/3/192024/3/1982024/3/192024/3/198 8 点点P的倍点定义为:的倍点定义为:过P点做椭圆曲线的切线,设与椭圆曲线交于R1,则P+P+R1=OP+P+R1=O,故2P=-R1=R2P=-R1=R。如图5-3。图图5-3 R=2P示意图示意图92024/3/192024/3/1992024/3/192024/3/199
9、2024/3/192024/3/199 9 对于上述加法,可以通过以下方式理解:对于上述加法,可以通过以下方式理解:对于上述加法,可以通过以下方式理解:对于上述加法,可以通过以下方式理解:设设设设椭椭椭椭圆圆圆圆曲曲曲曲线线线线的的的的方方方方程程程程为为为为y y2 2xx3 3+ax+b+ax+b,椭椭椭椭圆圆圆圆曲曲曲曲线线线线上上上上有有有有点点点点P(xP(x1 1,y y1 1),),Q(xQ(x2 2,y y2 2),见图见图见图见图5-25-2。则则则则过过过过QQ和和和和R R点点点点的的的的直直直直线线线线的的的的斜斜斜斜率率率率为为为为k=(yk=(y2 2-y-y1 1
10、)/(x)/(x2 2-x-x1 1),该该该该直直直直线线线线可可可可以以以以表表表表示示示示为为为为y=kx+cy=kx+c。通通通通过过过过把把把把直直直直线线线线方方方方程程程程代代代代人人人人椭椭椭椭圆圆圆圆曲曲曲曲线线线线方方方方程程程程,可可可可以以以以求求求求得得得得第第第第三三三三个个个个交交交交点点点点的的的的坐坐坐坐标标标标,取取取取第三个点关于第三个点关于第三个点关于第三个点关于x x轴的对称点即为所求。轴的对称点即为所求。轴的对称点即为所求。轴的对称点即为所求。图图5-2 R=P+Q示意图示意图102024/3/192024/3/19102024/3/192024/3
11、/19102024/3/192024/3/191010 对对对对于于于于倍倍倍倍点点点点运运运运算算算算,则则则则通通通通过过过过P(xP(x1 1,y y1 1)点点点点做做做做椭椭椭椭圆圆圆圆曲曲曲曲线线线线的的的的切切切切线线线线(见见见见图图图图5-35-3),则则则则该该该该切切切切线线线线的斜率可以如下求得的斜率可以如下求得的斜率可以如下求得的斜率可以如下求得:对对对对y y2 2xx3 3+ax+b+ax+b两两两两边边边边求求求求导导导导数得:数得:数得:数得:2yy=3x 2yy=3x2 2+a,k=y=(3x+a,k=y=(3x2 2+a)/2y +a)/2y 通通通通过过
12、过过P P点点点点的的的的椭椭椭椭圆圆圆圆曲曲曲曲线线线线的的的的切切切切线线线线就就就就可可可可以以以以表表表表示示示示为为为为y=kx+c,y=kx+c,通通通通过过过过把把把把直直直直线线线线方方方方程程程程代代代代入入入入椭椭椭椭圆圆圆圆曲曲曲曲线线线线方方方方程程程程,可可可可以以以以求求求求得得得得直直直直线线线线与与与与椭椭椭椭圆圆圆圆曲曲曲曲线线线线的的的的另另另另一一一一个个个个交交交交点点点点的的的的坐坐坐坐标标标标,取取取取该该该该点点点点关关关关于于于于x x轴轴轴轴的的的的对对对对称点即称点即称点即称点即为为为为所求所求所求所求。图图5-3 R=2P示意图示意图112
13、024/3/192024/3/19112024/3/192024/3/19112024/3/192024/3/191111 通通通通过过过过以以以以上上上上推推推推导导导导,可可可可以以以以得得得得出出出出椭椭椭椭圆圆圆圆曲曲曲曲线线线线y y2 2=x=x3 3+ax+b+ax+b上上上上的的的的点点点点的的的的加加加加法法法法运运运运算算算算规规规规则则则则,这个规则可以定义为:这个规则可以定义为:这个规则可以定义为:这个规则可以定义为:122024/3/192024/3/19122024/3/192024/3/19122024/3/192024/3/1912125.4.3 有限域上的椭圆
14、曲线 有限域有限域有限域有限域GF(p)GF(p)上的上的上的上的椭圆椭圆椭圆椭圆曲曲曲曲线线线线是由方程:是由方程:是由方程:是由方程:y y2 2xx3 3+ax+b(mod p)+ax+b(mod p)(a,ba,bGF(p),4aGF(p),4a3 3+27b+27b2 2(mod p)0(mod p)0)定定定定义义义义的曲的曲的曲的曲线线线线,简单简单简单简单表示表示表示表示为为为为E Ep p(a,b)(a,b)。132024/3/192024/3/19132024/3/192024/3/19132024/3/192024/3/191313 例例5-5:y2x3+x+6(mod
15、11)是是有有限限域域GF(11)上上的的椭椭圆圆曲曲线线,可可以以表表示示为为E11(1,6)。下面看看下面看看y2x3+x+6(mod 11)上的离散的点。上的离散的点。由平方剩余的定义,容易知道,由平方剩余的定义,容易知道,1,3,4,5,9是模是模11的平方剩余。的平方剩余。求求该该曲曲线线上上离离散散的的点点可可以以通通过过令令x=0,1,10,求求得得y26,8,5,3,8,4,8,4,9,7,4(mod 11).故故该该椭椭圆圆曲曲线线上上的的有有(2,4)(2,7)(3,5)(3,6)(5,2)(5,9)(7,2)(7,9)(8,3)(8,8)(10,2)(10,9)。1420
16、24/3/192024/3/19142024/3/192024/3/1914 -求解方法举例如下:求解方法举例如下:当当x=0,y26 mod11,6不是模不是模11的平方剩余,无解;的平方剩余,无解;当当x=1,y28 mod11,8不是模不是模11的平方剩余,无解;的平方剩余,无解;当当x=2,y28+2+65 mod11,5是模是模11的平方剩余,的平方剩余,y4 mod 11 其他的点可以按这个方式求出。其他的点可以按这个方式求出。由前面的分析可知,该椭圆曲线上一共有由前面的分析可知,该椭圆曲线上一共有12个点。个点。这这12个点的分布如图个点的分布如图5-4所示,图所示,图5-4中左
17、下标起点是中左下标起点是(0,0)点。点。对于对于同一条椭圆曲线,同一条椭圆曲线,y2x3+ax+b,p取不同的值,点的分布也不同。取不同的值,点的分布也不同。图图5-4 y2x3+x+6(mod 11)所表示的曲线所表示的曲线152024/3/192024/3/19152024/3/192024/3/19152024/3/192024/3/191515 通过比较通过比较通过比较通过比较y y2 2xx3 3+x+6+x+6在平面的曲线(见图在平面的曲线(见图在平面的曲线(见图在平面的曲线(见图5-15-1所示)和所示)和所示)和所示)和y y2 2xx3 3+x+6(mod 11)+x+6(
18、mod 11)在平面上的点(如图在平面上的点(如图在平面上的点(如图在平面上的点(如图5-45-4所示)所示)所示)所示),直观感觉没有太多的联系。,直观感觉没有太多的联系。,直观感觉没有太多的联系。,直观感觉没有太多的联系。图图5-1 y2x3+x+6所表示的曲线所表示的曲线图图5-4 y2x3+x+6(mod 11)所表示的曲线所表示的曲线162024/3/192024/3/19162024/3/192024/3/19162024/3/192024/3/191616 对于同一条椭圆曲线,在不同的有限域上(即对于同一条椭圆曲线,在不同的有限域上(即对于同一条椭圆曲线,在不同的有限域上(即对于
19、同一条椭圆曲线,在不同的有限域上(即p p取不同的值),点的个数是取不同的值),点的个数是取不同的值),点的个数是取不同的值),点的个数是有差别的,有差别的,有差别的,有差别的,当当当当p p很大时,虽然离散点的个数是确定的,离散点的分布情况看上去很大时,虽然离散点的个数是确定的,离散点的分布情况看上去很大时,虽然离散点的个数是确定的,离散点的分布情况看上去很大时,虽然离散点的个数是确定的,离散点的分布情况看上去也没有什么规律。也没有什么规律。也没有什么规律。也没有什么规律。172024/3/192024/3/19172024/3/192024/3/19172024/3/192024/3/19
20、1717 以以以以y y2 2xx3 3+x+6(mod 11)+x+6(mod 11)为例子,选取为例子,选取为例子,选取为例子,选取P=(2,7)P=(2,7),计算,计算,计算,计算2P2P。首先计算:首先计算:首先计算:首先计算:k=(32k=(322 2+1)(27)+1)(27)-1-1 mod 118 mod 118 于是于是于是于是,x x3 3=8=82 2-2-2 mod 115,y-2-2 mod 115,y3 3=8(2-5)-7 mod 112=8(2-5)-7 mod 112 因此因此因此因此,2P=(5,2)2P=(5,2)。再计算:再计算:再计算:再计算:3P=
21、2P+P=(5,2)+(2,7)3P=2P+P=(5,2)+(2,7),先计算先计算先计算先计算k=(7-2)(2-5)k=(7-2)(2-5)-1-1 mod 112 mod 112。于是于是于是于是,x x3 3=2=22 2-5-2 mod 118,y-5-2 mod 118,y3 3=2(5-8)-2 mod 113=2(5-8)-2 mod 113 因此,因此,因此,因此,3P=(8,3)3P=(8,3)。计算完毕后,可以通过把计算完毕后,可以通过把计算完毕后,可以通过把计算完毕后,可以通过把2P=(5,2),3P=(8,3)2P=(5,2),3P=(8,3)代入到代入到代入到代入到
22、y y2 2xx3 3+x+6(mod 11)+x+6(mod 11)中验中验中验中验证等式成立否,证等式成立否,证等式成立否,证等式成立否,如果不成立,则要检查计算过程的错误。如果不成立,则要检查计算过程的错误。如果不成立,则要检查计算过程的错误。如果不成立,则要检查计算过程的错误。182024/3/192024/3/19182024/3/192024/3/1918椭圆曲线密码体制椭圆曲线密码体制-原理原理 -椭圆曲线离散对数问题椭圆曲线离散对数问题 已知椭圆曲线已知椭圆曲线E和点和点P,随机生成一个整数,随机生成一个整数d,容易计算,容易计算:Q=d*P,但给定但给定Q和和P,计算计算d就
23、相对困难。就相对困难。(1 1)ECCECC密密密密码码码码体制的建立体制的建立体制的建立体制的建立 选取选取:一个基域一个基域GF(p);定义在该基域上的椭圆曲线定义在该基域上的椭圆曲线Ep(a,b);E上的一个拥有素数阶上的一个拥有素数阶n的点的点P。其中有限域其中有限域GF(p),椭圆曲线参数,椭圆曲线参数a,b,点,点P和阶和阶n都是公开信息。都是公开信息。192024/3/192024/3/19192024/3/192024/3/1919(2 2)密)密)密)密钥钥钥钥的生成的生成的生成的生成n在区间在区间1,n-1中随机选取一个整数中随机选取一个整数dn计算计算:Q=d*Pn实体的
24、实体的 -公开密钥公开密钥:点点Q -实体的私钥实体的私钥:整数整数d n待发送消息(待发送消息(AB):):M-查找查找B的公开密钥:的公开密钥:Q-将消息将消息M表示成一个域元素表示成一个域元素:m-在区间在区间1,n-1中随机选取一个整数中随机选取一个整数k(3 3)加密)加密)加密)加密过过过过程程程程202024/3/192024/3/19202024/3/192024/3/1920-计算点计算点:(x1,y1)=kP-计算点计算点:(x2,y2)=kQ,如果,如果x2=0,则返回第,则返回第步步-计算计算:c=mx2-传送加密数据传送加密数据(x1,y1,c)给给B n 当实体当实
25、体B解密从解密从A收到的密文收到的密文(x1,y1,c)时,执行步骤:时,执行步骤:-使用私钥使用私钥d,计算点,计算点:(x2,y2)=d(x1,y1)-计算计算 ,恢复出消息,恢复出消息m(4 4)解密)解密)解密)解密过过过过程程程程212024/3/192024/3/19212024/3/192024/3/1921212024/3/192024/3/19212024/3/192024/3/19212024/3/192024/3/1921215.4.4 椭圆曲线上的ElGamal密码体制(选讲)(1)先先由由系系统统选选取取一一条条椭椭圆圆曲曲线线,该该椭椭圆圆曲曲线线上上的的点点形形成
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 应用密码学 应用密码学课件第5章 非对称密码3 应用 密码学 课件 对称 密码