网络安全：公钥密码学RSAPPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,河北科技大学信息学院,*,Chapter 9,公钥密码学,RSA,密码编码学与网络安全,1,河北科技大学信息学院,2025/4/9 周三,2,2,为什么需要公钥密码,?,1,）,对称密码体制的密钥分配问题,：,通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现；,2,）,对称密码体制的密钥管理问题,：,在有多个用户的网络中，任何两个用户之间都需要有共享的秘密钥，当网络中的用户,n,很大时，需要管理的密钥数目是非常大 。,3,）,对称密码体制没有签名功能,：当主体,A,收到主体,B,的电子文挡（电子数据）时，无法向第三方证明此电子文档确实来源于,B,。,河北科技大学信息学院,2,3,公钥密码体制,密码学发展历史中最伟大的一次革命,公认该发明属于,Stanford Uni,的,Whitfield Diffie,和,Martin Hellman,，于,1976,年。,New Directions in Cryptography,IEEE Trans.Information Theory,IT-22,pp644-654,Nov 1976,James Ellis(UK CESG),在,1970,年曾提出此概念,基于数论中的结论,河北科技大学信息学院,公钥密码体制,公钥,/,双钥,/,非对称 密码都是指使用两个密钥,:,公钥：可以对任何人公开的密钥，用于加密消息或验证签名。,私钥：只能由接收者私存，用于解密消息或签名。,非对称,用于加密消息或验证签名的密钥不能进行,解,密消息的或消息的签名。,4,河北科技大学信息学院,2025/4/9 周三,2,5,河北科技大学信息学院,2025/4/9 周三,6,公钥密码体制的应用,分为三类,:,加密,/,解密,(,提供保密性,),数字签名,(,提供认证,),密钥交换,(,会话密钥,),一些算法可用于上述三类，而有些只适用用于其中一类或两类。,6,河北科技大学信息学院,2025/4/9 周三,2025/4/9 周三,7,DSS,：美国数字签名标准,7,河北科技大学信息学院,2025/4/9 周三,2025/4/9 周三,8,公钥密码体制的应用,是私钥密码的补充而不是代替,三种误解：,比传统密码更安全；,传统密码已过时；,公钥密码分配非常简单。,8,河北科技大学信息学院,2025/4/9 周三,2,9,公钥密码体制的应用：保密性,河北科技大学信息学院,2025/4/9 周三,10,公钥密码体制的应用：认证,10,河北科技大学信息学院,2025/4/9 周三,2,11,公钥密码体制的应用：保密性和认证,河北科技大学信息学院,2,12,公钥密码,的要求,公私钥对产生在计算上容易；,加密在计算上容易；,解密在计算上容易；,已知公钥，求私钥在计算上不可行；,已知公钥和密文，恢复明文计算上不可性。,加密和解密函数的顺序可以交换（附加条件）,河北科技大学信息学院,2,13,单向陷门函数,单向陷门函数：,若,k,和,X,已知，则容易计算,Y=f,k,(X).,若,k,和,Y,已知，则容易计算,X=f,k,-1,(Y).,若,Y,已知但,k,未知，则计算出,X=f,k,-1,(Y),是不可行的,.,寻找合适的单向陷门函数是公钥密码体制应用的关键,单向陷门函数举例：,离散对数,大整数分解,河北科技大学信息学院,2,14,公钥密码体制安全性分析,一样存在穷举攻击,从安全性考虑，使用的密钥一般都非常大,(512bits),为了便于实现加解密，密钥又必须足够短。,公钥密码目前仅限与密钥管理和签名中。,另外一种攻击方法：从给定的公钥计算出私钥的方法。,到目前为止，还未在数学上证明对一特定公钥算法这种攻击是不可行的。,（包括,RSA,）,公钥体制特有的攻击,穷举消息攻击,河北科技大学信息学院,2,15,9.2,RSA,1977,由,MIT,的,Rivest,Shamir,和,Adleman,发明,已知的且被广泛使用的公钥密码方案,有限域中的乘方运算,乘方运算需要,O(log n),3,),操作,(,容易的,),使用一些大的整数,(,例如,.1024 bits),安全性基于大数的素因子分解的困难性,素因子分解需要,O(e,log n log log n,),操作,(,困难的,),河北科技大学信息学院,2,16,河北科技大学信息学院,2,17,河北科技大学信息学院,2,18,RSA,密钥的建立,每一个用户通过以下方法产生一个公钥,/,私钥对,:,随机地选择两个大的素数,p,q,计算方案中的模数,n=p.q,(n)=(p-1)(q-1),随机地选择一个加密密钥,e,满足,1 e (n),gcd(e,(n)=1,求解下面的方程，以得到解密密钥,d,e.d 1 mod(n)and 0,d n,公开公钥,:PU=e,n,保密私钥,:PR=d,n,河北科技大学信息学院,2,19,RSA,的使用,为了加密消息,M,，发送方,:,获得接收方的公钥,PU=e,n,计算,:C=M,e,mod n,其中,0,M n,为了解密密文,C,，接收者,:,使用自己的私钥,PR=d,n,计算,:M=C,d,mod n,消息,M,一定要比模数,n,小,(,如果需要的话，可以进行分组,),河北科技大学信息学院,2,20,RSA,的工作原理,Euler,定理,:,a,(n),mod n 1,其中,(a,n)=1,RSA,中,:,n=p.q,(n)=(p-1)(q-1),仔细地选择,e,和,d,使得,mod(n),下，两者互逆,因此存在某个整数,k,，使得,e.d=1+k.(n),成立,所以,:C,d,=M,e.d,=M,1+k.(n),=M,1,.(M,(n),),k,M,1,.(1),k,=M,1,=M mod n,河北科技大学信息学院,2,21,RSA,举例,密钥的建立,选择素数,:,p,=17&,q,=11,计算,n,=,p q,=17,x,11=,187,计算,(,n,)=(,p,1)(,q-,1)=16,x,10=160,选择,e:,gcd(e,160)=1;,选择,e,=7,确定,d:,d e=,1 mod 160,且,d,160 d=23,因为,23,x,7=161=10,x,160+1,公钥,PU=7,187,私钥,PR=23,187,河北科技大学信息学院,2,22,RSA,举例,加密,/,加密,明文消息,M=88(,注意,88=1;,return ret;,河北科技大学信息学院,2,25,河北科技大学信息学院,2,26,加密的效率,加密要计算,e,次方幂,若,e,较小,计算将很快,通常选择,e=65537(2,16,+1),或选择,e=3,或,e=17,但若,e,太小,(,如,e=3),将易受到攻击,用中国剩余定理,解决方法：,M,随机填充一个唯一的伪随机比特串,必须确保,gcd,(e,(n)=1,河北科技大学信息学院,2,27,解密的效率,解密计算,d,次方幂,d,的值太小容易遭受穷举攻击和其他形式的攻击。,用中国剩余定理分别计算,mod p,和,mod q,，则可以得到所希望的答案,比直接快约,4,倍,只有知道,p,和,q,及私钥的接收者可以直接采用这个技术进行计算,河北科技大学信息学院,2,28,RSA,密钥的产生,RSA,的用户必须,:,随机确定两个素数,p,q,选择,e,或,d,，并求出另一个,素数,p,q,一定不能从,n=p.q,轻易得到,意味着数要足够大,典型地用猜测或可能性测试（,Miller-Rabin,）,指数,e,d,是互逆的（欧几里得扩展算法）,河北科技大学信息学院,2,29,RSA,安全性分析,攻击,RSA,可能的方法有,:,穷举搜索,(,对于给定的数字规模是不可行的,),数学攻击,(,基于计算,(n),的困难性,模,n,的因子分解的困难性,),计时攻击,(,基于解密的运行情况,),选择密文攻击,(RSA,的已知特性,),河北科技大学信息学院,2,30,分解因子问题,数学攻击的三种形式,:,分解,n=p.q,计算,(n),从而得到,d,直接确定,(n),并计算,d,（等价于因子分解,n,）,直接寻找,d,（至少和因子分解问题一样费时）,对于因子分解问题,很多年来进展很慢,用,“Lattice Sieve”(LS),算法，,最好的是分解了,200,位十进制数,(663 bit),最大的改进就是对改进算法的改良,QS to GHFS to LS,当前假设,1024-2048bit RSA,是安全的,确保,p,q,有相似的大小并满足其它约束,河北科技大学信息学院,2,31,MIPS,：一台每秒执行百万条指令的处理器运行,1,年,1GHz,的奔腾机约等于一台,250MIPs,河北科技大学信息学院,2,32,RSA,系统安全性与系统的参数,RSA,系统安全性与系统的参数有很大关系，,X.931,标准,ISO/IEC 14752,对此提出以下几点：,p,和,q,的长度应仅差几位。,（,p-1,）和（,q-1,）都应有大的素因子；,gcd(p-1,q-1),应该小；,河北科技大学信息学院,2,33,计 时 攻 击,20,世纪,90,年代由,Paul Kocher,提出,类似于窃贼通过观察他人转动保险柜拨号盘的时间长短来猜测密码。,探测操作中的时间变化,eg.multiplying by small vs large number,基于所耗时间的大小，对操作数的大小进行猜测,Countermeasures(,解决办法,),use constant exponentiation time,（不变的 幂运算时间）,add random delays,（随机时延）,blind values used in calculations,（隐蔽）,河北科技大学信息学院,2,34,选择密文攻击,RSA,对于选择密文（,CCA,）来说是易受攻击的,攻击者选择密文并得到相应明文,选择密文可给密码分析者探测,RSA,的特性提供信息,C=M,e,mod n,X=C*2,e,mod n,对策：,采用最优非对称加密填充,(OAEP).,的程序对明文进行修改。,河北科技大学信息学院,2,35,小 结,公钥密码的原理,两个密钥：公钥,/,私钥,单向陷门函数,RSA,算法，实现和安全分析,河北科技大学信息学院,