1、第5講 公鑰密碼技術楊 明紫金學院計算機系網絡信息安全2022-4-9內容n公鑰密碼的基本概念nRSA公鑰體制nDiffie-Hellman密鑰交換n公開密鑰的管理New Directions in Cryptography,by Whitfield Diffie and Martin. E. Hellman, IEEE Trans. Inform. Theory, vol. IT-22, pp. 644-654, Nov. 1976 Whitfield DiffieMartin Hellman密碼學中革命-公鑰密碼公鑰密碼的革命性意義n新理論n基本工具是數學函數而不是代換和置換n安全性是基于

2、數學難題n新技術n雙密鑰:kekdn非對稱加密:使用其中一個密鑰加密，使用另一個密鑰解密n可公開一個密鑰：僅知道密碼算法和公鑰要確定私鑰在計算上是不可行的公鑰密碼體制的原理n五元組（M，C，K，E，D）n雙密鑰KnKe Kd且由Ke 不能計算出 Kd ； nKe可公開, Kd保密K=(PK, SK)nPK為公鑰，SK為私鑰nSK嚴格保密，可作為個人的身份指紋n加密算法E和解密算法D可逆n方案1：c=E(m,PK), mD(c, SK)n方案2：c=E(m,SK), mD(c, PK)公開密鑰密碼的優點n簡化密鑰管理n實現數字簽名n簽名需要有無法被他人獲悉的能代表自身的秘密信息n簽名驗證時不會泄

3、漏上述秘密信息n密鑰交換n實現通過公開網絡環境下的密鑰協商簡化密鑰管理n對稱加密n密鑰分配困難n密鑰容易泄漏n通信雙方都知道密鑰n密鑰分配中心KDCn密鑰量大n密鑰生存期短簡化密鑰管理n非對稱加密n只需重點保護自己的私有密鑰n公有密鑰可通過相關機構進行下載，安全壓力小n密鑰存儲量小，使用方便n密鑰生存期長公鑰密碼的基本工作方式n保持機密性nc=E(m,PKB), mD(c, SKB)n保持真實性nc=E(m,SKA), mD(c, PKA)AliceBobSKBRSA公鑰體制n介紹n第一個公鑰密碼算法n1978年由Rivest, Shamir和Adleman提出nRSA密碼被譽為是一種風格幽雅

4、的公開密鑰密碼n迄今理論上最為成熟完善的公鑰體制n應用廣泛n安全性基于大整數分解RSA公鑰體制n構造過程,( )(1)(1)( )gcd( ( ), )11mod( )p qnpqf npqf ndf n ddadaf n選擇兩個素數尋找一個與互素的數計算 逆元( , , , , ), ,; , ,Kn p q a dn ap q d公開保密:mod,:mod,admncacnma加密過程加密密鑰解密過程解密密鑰RSA算法驗證nE和D的可逆性nc=E(m,e)=me mod nnD(c,d)=cd mod n=(me)dmod n ned1 mod(n) D(c,d)=(me)dmod n=m

5、 t(n)+1 n數論Euler定理 D(c,d)=m t(n)+1 =mn加密和解密運算的可交換性n D(E(m)=(me)d mod n =(md)e mod n=E(D(m)RSA算法示例n產生密鑰n選擇兩個素數: p=17 & q=11n計算 n = pq =1711=187 f(n)=(p1)(q-1)=1610=160n選擇加密密鑰 e : gcd(e,160)=1; choose e=7n確定對應的解密密鑰n de=1 mod 160 ， d 160 d=23 由于 237=161= 10160+1n公鑰PK=e, n=7,187n私鑰SK=d,p,q=23,17,11R

6、SA算法示例n加密與解密n公鑰PK=e, n=7,187n私鑰SK=d,p,q=23,17,11n明文m = 88n加密 c=me mod n= 887 mod 187 = 11 n解密 m =cd mod n= 1123 mod 187 = 88 RSA的安全性nRSA破解1mod( )( )(1)(1)()ddaf nf npqnpq計算e逆元大整數分解( , , , , ), ,; , ,Kn p q e dn ep q d公開保密nRSA的安全性依賴于大整數因子分解的難度n保密性良好RSA的安全性n安全性建議nRivest, Shamir和Adleman建議p和q為100位的十進制數，

7、這樣n為200位的十進制數。n估計200位的十進制數的因式分解在億次機要進行55萬年。n安全密鑰的產生np和q的長度接近np-1和q-1都包含大的素因子ngcd(p-1,q-1)很小混合密碼機制n比較nRSA涉及高次冪運算，加密和解密速度較慢nDES加密和解密速度較RSA快近一個數量級nRSA宜于密鑰管理而DES難于密鑰管理n結合使用n使用RSA進行密鑰的加密/解密n使用DES進行數據的加密/解密對稱加密和非對稱加密的混合使用n加密過程n數據加密密鑰knc1=Edes(m,k) c2=RSA(k,pkb) c=(c1, c2)明文數據加密加密加密數據 數據加密密鑰接收者公鑰 加密的數據加密密鑰

8、對稱加密和非對稱加密的混合使用明文數據加密數據 數據加密密鑰接收者私鑰 數據加密密鑰 解密解密n解密過程n數據加密密鑰knc=(c1, c2)nk=RSA (c2, skb)nm=Ddes(c1, k)數字信封技術Diffie-Hellman密鑰交換n密鑰交換（密鑰協商）n通信雙方通過不安全信道協商密鑰n竊聽者無法獲得密鑰ABxaxbK=f(a,xb)K=f(b,xa)f(xa,xb)得不到KDiffie-Hellman密鑰交換AliceBob1. 選擇選擇x1,g and p.2. 計算計算y1 = gx1 mod p4. 選擇選擇 x2.5. 計算計算 y2 = gx2 mod p7. 計

9、算計算 z = y2x1 mod p = gx1x2 mod p7.計算計算 z = y1x2 mod p = gx1x2 mod pTime(y1,g,p)3(y2)6“相同的密鑰相同的密鑰”Diffie-Hellman密鑰交換n安全性n離散對數問題n問題n有限域上的離散對數問題是難解問題,modxg gpxABgxagxbK=g(xaxb)f(xa,xb)得不到KK=g(xaxb)DH密鑰交換算法示例nAlice和Bob協商后采用素數p=353及其本原根a=3；nAlice選擇隨機數x=97，計算X=397 mod 353=40，并發送給Bob；nBob選擇隨機數y=233，計算Y=323

10、3 mod 353=248，并發送給Alice；nAlice計算k=Yx mod p=24897 mod 353=160；nBob計算k=Xy mod p=40233 mod 353=160。nk即為協商后的密鑰。公開密鑰的管理n公開密鑰的分配n公開宣布n公開可以得到的目錄n公開密鑰管理機構n公開密鑰證書公開密鑰的管理n公開宣布n簡單方便，不受控制n易于偽造AKuaKuaKuaKuan公開可以得到的目錄n公開密鑰放在公開密鑰目錄n目錄由可信機構負責n提高了安全性n仍有安全漏洞（篡改）AB公開密鑰目錄KuaKub公開密鑰的管理n公開密鑰管理機構n使用公開密鑰密碼完成管理n用戶知道管理機構的公鑰n存在瓶頸問題n公開密鑰證書n證書中包