搜索
第十二讲ElGamal公钥体制Diffie-Hellman协议Public-KeyCryptographypublic-key/two-key/asymmetric包括两个密钥:公开密钥(apublic-key),可以被任何人知道,用于加密或验证签名私钥(private-key),只能被消息的接收者或签名者知道,用于解密或签名加密或验证签名者不能解密或多或生成签名.是密码学几千年历史中最有意义的结果.公钥加密方案ElGamal公钥加密方案Diffie-Hellmankeydistributionscheme的变形能够用于安全交换密钥publishedin1985byElGamal:T.ElGamal,APublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms,IEEETrans.InformationTheory,volIT-31(4),pp469-472,July1985.安全性是基于离散对数缺点：增加了消息长度（2倍）密钥建立密钥生成：选取一个大素数p及本原元amodp接收者Bob有一个密秘钥xB计算yB=axBmodpElGamal加密为加密M发送者选择随机数k,0=k=p-1计算消息密钥K:K=yBkmodp计算密文对:C={C1,C2}C1=akmodpC2=K.Mmodp发送到接收者k需要永久保密ElGamal解密首先计算messagekeyKK=C1xBmodp=ak.xBmodp计算明文:M=C2.K-1modpElGamalExample选择p=97及本原根a=5recipientBob选择秘密钥xB=58&计算并发布公钥yB=558=44mod97Alice要加密M=3toBob首先得到Bob的公开密钥yB=44选择随机k=36计算:K=4436=75mod97计算密文对:C1=536=50mod97C2=75.3mod97=31mod97发送{50,31}toBobBob恢复messagekeyK=5058=75mod97Bob计算K-1=22mod97Bob恢复明文M=31.22=3mod97公钥的安全性依赖于足够大大的困难性差别类似与对称算法,穷搜索在理论上是能够破解公钥密码exhaustivesearch但实际上,密钥足够长(512bits)一般情况下,有一些已知的困难问题(hardproblem”要求足够大的密钥长度(512bits)导致加密速度比对称算法慢P至少为150位十进制以上P-1至少有一个大数因子Diffie-Hellman密钥分配方案公钥密码问世Diffie&Hellmanin1976:密钥交换的实际方法公钥方案概念的提出WDiffie,MEHellman,NewdirectionsinCryptography,IEEETrans.InformationTheory,IT-22,pp644-654,Nov1976JamesEllis(UKCESG)在案970年曾提出此概念公钥分配方案不能用于交换任意消息可以建立共享密钥(双方共享)依赖于双方的公、私钥值基于有限域上的指数问题安全性是基于计算离散对数的困难性Diffie-HellmanSetup两个通信主体Alice&Bob,希望在公开信道上建立密钥初始化:选择一个大素数p(~200digits)一个生成元Alice选择一个秘密钥(secretkey(number)xAp)Bob)选择一个秘密钥(secretkey(number)xBpAliceandBob计算他们的公开密钥:yA=axAmodpyB=axBmodpAlice,Bob分别公开yA,yBDiffie-Hellman密钥交换计算共享密钥:KAB=axA.xBmodp=yAxBmodp(whichBcancompute)=yBxAmodp(whichAcancompute)KAB可以用于对称加密密钥Diffie-Hellman举例选取素数p=97,及本根a=5Alice选取秘密xA=36&计算公钥yA=536=50mod97Bob选取秘密xB=58&计算公钥yB=558=44mod97AliceandBob交换公钥(50&44respectively)Alice计算公享秘密K=4436=75mod97Bob计算公享秘密K=5058=75mod97Diffie-HellmaninPractise两个主体每次可以选择新的秘密密钥(私钥),并计算及交换新的公钥可以抵抗被动攻击,但不能抵抗主动攻击每次可以给出新的密钥为抵抗主动攻击,需要其它新的协议也可以建立长期公钥,第三方攻击D-H的key交换容易被中间人攻击。在这个攻击中，敌人C截取A的公共值，然后发送自己的公共值给C，当B传递自己的公共值时，C代替B发送它自己的公共值给A，因此C和A同意彼此的共享key，C和B同意彼此的共享key。经过这个交换，C只需简单的解密任何由A或B发送的数据，然后在再次被使用合适的key加密以前读取并且修改这些数据，然后传输这些数据到另一方。漏洞原因D-H之所以有这个弱点，是因为key在交换时并不对其参与者进行认证。可能的解决办法是使用数字签名，以及使用其它的协议变种。改进措施1992年Diffie,vanOorschot和Wiener开发了authenticatedDiffie-Hellmankeyagreementprotocol，或称为Station-to-Station(STS)协议，它用于防止在Diffie-Hellmankeyagreementprotocol上的中间人攻击。它对中间人攻击的免疫来自于两方面，一个是使用数字签名来相互认证，另一个是使用public-keycertificate。改进措施使用STS协议时，A与B都提供自己的公钥/密钥对和共钥的证书，A根据一些消息来计算一个签名，其中包括公共值g^amodp，B也做类似的运算。即使C仍然能够截取A与B之间的信息，但他并不能在没有A和B的密钥的情况下伪造签名，因此，这个增强的协议抵挡了中间人攻击。快速模运算Chivers(1984)快速运算:givenanintegerAn-1A=SUMai.bii=0小结公钥密码的概念Diffie-Hellman公钥分配方案Exercises1.IllustratetheoperationoftheDiffie-Hellmanpublickeyexchangescheme,giventhefollowingpublicparameters:primep=37primroota=5ComputesuitablepublickeysforusersAliceandBob,andillustratethekeyexchange,verifyingthatthesamesharedsessionkeyisobtained.2.IllustratetheoperationoftheDiffie-Hellmanpublickeyexchangescheme,giventhefollowingpublicparameters:primep=59primroota=6Asabove.Exercises3、IllustratetheoperationofRSA,giventhefollowingparameters:Systemmodulusn=119(7x17)encryptionexpe=11Determinethedecryptionexponentd,andhencedetailsthepublicandprivatekeysforthisuser.ThenshowhowamessageM=20wouldbeencryptedanddecrpyted.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（可作为共享密钥）。（此协议是没有认证的交换协议，但可以通过第三方对交换的消息认证、签名）