公鑰密碼技術(shù)

第5講公鑰密碼技術(shù)楊明紫金學(xué)院計(jì)算機(jī)系網(wǎng)絡(luò)信息安全10/22/2024內(nèi)容公鑰密碼的基本概念RSA公鑰體制Diffie-Hellman密鑰交換公開(kāi)密鑰的管理NewDirectionsinCryptography,byWhitfieldDiffieandMartin.E.Hellman,IEEETrans.Inform.Theory,vol.IT-22,pp.644--654,Nov.1976

WhitfieldDiffieMartinHellman密碼學(xué)中革命-公鑰密碼公鑰密碼的革命性意義新理論基本工具是數(shù)學(xué)函數(shù)而不是代換和置換安全性是基于數(shù)學(xué)難題新技術(shù)雙密鑰:ke≠kd非對(duì)稱加密:使用其中一個(gè)密鑰加密，使用另一個(gè)密鑰解密可公開(kāi)一個(gè)密鑰：僅知道密碼算法和公鑰要確定私鑰在計(jì)算上是不可行的公鑰密碼體制的原理五元組（M，C，K，E，D）雙密鑰K＝<Ke,Kd>Ke≠Kd且由Ke不能計(jì)算出Kd；Ke可公開(kāi),Kd保密K=(PK,SK)PK為公鑰，SK為私鑰SK嚴(yán)格保密，可作為個(gè)人的身份指紋加密算法E和解密算法D可逆方案1：c=E(m,PK),m＝D(c,SK)方案2：c=E(m,SK),m＝D(c,PK)公開(kāi)密鑰密碼的優(yōu)點(diǎn)簡(jiǎn)化密鑰管理實(shí)現(xiàn)數(shù)字簽名簽名需要有無(wú)法被他人獲悉的能代表自身的秘密信息簽名驗(yàn)證時(shí)不會(huì)泄漏上述秘密信息密鑰交換實(shí)現(xiàn)通過(guò)公開(kāi)網(wǎng)絡(luò)環(huán)境下的密鑰協(xié)商簡(jiǎn)化密鑰管理對(duì)稱加密密鑰分配困難密鑰容易泄漏通信雙方都知道密鑰密鑰分配中心KDC密鑰量大密鑰生存期短簡(jiǎn)化密鑰管理非對(duì)稱加密只需重點(diǎn)保護(hù)自己的私有密鑰公有密鑰可通過(guò)相關(guān)機(jī)構(gòu)進(jìn)行下載，安全壓力小密鑰存儲(chǔ)量小，使用方便密鑰生存期長(zhǎng)公鑰密碼的基本工作方式保持機(jī)密性c=E(m,PKB),m＝D(c,SKB)保持真實(shí)性c=E(m,SKA),m＝D(c,PKA)AliceBobSKBRSA公鑰體制介紹第一個(gè)公鑰密碼算法1978年由Rivest,Shamir和Adleman提出RSA密碼被譽(yù)為是一種風(fēng)格幽雅的公開(kāi)密鑰密碼迄今理論上最為成熟完善的公鑰體制應(yīng)用廣泛安全性基于大整數(shù)分解RSA公鑰體制構(gòu)造過(guò)程RSA算法驗(yàn)證E和D的可逆性c=E(m,e)=memodnD(c,d)=cdmodn=(me)dmodn

ed＝1modφ(n)

D(c,d)=(me)dmodn=mtφ(n)+1

數(shù)論Euler定理

D(c,d)=mtφ(n)+1=m加密和解密運(yùn)算的可交換性

D(E(m))=(me)dmodn=(md))emodn=E(D(m))RSA算法示例產(chǎn)生密鑰選擇兩個(gè)素?cái)?shù):p=17&q=11計(jì)算n=pq=17×11=187f(n)=(p–1)(q-1)=16×10=160選擇加密密鑰e:gcd(e,160)=1;choosee=7確定對(duì)應(yīng)的解密密鑰de=1mod160，d<160

d=23由于23×7=161=10×160+1公鑰PK={e,n}={7,187}私鑰SK={d,p,q}={23,17,11}RSA算法示例加密與解密公鑰PK={e,n}={7,187}私鑰SK={d,p,q}={23,17,11}明文m

