现代密码学06---公钥密码学

现代密码学林喜军中国海洋大学信息安全实验室1公钥密码学第6章22本章内容36.1公钥密码学概述6.2单向函数6.3Diffie-Hellman密钥交换协议6.4RSA加密方案6.5ElGamal加密方案6.6数字信封3–源自美国黑色幽默派作家约瑟夫.赫勒(JosephHeller)的黑色幽默著作《二十二条军规》（Catch-22）。–该书引入了如下逻辑陷阱：•如果你疯了，只要你自己申请就允许你停止执行任务。可你一旦提出申请，就证明你不是疯子，还得接着执行任务。4约瑟夫.赫勒CATCH-22问题4如果你能证明自己疯了，那就说明你没疯。形容一件事陷入死循环•其他类似的CATCH-22问题–如果你去找工作，但没有工作经验。所有的招聘公司对你说，他们不招收没有工作经验的人。你将陷入CATCH-22问题的困境。–假设老板要你拿出个绝妙的新主意，你奉命照办了，但老板却说：“我们毫无先例可循？我们怎么能知道这个主意行不行？”5CATCH-22问题56密码学中的CATCH-22问题在保密通信中，通信双方在进行秘密通信之前，他们首先得共享密钥，即需要进行共享密钥的秘密通信，但“共享密钥的秘密通信”是否是安全的不能得到证明66.1公钥密码学概述778对称密码体制的缺陷密钥管理困难无法实现“非否认”密钥分发困难89–n个用户互相通信，系统中共有n(n-1)/2个密钥。如n=100时，共4,995个密钥。密钥爆炸。对称密码体制的缺陷密钥管理困难910–因为解密者也可以加密对称密码体制的缺陷无法实现“非否认”1011–与“CATCH-22问题”有关(如何安全地分发密钥)–密钥分发不仅要耗费巨大的成本，而且也很容易成为保密通信中的薄弱环节！对称密码体制的缺陷密钥分发困难1112•1976年，Diffie与Hellman提出公钥密码体制的设想参见：W.Diffie,M.Hellman,Newdirectionsincryptography,IEEETrans.onInformationTheory,IT-22(1976)6,644-654.HellmanDiffie公钥密码体制的提出公钥技术是二十世纪最伟大的思想之一，密码学一次伟大革命2015年，两人因此获得图灵奖12Diffieisoneofthepioneersofpublic-keycryptography.Now，heisamemberofthetechnicaladvisoryboardatCryptomathic,wherehecollaborateswithresearcherssuchasV.RijmenandI.Damgård。WhitfieldDiffie1314Hellmanisbestknownforhisinventionofpublickeycryptography.Heisalongtimecontributortothecomputerprivacydebateandismorerecentlyknownforpromotingriskanalysisstudiesonnuclearthreats,includingtheNuclearRisk.orgwebsite.MartinHellmanStanfordUniversity14•基本思想：•Alice有一个加密密钥PK，以及一个解密密钥SK•PK公开，SK保密（要求PK的公开不能影响SK的安全）•Bob要向Alice发送明文M时，可先查Alice的加密密钥PK，并用PK加密得密文C•Alice收到C后，用只有她自己才掌握的解密密钥SK解密C得到M。公钥密码体制的提出•当时Diffie和Hellman还没有实现这种体制的具体算法。15明文M公钥PK16加密E(·)解密D(·)明文M密文C私钥SK破译公开信道公钥密码学下的秘密通信模型公钥PKEPK(M)=C加密DSK(C)=M解密DSK(EPK(M))=M1617•加密与解密由不同的密钥完成–公钥:用于加密，任何人都可以知道(包括攻击者)–私钥:用于解密，必须保密•加解密的非对称性，故而又称非对称密码公钥密码学的特点1718公钥密码体制的基本组成部分公钥私钥加密算法解密算法明文密文1819公钥密码算法应满足的条件以上要求的本质在于，公钥密码算法需要一个陷门单向函数研究公钥密码算法就是先找出合适的陷门单向函数，在其基础上构造算法产生密钥是计算上容易的1用公钥加密明文是计算上容易的2知道私钥，解密密文是计算上容易的3通过密文/公钥，恢复明文/私钥是计算上不可行的4196.2单向函数202021单向函数的概念是公钥密码学的中心概念2122•现实世界中的例子——烧掉纸–把纸烧掉很容易–从纸灰恢复出原来的纸，却非常难单向函数的特点计算容易，求逆非常困难特点已知x，计算f(x)很容易已知f(x)，计算x很难“难”：任何概率多项式时间算法对单向函数求逆可以成功的概率都是可忽略的。2223•单向函数的定义：函数f:{0,1}*→{0,1}*称为单向函数，如果①存在概率多项式时间算法，给定x，输出f(x)②对任意概率多项式时间算法A，存在一个可忽略的函数ν(·)，使得对于足够大的k，有Pr[f(z)=y|x{0,1}k;yf(x);zA(1k,y)]≤ν(k)称k为安全参数一个长度为k的二进制串xy是f(x)的结果y根据y和长度k，寻找一个z，使得f(z)=y算法A目的算法A能达成目的的概率是可忽略的。如果对于所有这样的A，这一概率都满足，那么，f便是单向函数注意：z可以和x不同。也即，A的输出可以与f的输入不同所以，A不必一定找到x也能成功24f(x)=1|x|是单向函数吗？•回答：不是.Why?•找到z，使得f(z)=1|x|很容易•因为任意与x长度相同的比特串z都满足f(z)=1|z|=1|x|单向函数举例2425Q:单向函数在密码学中很有用，但它们是否存在呢？没有人证明单向函数是否真的存在，也没有实际的证据能够构造出真正的单向函数•但是，有很多函数看起来像单向函数–我们能有效地计算它们，且至今还不知道有什么办法能容易地求出它们的逆2526单向函数的作用单向函数不能用于加密，因为用单向函数加密的明文，没人能解开作用例：有人把消息写在纸上,然后把纸烧掉,把纸灰给你，让你恢复出消息。你会怎样？看看他的表情，一定在得儿意地笑！所以，除了单向以外，还需要一些其他的东西2627陷门单向函数计算很容易，求逆很困难。但知道秘密陷门的话，求逆将非常容易特点陷门单向函数满足下列条件：①给定x，计算y=f(x)很容易②给定y，计算x使y=f(x)很困难③给定e，对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的仅满足①、②两条的函数是单向函数第②条性质暗示仅由y推测x是计算上不可行的第③条称为陷门性，e称为陷门信息2728•基本思想①将f做为加密算法公开②任何人都可将明文x加密得到密文y=f(x)③合法用户(知道陷门信息)容易由y求x，实现解密④攻击者(不知道陷门信息)无法由密文y求得明文x如何用陷门单向函数f构造公钥密码陷门单向函数的强度取决于所依赖问题的计算复杂性(问题的困难性)2829•一个困难问题可以转化为密码体制必须满足以下条件：–能将陷门信息成功且安全地嵌入到该问题中，使得只有用该陷门信息才可以有效求解注意不是所有的困难问题都能转化成密码体制2930•它们是否真是单向函数，并未得到证明。但到目前为止，还没找到多项式时间算法能解决这些问题。•因此，“它们是困难的”只是一个假设，称为困难假设候选的单向函数离散对数问题大整数分解问题Diffie-Hellman问题3031设p是素数，g∈Zp*是生成元.给定p,g,y=gx，求x.(称x是以g为底y的离散对数)候选的单向函数离散对数问题•给定x，求gx很容易•给定p,g,gx，求x却很难性质3132已知n是两个大素数p和q的乘积，对n进行分解，求出p和q候选的单向函数大整数分解问题•给定p和q，求n很容易•给定n，求p和q却很难性质3233给定(p,g,gx,gy)，p是素数，g∈Zp*是生成元①计算Diffie-Hellman问题(CDH)计算gxy②判定Diffie-Hellman问题(DDH)给定T∈Zp*，判断T是否等于gxy候选的单向函数Diffie-Hellman问题•给定x或y，计算gxy很容易•给定p,g,gx,gy，计算gxy很难•对任意的T，判断是否T=gxy很难性质336.3DH密钥交换协议343435•公钥密码的提出，首先是解决从未见过面的两个人如何实现秘密通信的问题。–实质是，如何在公开信道上(肯定不安全)，实现对称密钥的秘密传递。•Diffie-Hellman密钥交换方案正是为解决这一问题而提出的–基于的困难问题被称为Diffie-Hellman问题35Q:从未见过面的两个人如何实现秘密通信？36(YBx)modp=K(YAy)modp=KYB=gyYA=gxYAYB(gxy)modp=K(gxy)modp=K•系统建立：–随机选择素数p–随机选择生成元g∈Z*pDiffie-Hellman密钥交换方案3637•注意–该方案不能用于交换任意实际的信息–仅允许安全地共享一个密钥，用于后续通讯中使用对称密码体制Diffie-Hellman密钥交换方案3738gx随机选择x随机选择zgz随机选择ygy拦截拦截gzK=gxzK’=gyzK=gxzK’=gyz共享共享Diffie-Hellman密钥交换方案中间人攻击3839如何防止中间人攻击•需要对传送的信息进行认证保护，以使通信双方知道到底在与谁进行密钥交换Diffie-Hellman密钥交换方案中间人攻击396.4RSA加密方案404041•1977年，由MIT的三位密码学家Rivest，Shamir，Adleman联合发明RivestShamirAdleman参见：Rivest,Shamir,Adleman.Amethodforobtainingdigitalsignaturesandpublickeycryptosystems.CommunicationsoftheACM,1978,21(2):120-126.2002年，三人因RSA的发明共同获得图灵奖RSA加密方案4142RivestistheinventorofthesymmetrickeyencryptionalgorithmsRC2,RC4,RC5,andco-inventorofRC6.TheRCstandsforRivestCipher,oralternatively,Ron'sCode.HealsoauthoredMD2,MD4,MD5andMD6.RonaldL.RivestMIT4243ShamirisanIsraelicryptographer.Heisaco-inventoroftheFeige-Fiat-Shamiridentificationscheme,oneoftheinventorsofdifferentialcryptanalysisandhasmadenumerouscontributionstothefieldsofcryptographyandcomputerscience.AdiShamirWeizmannInstituteofScience4344LeonardAdlemanAdlemaniswellknownforDNAcomputingandwidelyreferredtoastheFatherofDNAComputing.HeisoneoftheoriginaldiscoverersoftheAdleman-Pomerance-Rumelyprimalitytest.HeisalsoanamateurboxerandhassparredwithJamesToney.UniversityofSouthernCalifornia4445•RSA被提出后，得到最广泛的应用。•1992年，ISO颁布的国际标准X.509中，引入RSA算法。•RS