第09讲 公钥密码学

1、第九讲公钥密码学,上海交通大学计算机科学与工程系,1.对称密码体制的缺陷：,2.Public-KeyCryptography,public-key/two-key/asymmetric包括两个密钥:公开密钥(apublic-key),可以被任何人知道,用于加密或验证签名私钥(private-key),只能被消息的接收者或签名者知道,用于解密或签名加密或验证签名者不能解密或多或生成签名.是密码学几千年历史中最有意义的结果,3.公钥加密方案,4.公钥密码理论,由私钥及其他密码信息容易计算出公开密钥(apolynomialtime(P-time)problem)由公钥及算法描述,计算私钥是难的(an

2、NP-timeproblem)因此,公钥可以发布给其他人(wishingtocommunicatesecurelywithitsowner)密钥分配问题不是一个容易的问题(thekeydistributionproblem),5.公钥算法分类,Public-KeyDistributionSchemes(PKDS)用于交换秘密信息(依赖于双方主体)常用于对称加密算法的密钥PublicKeyEncryption(PKE)用于加密任何消息任何人可以用公钥加密消息私钥的拥有者可以解密消息任何公钥加密方案能够用于密钥分配方案PKDS许多公钥加密方案也是数字签名方案SignatureSchemes用于生成

3、对某消息的数字签名私钥的拥有者生成数字签名任何人可以用公钥验证签名,6.公钥的安全性,依赖于足够大大的困难性差别类似与对称算法,穷搜索在理论上是能够破解公钥密码exhaustivesearch但实际上,密钥足够长(512bits)一般情况下,有一些已知的困难问题(hardproblem”要求足够大的密钥长度(512bits)导致加密速度比对称算法慢,7.Diffie-Hellman密钥分配方案,公钥密码问世Diffie&Hellmanin1976:密钥交换的实际方法公钥方案概念的提出WDiffie,MEHellman,NewdirectionsinCryptography,IEEETrans.

4、InformationTheory,IT-22,pp644-654,Nov1976JamesEllis(UKCESG)在案970年曾提出此概念,8.公钥分配方案,不能用于交换任意消息可以建立共享密钥(双方共享)依赖于双方的公、私钥值基于有限域上的指数问题安全性是基于计算离散对数的困难性,9.Diffie-HellmanSetup,两个通信主体Alice&Bob,希望在公开信道上建立密钥初始化:选择一个大素数p(200digits)一个生成元Alice选择一个秘密钥(secretkey(number)xAp)Bob)选择一个秘密钥(secretkey(number)xBpAliceandBob计

5、算他们的公开密钥:yA=axAmodpyB=axBmodpAlice,Bob分别公开yA,yB,10.Diffie-Hellman密钥交换,计算共享密钥:KAB=axA.xBmodp=yAxBmodp(whichBcancompute)=yBxAmodp(whichAcancompute)KAB可以用于对称加密密钥,11.Diffie-Hellman举例,选取素数p=97,及本根a=5Alice选取秘密xA=36&计算公钥yA=536=50mod97Bob选取秘密xB=58&计算公钥yB=558=44mod97AliceandBob交换公钥(50&44respectively)Alice计算公

6、享秘密K=4436=75mod97Bob计算公享秘密K=5058=75mod97,12.Diffie-HellmaninPractise,两个主体每次可以选择新的秘密密钥(私钥),并计算及交换新的公钥可以抵抗被动攻击,但不能抵抗主动攻击每次可以给出新的密钥为抵抗主动攻击,需要其它新的协议也可以建立长期公钥,13.快速模运算,Chivers(1984)快速运算:givenanintegerAn-1A=SUMai.bii=0,16.小结,公钥密码的概念Diffie-Hellman公钥分配方案,练习,IllustratetheoperationoftheDiffie-Hellmanpublickeyexchangescheme,giventhefollowingpublicparameters:primep=37primroota=5ComputesuitablepublickeysforusersAliceandBob,andillustratethekeyexchange,verifyingthatthesamesharedsessionkeyisobtained.2.Illustratetheoperationofthe