公鑰密碼技術

第5講公鑰密碼技術楊明紫金學院計算機系網絡信息安全10/22/2024內容公鑰密碼的基本概念RSA公鑰體制Diffie-Hellman密鑰交換公開密鑰的管理NewDirectionsinCryptography,byWhitfieldDiffieandMartin.E.Hellman,IEEETrans.Inform.Theory,vol.IT-22,pp.644--654,Nov.1976

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

ed＝1modφ(n)

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

數論Euler定理

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

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