网络安全-09：公钥密码学与RSA

Chapter9公钥密码学与RSA《密码编码学与网络安全》2020/2/24西安电子科技大学计算机学院2§9.1公钥密码体制的基本原理传统密码体制只使用一个密钥收发双方共享这个单一的密钥密钥是对称的，双方是对等的；因此，不能确保接收方伪造信息，并声称是该信息是发送方发送的2020/2/24西安电子科技大学计算机学院31）密钥分配问题通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现；2）密钥管理问题在有多个用户的网络中，任何两个用户之间都需要有共享的秘密钥，当网络中的用户n很大时，需要管理的密钥数目是非常大2/)1(nn。3）没有签名功能：当主体A收到主体B的电子文挡（电子数据）时，无法向第三方证明此电子文档确实来源于B。对称密码体制的缺陷2020/2/24西安电子科技大学计算机学院4公钥密码体制密码学发展历史中最伟大的一次革命采用两个密钥：一个公钥，一个私钥参与方不对等，所以是非对称的；基于数论中的结论是私钥密码的补充而不是代替2020/2/24西安电子科技大学计算机学院5为什么需要公钥密码?两个考虑：密钥分配-KDC数字签名公认该发明属于StanfordUni的WhitfieldDiffie和MartinHellman，于1976年。NewDirectionsinCryptography,IEEETrans.InformationTheory,IT-22,pp644-654,Nov1976JamesEllis(UKCESG)在1970年曾提出此概念2020/2/24西安电子科技大学计算机学院6公钥密码体制公钥/双钥/非对称密码都是指使用两个密钥:公钥：可以对任何人公开的密钥，用于加密消息或验证签名。私钥：只能由接收者私存，用于解密消息或签名。非对称用于加密消息或验证签名的人不能进行消息的加密或消息的签名。2020/2/24西安电子科技大学计算机学院7公钥密码体制2020/2/24西安电子科技大学计算机学院82020/2/24西安电子科技大学计算机学院9公钥密码体制特点公钥密码算法依赖于:仅仅知道算法和加密密钥，推导解密密钥计算上是不可行的已知加解密密钥时，进行加解密运算计算上是容易的两个密钥中的任何一个都可以用来加密，而另一个用来解密。书上6个条件p1962020/2/24西安电子科技大学计算机学院10单向陷门函数单向陷门函数：若k和X已知，则容易计算Y=fk(X).若k和Y已知，则容易计算X=fk-1(Y).若Y已知但k未知，则计算出X=fk-1(Y)是不可行的.寻找合适的单向陷门函数是公钥密码体制应用的关键单向陷门函数举例：离散对数大整数分解背包问题2020/2/24西安电子科技大学计算机学院11公钥密码体制：保密性和认证2020/2/24西安电子科技大学计算机学院12公钥算法分类Public-KeyDistributionSchemes(PKDS)用于交换秘密信息(依赖于双方主体)常用于对称加密算法的密钥PublicKeyEncryption(PKE)用于加密任何消息任何人可以用公钥加密消息私钥的拥有者可以解密消息任何公钥加密方案能够用于密钥分配方案PKDS许多公钥加密方案也是数字签名方案SignatureSchemes用于生成对某消息的数字签名私钥的拥有者生成数字签名任何人可以用公钥验证签名2020/2/24西安电子科技大学计算机学院13公钥密码体制的应用分为三类:加密/解密(提供保密性)数字签名(提供认证)密钥交换(会话密钥)一些算法可用于上述三类，而有些只适用用于其中一类或两类。2020/2/24西安电子科技大学计算机学院142020/2/24西安电子科技大学计算机学院15公钥密码体制安全性分析一样存在穷举攻击但所使用的密钥一般都非常大(512bits)安全性基于容易（加解密）和困难（破译）之间巨大的差别许多算法没有得到证明是安全的。（包括RSA）需要采用一些特别大的数字与私钥密码体制相比，速度慢。2020/2/24西安电子科技大学计算机学院16§9.2RSA1977由MIT的Rivest,Shamir和Adleman发明已知的且被广泛使用的公钥密码方案有限域中的乘方运算乘方运算需要O((logn)3)操作(容易的)使用一些大的整数(例如.1024bits)安全性基于大数的素因子分解的困难性素因子分解需要O(elognloglogn)操作(困难的)2020/2/24西安电子科技大学计算机学院172020/2/24西安电子科技大学计算机学院182020/2/24西安电子科技大学计算机学院19RSA密钥的建立每一个用户通过以下方法产生一个公钥/私钥对:随机地选择两个大的素数p,q计算方案中的模数n=p.qø(n)=(p-1)(q-1)随机地选择一个加密密钥e满足1eø(n),(e,ø(n))=1求解下面的方程，以得到解密密钥de.d≡1modø(n)and0≤d≤n公开公钥:PU={e,n}保密私钥:PR={d,n}2020/2/24西安电子科技大学计算机学院20RSA的使用为了加密消息M，发送方:获得接收方的公钥PU={e,n}计算:C=Memodn,其中0≤Mn为了解密密文C，接收者:使用自己的私钥PR={d,n}计算:M=Cdmodn消息M一定要比模数n小(如果需要的话，可以进行分组)2020/2/24西安电子科技大学计算机学院21RSA的工作原理Euler定理:aø(n)modn≡1其中(a,n)=1RSA中:n=p.qø(n)=(p-1)(q-1)仔细地选择e和d使得modø(n)下，两者互逆因此存在某个整数k，使得e.d=1+k.ø(n)成立所以:Cd=Me.d=M1+k.ø(n)=M1.(Mø(n))k≡M1.(1)k=M1=Mmodn2020/2/24西安电子科技大学计算机学院22RSA举例–密钥的建立1.选择素数:p=17&q=112.计算n=pq=17x11=1873.计算ø(n)=(p–1)(q-1)=16x10=1604.选择e:gcd(e,160)=1;选择e=75.确定d:de=1mod160且d160d=23因为23x7=161=10x160+16.公钥PU={7,187}7.私钥PR={23,187}2020/2/24西安电子科技大学计算机学院23RSA举例–加密/加密明文消息M=88(注意88187)加密:C=887mod187≡11解密:M=1123mod187≡882020/2/24西安电子科技大学计算机学院24幂运算可以用平方和乘法运算N次方，只需要O(log2n)次乘法运算如.75=74.71=3.7=10mod11如.3129=3128.31=5.3=4mod112020/2/24西安电子科技大学计算机学院25幂运算c=0;f=1fori=kdownto0doc=2xcf=(fxf)modnifbi==1thenc=c+1f=(fxa)modnreturnf2020/2/24西安电子科技大学计算机学院262020/2/24西安电子科技大学计算机学院27加密的效率加密要计算e次方幂若e较小,计算将很快通常选择e=65537(216-1)或选择e=3或e=17但若e太小(如e=3)将易受到攻击用中国剩余定理必须确保(e,ø(n))=12020/2/24西安电子科技大学计算机学院28解密的效率解密计算d次方幂看起来很大，否则不安全用中国剩余定理分别计算modp和modq，则可以得到所希望的答案比直接快约4倍只有知道p和q及私钥的接收者可以直接采用这个技术进行计算2020/2/24西安电子科技大学计算机学院29RSA密钥的产生RSA的用户必须:随机确定两个素数p,q选择e或d，并求出另一个素数p,q一定不能从n=p.q轻易得到意味着数要足够大典型地用猜测或可能性测试指数e,d是互逆的2020/2/24西安电子科技大学计算机学院30RSA安全性分析攻击RSA可能的方法有:穷举搜索(对于给定的数字规模是不可行的)数学攻击(基于计算ø(n)的困难性,模n的因子分解的困难性)计时攻击(基于解密的运行情况)选择密文攻击(RSA的已知特性)2020/2/24西安电子科技大学计算机学院32分解因子问题数学攻击的三种形式:分解n=p.q,计算ø(n)从而得到d直接确定ø(n)并计算d直接寻找d对于因子分解问题很多年来进展很慢用“LatticeSieve”(LS),算法，最好的是分解了200位十进制数(663bit)最大的改进就是对改进算法的改良QStoGHFStoLS当前假设1024-2048bitRSA是安全的确保p,q有相似的大小并满足其它约束2020/2/24西安电子科技大学计算机学院332020/2/24西安电子科技大学计算机学院34计时攻击20世纪90年代由PaulKocher提出探测操作中的时间变化eg.multiplyingbysmallvslargenumberorIF'svaryingwhichinstructionsexecuted基于所耗时间的大小，对操作数的大小进行猜测RSAexploitstimetakeninexponentiationCountermeasures(解决办法)useconstantexponentiationtime（不变的幂运算时间）addrandomdelays（随机时延）blindvaluesusedincalculations（隐蔽）2020/2/24西安电子科技大学计算机学院35选择密文攻击RSA对于选择密文来说是易受攻击的攻击者选择密文并得到相应明文选择密文可给密码分析者探测RSA的特性提供信息optimalasymmetricencryptionpadding(OAEP).2020/2/24西安电子科技大学计算机学院36小结公钥密码的原理两个密钥：公钥/私钥单向陷门函数RSA算法，实现和安全分析2020/2/24西安电子科技大学计算机学院37第9章作业思考题：9.19.39.6习题：9.2.a9.2.b9.39.4