=88加密c=memodn=887mod187=11解密

m=cdmodn=1123mod187=88RSA的安全性RSA破解RSA的安全性依賴于大整數(shù)因子分解的難度保密性良好RSA的安全性安全性建議Rivest,Shamir和Adleman建議p和q為100位的十進(jìn)制數(shù)，這樣n為200位的十進(jìn)制數(shù)。估計(jì)200位的十進(jìn)制數(shù)的因式分解在億次機(jī)要進(jìn)行55萬(wàn)年。安全密鑰的產(chǎn)生p和q的長(zhǎng)度接近p-1和q-1都包含大的素因子gcd(p-1,q-1)很小混合密碼機(jī)制比較RSA涉及高次冪運(yùn)算，加密和解密速度較慢DES加密和解密速度較RSA快近一個(gè)數(shù)量級(jí)RSA宜于密鑰管理而DES難于密鑰管理結(jié)合使用使用RSA進(jìn)行密鑰的加密/解密使用DES進(jìn)行數(shù)據(jù)的加密/解密對(duì)稱加密和非對(duì)稱加密的混合使用加密過(guò)程數(shù)據(jù)加密密鑰kc1=Edes(m,k)c2=RSA(k,pkb)c=(c1,c2)明文數(shù)據(jù)加密加密加密數(shù)據(jù)數(shù)據(jù)加密密鑰接收者公鑰加密的數(shù)據(jù)加密密鑰對(duì)稱加密和非對(duì)稱加密的混合使用明文數(shù)據(jù)加密數(shù)據(jù)數(shù)據(jù)加密密鑰接收者私鑰數(shù)據(jù)加密密鑰解密解密解密過(guò)程數(shù)據(jù)加密密鑰kc=(c1,c2)k=RSA(c2,skb)m=Ddes(c1,k)數(shù)字信封技術(shù)Diffie-Hellman密鑰交換密鑰交換（密鑰協(xié)商）通信雙方通過(guò)不安全信道協(xié)商密鑰竊聽(tīng)者無(wú)法獲得密鑰Diffie-Hellman密鑰交換AliceBob1.選擇x1,gandp.2.計(jì)算y1=gx1modp4.選擇x2.5.計(jì)算y2=gx2modp7.計(jì)算z=y2x1modp=gx1x2modp7.計(jì)算z=y1x2modp=gx1x2modpTime(y1,g,p)3(y2)6“相同的密鑰”Diffie-Hellman密鑰交換安全性離散對(duì)數(shù)問(wèn)題問(wèn)題有限域上的離散對(duì)數(shù)問(wèn)題是難解問(wèn)題DH密鑰交換算法示例Alice和Bob協(xié)商后采用素?cái)?shù)p=353及其本原根a=3；Alice選擇隨機(jī)數(shù)x=97，計(jì)算X=397mod353=40，并發(fā)送給Bob；Bob選擇隨機(jī)數(shù)y=233，計(jì)算Y=3233mod353=248，并發(fā)送給Alice；Alice計(jì)算k=Yxmodp=24897mod353=160；Bob計(jì)算k=Xymodp=40233mod353=160。k即為協(xié)商后的密鑰。公開(kāi)密鑰的管理公開(kāi)密鑰的分配公開(kāi)宣布公開(kāi)可以得到的目錄公開(kāi)密鑰管理機(jī)構(gòu)公開(kāi)密鑰證書(shū)公開(kāi)密鑰的管理公開(kāi)宣布簡(jiǎn)單方便，不受控制易于偽造公開(kāi)可以得到的目錄公開(kāi)密鑰放在公開(kāi)密鑰目錄目錄由可信機(jī)構(gòu)負(fù)責(zé)提高了安全性仍有安全漏洞（篡改）公開(kāi)密鑰的管理公開(kāi)密鑰管理機(jī)構(gòu)使用公開(kāi)密鑰密碼完成管理用戶知道管理機(jī)構(gòu)的公鑰存在瓶頸問(wèn)題公開(kāi)密鑰證書(shū)證書(shū)中包含公開(kāi)密鑰和其