公鑰密碼技術(shù)

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

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