第09讲 公钥密码学

第九讲公钥密码学上海交通大学计算机科学与工程系1）密钥分配问题通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现；2）密钥管理问题在有多个用户的网络中，任何两个用户之间都需要有共享的秘密钥，当网络中的用户n很大时，需要管理的密钥数目是非常大2/)1(nn。3）没有签名功能：当主体A收到主体B的电子文挡（电子数据）时，无法向第三方证明此电子文档确实来源于B。1.对称密码体制的缺陷：2.Public-KeyCryptographypublic-key/two-key/asymmetric包括两个密钥:公开密钥(apublic-key),可以被任何人知道,用于加密或验证签名私钥(private-key),只能被消息的接收者或签名者知道,用于解密或签名加密或验证签名者不能解密或多或生成签名.是密码学几千年历史中最有意义的结果3.公钥加密方案4.公钥密码理论由私钥及其他密码信息容易计算出公开密钥(apolynomialtime(P-time)problem)由公钥及算法描述,计算私钥是难的(anNP-timeproblem)因此,公钥可以发布给其他人(wishingtocommunicatesecurelywithitsowner)密钥分配问题不是一个容易的问题(thekeydistributionproblem)5.公钥算法分类Public-KeyDistributionSchemes(PKDS)用于交换秘密信息(依赖于双方主体)常用于对称加密算法的密钥PublicKeyEncryption(PKE)用于加密任何消息任何人可以用公钥加密消息私钥的拥有者可以解密消息任何公钥加密方案能够用于密钥分配方案PKDS许多公钥加密方案也是数字签名方案SignatureSchemes用于生成对某消息的数字签名私钥的拥有者生成数字签名任何人可以用公钥验证签名6.公钥的安全性依赖于足够大大的困难性差别类似与对称算法,穷搜索在理论上是能够破解公钥密码exhaustivesearch但实际上,密钥足够长(512bits)一般情况下,有一些已知的困难问题(hardproblem”要求足够大的密钥长度(512bits)导致加密速度比对称算法慢7.Diffie-Hellman密钥分配方案公钥密码问世Diffie&Hellmanin1976:密钥交换的实际方法公钥方案概念的提出WDiffie,MEHellman,NewdirectionsinCryptography,IEEETrans.InformationTheory,IT-22,pp644-654,Nov1976JamesEllis(UKCESG)在案970年曾提出此概念8.公钥分配方案不能用于交换任意消息可以建立共享密钥(双方共享)依赖于双方的公、私钥值基于有限域上的指数问题安全性是基于计算离散对数的困难性9.Diffie-HellmanSetup两个通信主体Alice&Bob,希望在公开信道上建立密钥初始化:选择一个大素数p(~200digits)一个生成元Alice选择一个秘密钥(secretkey(number)xAp)Bob)选择一个秘密钥(secretkey(number)xBpAliceandBob计算他们的公开密钥:yA=axAmodpyB=axBmodpAlice,Bob分别公开yA,yB10.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计算公享秘密K=4436=75mod97Bob计算公享秘密K=5058=75mod9712.Diffie-HellmaninPractise两个主体每次可以选择新的秘密密钥(私钥),并计算及交换新的公钥可以抵抗被动攻击,但不能抵抗主动攻击每次可以给出新的密钥为抵抗主动攻击,需要其它新的协议也可以建立长期公钥,13.快速模运算Chivers(1984)快速运算:givenanintegerAn-1A=SUMai.bii=016.小结公钥密码的概念Diffie-Hellman公钥分配方案练习1.IllustratetheoperationoftheDiffie-Hellmanpublickeyexchangescheme,giventhefollowingpublicparameters:primep=37primroota=5ComputesuitablepublickeysforusersAliceandBob,andillustratethekeyexchange,verifyingthatthesamesharedsessionkeyisobtained.2.IllustratetheoperationoftheDiffie-Hellmanpublickeyexchangescheme,giventhefollowingpublicparameters:primep=59primroota=6Asabove.END!!交换协议描述如下：1)A和B公开选择一个有限群G及一个群元素G。2）A生成一个随机整数a，，在群G中计算a，并把计算结果在公开信道上传给B2）B生成一个随机整数b，，在群G中计算b，并把计算结果在公开信道上传给A。3）A接收到b，并计算ab)(4）B接收到a，并计算ba)(此时，A和B已有了共享的群元素ab（可作为共享密钥）。（此协议是没有认证的交换协议，但可以通过第三方对交换的消息认证、签名）