收藏 分销(赏)

公钥密码算法RSA.ppt

上传人:仙人****88 文档编号:14753242 上传时间:2026-11-13 格式:PPT 页数:40 大小:814KB 下载积分:10 金币
下载 相关
公钥密码算法RSA.ppt_第1页
第1页 / 共40页
公钥密码算法RSA.ppt_第2页
第2页 / 共40页


点击查看更多>>
资源描述
-,*,-,第6讲,公钥密码算法,信息安全概论,课程幻灯片,主要内容,RSA,公钥密码算法,Diffie-Hellman,密钥交换协议,EIGamal,公钥加密算法,一,、,传统加脱密方式分析,加密的目的:,(1),不让窃听者读懂-信道上是密文!,(2),收方能够正常脱密-有脱密密钥即可!,发方,收方,密钥,破译者不知道,结论:(1),发方可以不具有脱密的能力!,(2),加密密钥可与脱密密钥不同,可以公开,一,、,传统加脱密方式分析(续),传统加密的缺点:,1.,密钥必须通过可靠信道在脱密前分发完毕!,2.,密钥的分配、存储与管理非常棘手!,3.,互不信任的收发双方的抵赖与否认无法判决,解决方案:,加密密钥公开,脱密密钥保密-非对称的,要求:,由公开的密钥,在实际上,求不出保密的密钥,发方,收方,密钥,绝对可靠的信道,二、公钥密码体制的基本思想,(,Diffie,-,Hellman,在1977年提出),密码算法有一对密钥:一个用于加密,称为,加密密钥,;另一个用于脱密,称为,脱密密钥,。,加密密钥是公开的,而脱密密钥是保密的,且加密密钥的公开不会危及脱密密钥的安全。,此时,加密消息不受限制(加密密钥公开),但只有能够脱密者只有一个!,二、公钥密码体制的基本思想,此时,如果一个用户使用秘密密钥,处理,信息,其它用户都可使用公开密钥,解读,处理过的信息。,数字签名,该方法可实现数字签名,。,识别签名,公开密钥,秘密密钥,难求出,用 作,加密密钥,用 作,脱密密钥,用 作,签名密钥,用 作,签名识别密钥,依赖于特殊的,数学难题,基于公钥密码的保密通信和数字签名,三、,RSA,密码算法,作 者:,R.Rivest,;A.,Shamir,;L.,Adlman,(,美国麻省理工学院),提出时间:,1977年研制,1978发表。,数学难题:,大合数分解是计算上不可行的。,大合数分解问题的困难性,已知,p,和,q,,,很容易计算出,p,q,?;,但是,如果已知,p,q,n,,,由,n,计算,p,?,和,q,?,却是十分困难的。这就是因式分解问题。,例如:,345677,135317,=,46775974609,计算 46773080681,=,?,困难!,解决该问题的一种最直接的方法就是利用每个可能的,p,试除,n,(,穷举,p,)。,但当,n,很大时,该方法的计算量太大。最多需试除,次,RSA,密码算法:,Step 1,用户,Bob,首先选取两个不同的大素数,p,q,并计算出,N,pq,和,(,N,)(,p,-1)(,q,-1)。,公开密钥:(,e,N,),秘密密钥:(,d,N,),明文空间和密文空间:,Z,/(,N,),0,1,N,-1,加密算法:,Step2,选加密密钥,e,:0,e,(,N,),使得,e,与,(,p,-1)(,q,-1),互,素。,Step3,求出满足,0,d,(,N,),和,ed,mod,(,N,),1,的,d,c,m,e,mod,N,Alice,Bob,秘密参数:,p,q,(,N,),d,最大的公因子是1,ed,被,(,N,),除后所得的余数,脱密算法:,m,c,d,mod,N,例:,设,RSA,体制中,p,=3,q,=11,取加密密钥,e,=7,因,e=7,与,(,N,)20,互素,故可解模方程,得到,d,3。,加密算法:,c,m,7,mod33,脱密算法:,m,c,3,mod33,(1),求脱密密钥,d;,(2),写出相应的加密算法和脱密算法,解:,此时,N,p,q,33,且,(,N,)(,p,-1)(,q,-1),即,7,d,mod 201,明、密文空间:,Z,/(33),加密密钥,:,(,e,n,)=(7,33),脱密密钥,:,(,d,n,)=(3,33),(3-1)(11-1)20,ed,mod(,N,)1,故,RSA,体制为:,加密实例:,设,RSA,算法为:,当明文,m,8,时,密文为:,明、密文空间:,Z,/(33),加密密钥,:,(,e,n,)=(7,33),脱密密钥,:,(,d,n,)=(3,33),加密算法:,c,m,7,mod33,脱密算法:,m,c,3,mod33,c,m,7,mod33,8,7,mod33,2,21,mod33,(,2,10,),2,2,mod33,(1024,),2,2,mod33,(1024,mod33),2,2mod33,(31,331),mod33,2,2mod33,2mod33 2,对密文,c,2,的脱密:,m,c,3,mod33,8mod33,8,2,3,mod33,有关,RSA,公钥密码的,几个问题,(1),RSA,的脱密算法为何正确?,N,pq,和,(,N,)(,p,-1)(,q,-1),公开密钥:(,e,N,),秘密密钥:(,d,N,),明文空间和密文空间:,Z,/(,N,),0,1,N,-1,加密算法:,0,e,d,(,N,),使得,e,与,(,p,-1)(,q,-1),互,素,且,ed,mod,(,N,),1,c,m,e,mod,N,脱密算法:,m,c,d,mod,N,c,d,mod,N,(,m,e,mod,N,),d,mod,N,m,ed,mod,N,m,?,问题:,现证:,当,0,x,N,时,有,x,ed,mod,N,x,Fermat,小定理,设,p,是素数,则任意非零整数,m,,,都有,x,p,-1,mod,p,1,首先:,由,ed,mod,(,N,),1,和,(,N,)(,p,-1)(,q,-1),存在整数,k,,,使得,ed,k,(,p,-1)(,q,-1),1,x,k,(,p,-1)(,q,-1),mod,p,1,对所有,整数,x,,,都有,x,k,(,p,-1)(,q,-1)1,mod,p,x mod p,即:,x,ed,mod,p,x mod p,对所有,x,都成立,同理可证:,x,ed,mod,q,x mod p,对,所有,x,都成立,现证:,m,ed,mod,N,m,已证:,对所有,x,,,都有,当0,x,N,时,有,孙子定理,p,与,q,互素,(2),RSA,的改进,-,e,和,d,可以更小,将,(,N,)(,p,-1)(,q,-1),由,p,-1,和,q,-1,最小公倍数,(,N,)lcm(,p,-1,q,-1),代替,就可得到改进后的,RSA,体制。,N,pq,和,(,N,)lcm(,p,-1,q,-1),公开密钥:(,e,N,),秘密密钥:(,d,N,),明文空间和密文空间:,Z,/(,N,),0,1,N,-1,加密算法:,0,e,d,(,N,),使得,e,与,(,N,),互素,且,ed,mod,(,N,),1,c,m,e,mod,N,脱密算法:,m,c,d,mod,N,改进的,RSA:,(,N,),整除,(,N,),(3),RSA,的,安全特征,已知,p,和,q、,已知,(,N,)(,p,-1)(,q,-1)、,或者已知,(,N,)lcm(,p,-1,q,-1),,都可由,公开密钥求出秘密密钥,还可分解,n,。,ed,mod,(,N,),1,原因:,此时,由于,e,和,(,N,)lcm(,p,-1,q,-1),已知,通过解方程,就可求出秘密参数,d。,已知证明,即使只知道,(,N,)lcm(,p,-1,q,-1),的,一个倍数,也可分解,n,,,从而破解,RSA。,(3),RSA,的,安全特征(续1),已知一对公、私钥(,e,n),和(,d,n),,就可,分解,n,原因:,此时,由,ed,mod,(,N,),1,可推知,ed,1,是,(,N,),的,一个倍数,因而可分解,n,。,意义:,只要掌握一个模数,n,对应的一对密钥,就可破解基于该模数,n,设计的所有,RSA,算法。,因此,不同的,RSA,用户,应配发不同的模数,n。,(3),RSA,的,安全特征(续2),公开指数,e,太小(如,e=3),,通播,信息不安全,向用户,A,1,发送密文:,m,e,mod,n,1,=,c,1,向用户,A,2,发送密文:,m,e,mod,n,2,=,c,2,向用户,A,t,发送密文:,m,e,mod,n,t,=,c,t,如果,e,很小,可由密文,c,1,c,2,c,t,求出消息,m,不妨,设,n,1,n,2,n,t,互素,则由孙子定理可求出,y,=,m,e,mod,n,1,n,2,n,t,如果,e,很小,就有,m,e,n,1,n,2,n,t,从而,m,e,mod,n,1,n,2,n,t,=m,e,在实数域中可求出,两个素数,p,和,q,不能选择的太接近。,p1,和,q1,应当有大的素因子。,一般取,p-1=2p,*,是素数,p,*,的2倍,,,这样的素数称为安全素数,。,脱密密钥不能选择的太小:,当脱密指数的位数小于模数,N,的位数的,4分之一时,,,就可利用连分数方法或,L,3,算法求出秘密指数,d.,(3),RSA,的,安全特征(续3),(3),RSA,的,安全特征(续4),不动点:,(,A),m,=0,c,m,e,mod,N,0,(B),m,=1,c,m,e,mod,N,1,(C),m,=,N,-1,c,m,e,mod,N,(N-1),e,mod,N,(-1),e,mod,N,(-1),mod,N,N,-1,(3),RSA,的,安全特征(续5),目前分解大合数的最好算法是数域筛法,其计算复杂性是,n,的二进制位数,log,2,n,的亚指数时间:,关键参数:1/3,穷举攻击的计算复杂性是,log,2,n,的指数时间:,关键参数:1,注意:,能分解,n,未必不能破解,RSA。(,没有证明),(4),RSA,的,安全界限,当,log,2,n,512,时可分解,n,(,已有,实验报道),当,log,2,n,512+256,时,已证明分解,n,的计算量可以实现。,密码学界普遍认为,要使,RSA,安全,,log,2,n,至少要大于1024,一般应取2048;更保守的选择是取,log,2,n,=4096。,N,pq,和,(,N,)lcm(,p,-1,q,-1),公开密钥:(,e,N,),秘密密钥:(,d,N,),加密算法:,0,e,d,(,N,),使得,e,与,(,N,),互素,且,ed,mod,(,N,),1,c,m,e,mod,N,脱密算法:,m,c,d,mod,N,改进的,RSA:,(5),RSA,的实现方法,从随机数中挑选素数,计算量是(,log,2,p),4,欧几里德算法,求,d,和检测,e,:,欧几里德算法,平方乘算法,计算量是1.5(,log,2,d),次模乘法,(6),RSA,的,应用情况,公钥密码主要用于密钥分配和数字签名,很少用于加密。主要是因为运行太慢。,前些年一直使用,RSA,,但最近几年,大多趋向选择椭圆曲线公钥密码。,主要原因是破解椭圆曲线公钥密码的最好算法的计算复杂性是,远比破解,RSA,的计算量大。,因此,在安全性相同时,椭圆曲线公钥密码的规模,N,可以取得更小,因而实现时所需的资源更少,运行速度可以更快。,Diffie,-,Hellman,密,钥交换协议,由,W.Diffie,和,M.Hellman,于1976年提出,是至今仍在广泛使用的一种公钥密码技术。,一、群,F,上的离散对数问题,定义1,设,G,是一个群,则在已知,G,中的元,a,和,b,,,求解整数,x,,,使得,a,x,b,在群,G,中成立的问题,称为群,G,上的,离散对数问题,。,如果,G,是实数域,则,x,log,a,b,,,故由,a,和,b,求,x,的问题是求对数问题。,在密码学中,由于群,G,是有限群,因而称之为离散对数问题。,二、离散对数问题的求解难度,(1),n,元域上的离散对数问题,最好的求解算法是数域筛法,其计算复杂性与分解同样位数的大合数,n,的时间相同。,(2)椭圆曲线群上的离散对数问题,由,a,x,b,在,a,和,b,已知时求,x,的,最好求解算法是,算法,其计算复杂性是,其中,ord,(,a,),是,a,的阶-使,a,t,1,的最小正整数,t,定义,设,GF(,q,),是有,q,个元素的有限域,则存在,a,GF(,q,),,使得,GF(,q,),0,a,a,2,a,3,a,4,a,q,-1,=1,我们称,a,是,有限域,GF(,q,),的一个本原元。,三、域,GF,(,q,),中本原元的概念,备注:,(1)一个有限域的本原元有很多;,(2)找出给定的有限域的一个本原元不困难。,四、,Diffie,-,Hellman,密钥交换协议,Step4,用户,U,算出,Step6,将,k,作为双方协商的密钥,并销毁,x,u,和,x,v,Step2,用户,U,随机选取整数,x,u,:1,x,u,q,-2,,并算出 后,将,明传给用户,V,并暂时保留,x,u,;,Step1,选取有限域,GF(,q,),,再选取有限域,GF(,q,),的一个本原元,a,并将,GF(,q,),和,a,公开,全网公用。,Step3,用户,V,随机选取整数,x,v,:,1,x,v,q,-2,,并算出 后,将,明传给用户,U,并暂时保留,x,v,;,Step5,用户,V,算出,(1),任何两个人都可协商出会话密钥,不需事先拥有对方的公开或秘密的信息;,(2),每次密钥交换后不必再保留秘密信息,减少了保密的负担。,前提条件:,必须进行身份认证,确保不是与假冒的用户进行密钥交换,否则不能抵抗中间人攻击.,中间人攻击:,攻击者,W,在信道中间:假冒,U,与,V,进行密钥交换;同时假冒,V,与,U,进行密钥交换.致使看似,U,与,V,交换的密钥,实际上都是与攻击者交换的密钥.,五、,Diffie,-Hellman,密钥交换协议的,优点,:,EIGamal,公钥密码体制,Step1,选取有限域,GF(,q,),,再选取有限域,GF(,q,),的一个本原元,a,并将,GF(,q,),和,a,公开;,Step2,随机选取整数,d,:1,d,q,-,2,并计算出,a,d,Step3,将,作为公开的加密密钥,,将,d,作为保密的脱密密钥。,EIGamal,公钥加密算法,与,D-H,密钥分配的过程一样,与,D-H,协议的差异:,(1),D-H,将,发给对方,这里将它公开(广播出去);,(2),d,都是秘密的。,EIGamal,公钥加密算法,加密算法:,对,m,GF(,q,)0,秘密选择一个随机整数,k,:1,k,q,-,2,则密文,c,(,c,1,c,2,),M,M,其中,脱密变换:,对任意密文,(,c,1,c,2,),M,M,,,明文为,脱密原理,:,脱密密钥:,d,:1,d,p,-,2,加密密钥:,a,d,明文空间:,M=,GF(,q,)0,密文空间:,M,M=(,x,y,):,x,y,M,EIGamal,公钥加密算法的,设计思想:,(1),利用,Diffie,-,Hellman,密钥交换协议,生成双方加密用的密钥,k,.,此时,与,D-H,协议的不同之处在于已将,a,d,作为公开密钥公布,不需每次发送给对方。,(2),采取了一次一密的加密思想:,将,k,作为双方交换的密钥,利用它进行加脱密,加密时临时,生成,备注:,(1),本原元,和,GF(,q,),可以全网公用,也可一人一套;,(2)本原元,可以用阶是大素数的,代替,(3),加密不同的明文分组时须选用独立的随机数,k,,,但秘密的脱密密钥,d,需和其版本号一起长期不变。,参数选取原则:,(1),q,-1,必须具有大的素因子;,(2),q,的位数应在1024比特以上。,a,的阶是使,a,t,1,的最小正整数,t,实际的应用选择:,(1),可选择,GF(,q,)=Z/(,p,),,且,p,是素数;,(2),可选择,GF(,q,)=GF(2,n,);,(3),当将有限域,GF(,q,),换作椭圆曲线群时,就构成椭圆曲线群上的公钥加密算法。,加、减、乘都是实数运算后的结果除以,p,不是所得的非负余数,当,p,是素数时,,Z/(,p,)=0,1,2,p-1,按照模,p,的加法和乘法构成有限域。,小 结,(1),RSA,公钥密码是基于大合数分解问题是困难问题的设计的,其参数有许多设计要求;,(2),Diffie-Hellman,密钥交换协议,是进行密钥交换的一个协议,其安全基础是离散对数问题是困难问题;,(3),EIGamal,公钥加密算法是利用,D,-H,密钥交换协议,设计的公钥算法,其安全性基础是离散对数问题是困难问题;,(4),有限域上求离散对数问题的难度与分解同等规模的大合数的难度相当,但椭,圆曲线群上的,离散对数问题要难的多,。,最后的强调:,基于,(1)大合数分解问题的难解性;,(2)离散对数问题的难解性;,并不是设计公钥密码算法的唯一方法。,还可基于其它的困难问题设计公钥密码,但这些密码都有这样或那样的安全或实现方面的问题,这里不再具体介绍。,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 包罗万象 > 大杂烩

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服