网络安全-08：公钥密码学与RSA.ppt

Chapter9公钥密码学与RSA,密码编码学与网络安全,对称密码,2020/5/13,西安电子科技大学计算机学院,3,对称密码体制的缺陷,如何解决这些问题?,要进行保密通信，事先不秘密传送密钥行不行？,已学到的方法,Alice,Bob,带一把锁的对称密码体制能否实现？,Shamir盒,Alice,Bob,对你的启示？,1.不事先交换密钥就能进行秘密通信2.加密、解密的密钥可以分开,课程目标,公钥密码体制的原理公钥加密数字签名密钥交换RSA算法,私钥和公钥密码体制共存共同发展二者能够实现优势互补,Note,2020/5/13,西安电子科技大学计算机学院,9,公钥密码体制,密码学发展历史中最伟大的一次革命采用两个密钥：一个公钥，一个私钥参与方不对等，所以是非对称的；基于数论中的结论是私钥密码的补充而不是代替,2020/5/13,西安电子科技大学计算机学院,10,为什么需要公钥密码?,两个考虑：密钥分配-KDC数字签名公认该发明属于StanfordUni的WhitfieldDiffie和MartinHellman，于1976年。NewDirectionsinCryptography,IEEETrans.InformationTheory,IT-22,pp644-654,Nov1976JamesEllis(UKCESG)在1970年曾提出此概念,2020/5/13,西安电子科技大学计算机学院,11,公钥密码体制,公钥/双钥/非对称密码都是指使用两个密钥:公钥：可以对任何人公开的密钥，用于加密消息或验证签名。私钥：只能由接收者私存，用于解密消息或签名。非对称用于加密消息或验证签名的人不能进行消息的加密或消息的签名。,10.12,公钥密码体制的一般思路,公钥密码体制思路,10.13,公钥密码体制公私钥对,10.14,公钥密码体制的一般思路,公钥密码体制加解密算法,C=E(Kpub,P)P=D(Kpriv,C),计算复杂性理论,准则1,公钥密码的设计准则1,单向函数（One-WayFunction）,定义：一个函数f，对于定义域内的任意f，计算f(x)都是容易的，然而对于值域内的任意y，计算f-1(y)都是困难的。,例：蹦极,公钥密码的设计准则2：已知加解密密钥时，进行加解密运算计算上是容易的,准则2,单向函数能够满足这一条件吗？,陷门单向函数TrapdoorOne-WayFunction,定义：包含一组秘密信息（陷门）的特殊单向函数，已知陷门信息时求逆是容易的。,例：邮筒,陷门单向函数,利用困难问题离散对数问题大整数分解问题,困难问题,公钥密码的设计就是陷门单向函数的构造,2020/5/13,西安电子科技大学计算机学院,20,公钥密码体制：保密性和认证,2020/5/13,西安电子科技大学计算机学院,21,公钥算法分类,Public-KeyDistributionSchemes(PKDS)用于交换秘密信息(依赖于双方主体)常用于对称加密算法的密钥PublicKeyEncryption(PKE)用于加密任何消息任何人可以用公钥加密消息私钥的拥有者可以解密消息任何公钥加密方案能够用于密钥分配方案PKDS许多公钥加密方案也是数字签名方案SignatureSchemes用于生成对某消息的数字签名私钥的拥有者生成数字签名任何人可以用公钥验证签名,2020/5/13,西安电子科技大学计算机学院,22,公钥密码体制的应用,分为三类:加密/解密(提供保密性)数字签名(提供认证)密钥交换(会话密钥)一些算法可用于上述三类，而有些只适用用于其中一类或两类。,2020/5/13,西安电子科技大学计算机学院,23,2020/5/13,西安电子科技大学计算机学院,24,公钥密码体制安全性分析,一样存在穷举攻击但所使用的密钥一般都非常大(512bits)安全性基于容易（加解密）和困难（破译）之间巨大的差别许多算法没有得到证明是安全的。（包括RSA）需要采用一些特别大的数字与私钥密码体制相比，速度慢。,2020/5/13,西安电子科技大学计算机学院,25,9.2RSA,1977由MIT的Rivest,Shamir和Adleman发明已知的且被广泛使用的公钥密码方案有限域中的乘方运算乘方运算需要O(logn)3)操作(容易的)使用一些大的整数(例如.1024bits)安全性基于大数的素因子分解的困难性素因子分解需要O(elognloglogn)操作(困难的),2020/5/13,西安电子科技大学计算机学院,26,RSA,1977由MIT的Rivest,Shamir和Adleman发明已知的且被广泛使用的公钥密码方案有限域中的乘方运算乘方运算需要O(logn)3)操作(容易的)使用一些大的整数(例如.1024bits)安全性基于大数的素因子分解的困难性素因子分解需要O(elognloglogn)操作(困难的),2020/5/13,西安电子科技大学计算机学院,27,2020/5/13,西安电子科技大学计算机学院,28,公开公钥（e,n）,保存私钥d,C=Pemodn,P=Cdmodn,RSA算法,两个限制RSA明文消息M一定要比模数n小RSA的明文消息M要和n互素？为什么？,RSA算法,1.选择：p=17,q=11;2.计算：n=17*11=1873.计算：(17*11)=(17-1)(11-1);=160,公钥目录,Bob的公钥:e=7,n=187,Bob的私钥:d=23,Bob的公钥:e=7,n=187,明文消息M=88,加密:C=887mod18711,解密:M=1123mod18788,RSA算法的例子,2020/5/13,西安电子科技大学计算机学院,32,RSA的工作原理,Euler定理:a(n)modn1其中(a,n)=1RSA中:n=pq(n)=(p-1)(q-1)仔细地选择e和d使得mod(n)下，两者互逆因此存在某个整数k，使得ed=1+k(n)成立所以:Cd=Med=M1+k.(n)=M1(M(n)kM1(1)k=M1=Mmodn,2020/5/13,西安电子科技大学计算机学院,33,幂运算,可以用平方和乘法运算N次方，只需要O(log2n)次乘法运算如.75=7471=37=10mod11如.3129=312831=53=4mod11,2020/5/13,西安电子科技大学计算机学院,34,加密的效率,加密要计算e次方幂若e较小,计算将很快通常选择e=65537(216-1)或选择e=3或e=17但若e太小(如e=3)将易受到攻击用中国剩余定理必须确保(e,(n)=1,2020/5/13,西安电子科技大学计算机学院,35,解密的效率,解密计算d次方幂看起来很大，否则不安全用中国剩余定理分别计算modp和modq，则可以得到所希望的答案比直接快约4倍,2020/5/13,西安电子科技大学计算机学院,36,RSA密钥的产生,RSA的用户必须:随机确定两个素数p,q选择e或d，并求出另一个素数p,q一定不能从n=pq轻易得到意味着数要足够大典型地用猜测或可能性测试指数e,d是互逆的,2020/5/13,西安电子科技大学计算机学院,37,RSA安全性分析,攻击RSA可能的方法有:穷举搜索(对于给定的数字规模是不可行的)数学攻击(基于计算(n)的困难性,模n的因子分解的困难性)计时攻击(基于解密的运行情况)选择密文攻击(RSA的已知特性),2020/5/13,西安电子科技大学计算机学院,38,RSA系统安全性与系统的参数,RSA系统安全性与系统的参数有很大关系，X.931标准,ISO/IEC14752对此提出以下几点：如果公钥e是奇数，e应与p-1，q-1互质；如果公钥e是偶数，e必须与(p-1)/2,(q-1)/2互质，且pqmod8不成立；模数的长应该为1024+256x，x=0,1；质数p，q应通过质数检测p-1,q-1,p+1,q+1应有大质数因子；gcd(p-1,q-1)应该小；p/q不应靠近两个小整数比值，且；|p-q|应有大质数因子。,2020/5/13,西安电子科技大学计算机学院,39,分解因子问题,数学攻击的三种形式:分解n=pq,计算(n)从而得到d直接确定(n)并计算d直接寻找d对于因子分解问题很多年来进展很慢用“LatticeSieve”(LS),算法，最好的是分解了200位十进制数(663bit)最大的改进就是对改进算法的改良QStoGHFStoLS当前假设1024-2048bitRSA是安全的确保p,q有相似的大小并满足其它约束,2020/5/13,西安电子科技大学计算机学院,40,计时攻击,20世纪90年代由PaulKocher提出探测操作中的时间变化eg.multiplyingbysmallvslargenumberorIFsvaryingwhichinstructionsexecuted基于所耗时间的大小，对操作数的大小进行猜测RSAexploitstimetakeninexponentiationCountermeasures(解决办法)useconstantexponentiationtime（不变的幂运算时间）addrandomdelays（随机时延）blindvaluesusedincalculations（隐蔽）,202