第5章公鑰密碼體制edit

1、112 Warm up 1. 2.23 解密是加密的逆運(yùn)算解密是加密的逆運(yùn)算: : Dk( )=( )=Ek-1-1( )( )； 解密與加密使用同樣的密鑰，解密與加密使用同樣的密鑰， 掌握了加密方法與密鑰的人，就能解密。掌握了加密方法與密鑰的人，就能解密。 這樣的密碼系統(tǒng)被稱為這樣的密碼系統(tǒng)被稱為對稱密鑰體系對稱密鑰體系（也叫（也叫單密鑰制系統(tǒng)單密鑰制系統(tǒng)）。）。對稱密鑰系統(tǒng)對稱密鑰系統(tǒng)(symmetric cipher)溫舊引新溫舊引新 4提 綱公公鑰鑰密密碼碼體制體制概概述述RSA密密鑰鑰分配分配與與管理管理123455.1 公鑰密碼體制概述公鑰密碼體制概述(asymmetric cip

2、her) 參考文獻(xiàn)：參考文獻(xiàn)：1盧開澄：盧開澄：計算機(jī)密碼學(xué)計算機(jī)密碼學(xué) 清華大學(xué)出版社清華大學(xué)出版社（1998年年7月第二版）月第二版） 2章照之：章照之：現(xiàn)代密碼學(xué)基礎(chǔ)現(xiàn)代密碼學(xué)基礎(chǔ) 北京郵電大學(xué)北京郵電大學(xué)出版社出版社 （20042004年年4 4月第月第1 1版）版） 6外語關(guān)鍵詞外語關(guān)鍵詞 公鑰密鑰體系：公鑰密鑰體系： asymmetric cipher 計算復(fù)雜性：計算復(fù)雜性：computational complexity 素數(shù)分解素數(shù)分解：factorization of prime number 離散對數(shù)：離散對數(shù)：Discrete Logarithms 單向陷門函數(shù)：單向陷

3、門函數(shù)：trap-door one-way function 公鑰與私鑰：公鑰與私鑰：Public Key and Private Key 7 20 20世紀(jì)末世紀(jì)末, ,電子商務(wù)與因特網(wǎng)迅速發(fā)展，一方面電子商務(wù)與因特網(wǎng)迅速發(fā)展，一方面極大地方便了人們對信息的交換和共享極大地方便了人們對信息的交換和共享, ,另一方面，另一方面，也給安全通信提出了很多新的需求，傳統(tǒng)的單鑰制也給安全通信提出了很多新的需求，傳統(tǒng)的單鑰制密碼系統(tǒng)對此無能為力。如何更好地解決信息安全密碼系統(tǒng)對此無能為力。如何更好地解決信息安全問題，已成為刻不容緩的任務(wù)。問題，已成為刻不容緩的任務(wù)。1 1、對稱密碼體制面對的形勢、對稱密

4、碼體制面對的形勢 5.1.1 5.1.1 公鑰密碼體系產(chǎn)生的背景：公鑰密碼體系產(chǎn)生的背景：82 2、傳統(tǒng)密碼體制已不適應(yīng)形勢的發(fā)展、傳統(tǒng)密碼體制已不適應(yīng)形勢的發(fā)展1). 功能上的缺憾功能上的缺憾 傳統(tǒng)密碼學(xué)不擅長認(rèn)證功能。傳統(tǒng)密碼學(xué)不擅長認(rèn)證功能。 2). 使用上的難題使用上的難題 密鑰交換是對稱密鑰體制的難題。密鑰交換是對稱密鑰體制的難題。 3). 管理上的困難管理上的困難 密鑰管理問題成了通信的瓶頸。密鑰管理問題成了通信的瓶頸。9 在這種情況下，一種新的密碼體制在這種情況下，一種新的密碼體制出現(xiàn)了。它就是公開密鑰系統(tǒng)，也稱出現(xiàn)了。它就是公開密鑰系統(tǒng)，也稱非非對稱密鑰體系對稱密鑰體系（也叫（

5、也叫雙密鑰制系統(tǒng)雙密鑰制系統(tǒng)）。）。從理論到實(shí)踐上逐步解決了對稱密鑰存從理論到實(shí)踐上逐步解決了對稱密鑰存在的問題，并從根本上提升了密碼學(xué)的在的問題，并從根本上提升了密碼學(xué)的理念，標(biāo)志著密碼學(xué)進(jìn)入了嶄新的發(fā)展理念，標(biāo)志著密碼學(xué)進(jìn)入了嶄新的發(fā)展階段。階段。 3 3、非對稱密鑰體系開始出現(xiàn)、非對稱密鑰體系開始出現(xiàn)105.1.2 公鑰密碼體系的幾種算法 一種新理論新技術(shù)的產(chǎn)生，一方面是因一種新理論新技術(shù)的產(chǎn)生，一方面是因?yàn)閷?shí)際問題的需求，另一方面，也是科學(xué)發(fā)為實(shí)際問題的需求，另一方面，也是科學(xué)發(fā)展的必然結(jié)果。展的必然結(jié)果。 創(chuàng)新成果的產(chǎn)生，源于對前人成果的不斷積累與改進(jìn)，也離不開發(fā)明者開創(chuàng)性的思維。

6、我們將通過三個典型案例的介紹，向同學(xué)們展示公鑰密碼體系的產(chǎn)生過程。111.Merkle難題 (Puzzle)： 起初人們并沒有想到去發(fā)明一個公鑰密碼，起初人們并沒有想到去發(fā)明一個公鑰密碼，只不過是為了解決在只不過是為了解決在普通信道中完成密鑰交換普通信道中完成密鑰交換問題而進(jìn)行了一系列探索和努力。問題而進(jìn)行了一系列探索和努力。 1974年，年，Merkle為解決對稱單鑰制密鑰體為解決對稱單鑰制密鑰體系的密鑰交換問題，提出了一個設(shè)想。系的密鑰交換問題，提出了一個設(shè)想。 Merkle密鑰交換協(xié)議如下：密鑰交換協(xié)議如下： 12uxi是是0999999之間一個任意的但又各不相同的隨機(jī)數(shù)；之間一個任意的

7、但又各不相同的隨機(jī)數(shù)；uYi也也是是0999999之間任意但又各不相同的隨機(jī)數(shù)，分之間任意但又各不相同的隨機(jī)數(shù)，分別作為每條消息的密鑰。別作為每條消息的密鑰。uAlice秘密保存所有秘密保存所有yi與與xi的密鑰對照表后，就把這的密鑰對照表后，就把這100萬條消息分別用所宣布的萬條消息分別用所宣布的yi加密，發(fā)給加密，發(fā)給Bob。Eyi(這條信息是這條信息是xi，它的密鑰是，它的密鑰是yi)明文明文 xj （1）Alice向向Bob發(fā)送發(fā)送100萬條消息萬條消息；13(2) Bob收到收到100萬條消息，從中任選一條，然后遍歷萬條消息，從中任選一條，然后遍歷100萬個密鑰進(jìn)行嘗試，總有一個萬個

8、密鑰進(jìn)行嘗試，總有一個yj可將其解密，從可將其解密，從而得知而得知xj的值。的值。(3) Bob以明文形式將以明文形式將xj發(fā)給發(fā)給Alice (4) Alice收到收到xj，即知，即知Bob所選的是哪個所選的是哪個yj，從而二人，從而二人都有了同樣的密鑰都有了同樣的密鑰yj。14Merkle安全性探討安全性探討 非法竊聽者非法竊聽者Eve，即使收到了全部往來的明文，即使收到了全部往來的明文和密文，為了找到和密文，為了找到xj對應(yīng)的對應(yīng)的yj，他需要對約，他需要對約100萬條消息一一作遍歷萬條消息一一作遍歷100萬萬個密鑰的嘗試。個密鑰的嘗試。 若嘗試若嘗試1個密鑰耗時個密鑰耗時1毫秒，嘗試毫

9、秒，嘗試100萬萬個密鑰個密鑰耗時耗時10001000秒秒17 7分鐘，這才解譯了一條消息，分鐘，這才解譯了一條消息，100萬條消息約萬條消息約3 31年才能全部試完。年才能全部試完。 而合法用戶乙最多只需要而合法用戶乙最多只需要17 7分鐘。分鐘。 此設(shè)計方案顯然不現(xiàn)實(shí)，但其思想是很先進(jìn)的。他用的是公開此設(shè)計方案顯然不現(xiàn)實(shí)，但其思想是很先進(jìn)的。他用的是公開的算法，的算法，通過普通（不安全）信道完成了密鑰交換，其保密機(jī)制是通過普通（不安全）信道完成了密鑰交換，其保密機(jī)制是基于計算復(fù)雜性，安全理念是基于破譯的時效性，其設(shè)計理念已經(jīng)基于計算復(fù)雜性，安全理念是基于破譯的時效性，其設(shè)計理念已經(jīng)進(jìn)入了公

10、鑰密碼的大門。進(jìn)入了公鑰密碼的大門。 14152 雙鑰制的提出 1976年年11月，美國斯坦福大學(xué)電月，美國斯坦福大學(xué)電氣工程系研究生氣工程系研究生W.Diffie和副教授和副教授Helman在在IEEE上發(fā)表了題為上發(fā)表了題為“密碼學(xué)新密碼學(xué)新方向方向“的學(xué)術(shù)論文，利用離散對數(shù)復(fù)雜性的學(xué)術(shù)論文，利用離散對數(shù)復(fù)雜性實(shí)際地解決了單鑰制的密鑰交換問題。實(shí)際地解決了單鑰制的密鑰交換問題。 16(1)(1)離散對數(shù)問題離散對數(shù)問題 設(shè)設(shè)p一個為大素數(shù)，已知整數(shù)一個為大素數(shù)，已知整數(shù)x和和b ，不難求，不難求出出: modxybp例如，例如，y=3=36 6 mod 7=729 mod 7=1mod 7

11、=729 mod 7=1；然而若已知然而若已知 y 和和 b，用逆運(yùn)算求，用逆運(yùn)算求x卻十分困難卻十分困難: : logmodbxyp為了求上例的逆運(yùn)算：為了求上例的逆運(yùn)算：x=log3 1 mod 7=? 需要算出需要算出全部指數(shù)數(shù)據(jù)，全部指數(shù)數(shù)據(jù)，查表求反函數(shù)：查表求反函數(shù)：x 1 2 3 4 5 6y 3 2 6 4 5 1 17 遍歷法雖然是萬能的方法，卻是個笨方法。設(shè)想遍歷法雖然是萬能的方法，卻是個笨方法。設(shè)想如果如果p是一個六位數(shù)，計算大約是一個六位數(shù)，計算大約100萬個萬個x與與y的對照的對照表，再快也不會少于表，再快也不會少于1毫秒吧，而如果毫秒吧，而如果p是一個一百是一個一百

12、零六位的數(shù)，按照同樣的計算速度就需要零六位的數(shù)，按照同樣的計算速度就需要10100毫秒毫秒=3.171089年。年。 實(shí)際上，上面的估計還是太保守了。隨著數(shù)位實(shí)際上，上面的估計還是太保守了。隨著數(shù)位的增大，加減乘除都會變得更加繁雜，對于大數(shù)的乘的增大，加減乘除都會變得更加繁雜，對于大數(shù)的乘方運(yùn)算與求模運(yùn)算，計算量已經(jīng)遠(yuǎn)遠(yuǎn)增大，不能再沿方運(yùn)算與求模運(yùn)算，計算量已經(jīng)遠(yuǎn)遠(yuǎn)增大，不能再沿用計算小數(shù)的速度來估計了。用計算小數(shù)的速度來估計了。18（2 2）計算復(fù)雜性）計算復(fù)雜性 所謂復(fù)雜性指計算所必須的基本運(yùn)算步驟數(shù)量，它決定了所謂復(fù)雜性指計算所必須的基本運(yùn)算步驟數(shù)量，它決定了計算所必須的機(jī)時和占用的計算

13、機(jī)資源。計算所必須的機(jī)時和占用的計算機(jī)資源。 計算復(fù)雜性理論告訴我們，隨著數(shù)位計算復(fù)雜性理論告訴我們，隨著數(shù)位N的增大，計算量從的增大，計算量從小到大的次序是：小到大的次序是：常數(shù)常數(shù)對數(shù)函數(shù)對數(shù)函數(shù)logN 線性函數(shù)線性函數(shù)aN 二次函數(shù)二次函數(shù)N2 三次函數(shù)三次函數(shù)N3多項(xiàng)式函數(shù)多項(xiàng)式函數(shù)Nd 亞指數(shù)函亞指數(shù)函數(shù)數(shù)2 2logN logN 指數(shù)函數(shù)指數(shù)函數(shù)2 2N N或或1010N N。 多項(xiàng)式以下的運(yùn)算都認(rèn)為是有效算法，屬于可解問題（多項(xiàng)式以下的運(yùn)算都認(rèn)為是有效算法，屬于可解問題（P類），而比多項(xiàng)式發(fā)散更快的算法都被認(rèn)為是難解問題類），而比多項(xiàng)式發(fā)散更快的算法都被認(rèn)為是難解問題（NP類，

14、類，NPC類）。類）。 數(shù)學(xué)上已經(jīng)證明離散對數(shù)是非正常（數(shù)學(xué)上已經(jīng)證明離散對數(shù)是非正常（NP）類復(fù)雜問題）類復(fù)雜問題, ,計計算量隨著算量隨著N的增大而趨于無窮。的增大而趨于無窮。 19補(bǔ)充：補(bǔ)充：P問題、問題、NP問題和問題和NPC問題問題1 P問題問題 P是一個判定問題類，這些問題可以用一個確定性算法在是一個判定問題類，這些問題可以用一個確定性算法在多項(xiàng)式時間內(nèi)判定或解出。如果一個判定性問題的復(fù)雜度多項(xiàng)式時間內(nèi)判定或解出。如果一個判定性問題的復(fù)雜度是該問題的一個實(shí)例的規(guī)模是該問題的一個實(shí)例的規(guī)模n的多項(xiàng)式函數(shù)，則我們說這種的多項(xiàng)式函數(shù)，則我們說這種可以在多項(xiàng)式時間內(nèi)解決的判定性問題屬于可以

15、在多項(xiàng)式時間內(nèi)解決的判定性問題屬于P類問題。類問題。P類類問題就是所有復(fù)雜度為多項(xiàng)式時間的問題的集合。問題就是所有復(fù)雜度為多項(xiàng)式時間的問題的集合。2 NP問題（問題（Non-deterministic Polynomial） NP是一個判定問題類，這些問題可以用一個確定算法在是一個判定問題類，這些問題可以用一個確定算法在多項(xiàng)式時間內(nèi)檢查或驗(yàn)證出它們的解。也可以說這些問題多項(xiàng)式時間內(nèi)檢查或驗(yàn)證出它們的解。也可以說這些問題可以在非確定性多項(xiàng)式時間內(nèi)解決，它并不要求給出一個可以在非確定性多項(xiàng)式時間內(nèi)解決，它并不要求給出一個算法來求解問題本身，而只要求給出一個確定性算法在多算法來求解問題本身，而只要求

16、給出一個確定性算法在多項(xiàng)式時間內(nèi)驗(yàn)證它的解。項(xiàng)式時間內(nèi)驗(yàn)證它的解。顯然所有顯然所有P類問題都屬于類問題，但是是否等于？類問題都屬于類問題，但是是否等于？未解。未解。20 NPC問題問題 NPC，NP完全問題，是求完全問題，是求NP中判中判定問題的一個子類，是最不可能被定問題的一個子類，是最不可能被簡化為簡化為P的決定性問題的集合。的決定性問題的集合。 每一個每一個NPC問題都可以在多項(xiàng)式時問題都可以在多項(xiàng)式時間內(nèi)轉(zhuǎn)化為任何一個間內(nèi)轉(zhuǎn)化為任何一個NP問題。問題。補(bǔ)充：補(bǔ)充：P問題、問題、NP問題和問題和NPC問題問題21用戶用戶I 選選xi為私鑰為私鑰求出求出 yi=bxi mod p 為公鑰為

17、公鑰用戶用戶J 選選xj為私鑰為私鑰求出求出 yj=bxj mod p 為公鑰為公鑰發(fā)發(fā)b, p, yi發(fā)發(fā) yj=(bxj)xi=kij =(bxi)xj=（3 3）DiffieDiffie和和HelmanHelman的方案：的方案： 收到收到y(tǒng)j后后, 由由 (yj )xi mod p 得到會話密鑰得到會話密鑰收到收到y(tǒng)i后后, 由由 (yi )xj mod p 得到會話密鑰得到會話密鑰22 盡管公布了盡管公布了yi，yj和和p p，基于離散對數(shù)的困難性，基于離散對數(shù)的困難性，任何第三者難以求出任何第三者難以求出xi和和xj，因此無法獲得，因此無法獲得kij。 DiffieDiffie和和

18、HelmanHelman雖然討論的仍然是單鑰制的密鑰雖然討論的仍然是單鑰制的密鑰交換問題，但他們的觀念交換問題，但他們的觀念是很超前的。他們采用的算是很超前的。他們采用的算法是公開的，他們的法是公開的，他們的保密機(jī)制是基于計算復(fù)雜性，并保密機(jī)制是基于計算復(fù)雜性，并且他們首次提出了雙密鑰的觀點(diǎn)且他們首次提出了雙密鑰的觀點(diǎn)。因此這篇論文被認(rèn)。因此這篇論文被認(rèn)為是現(xiàn)代密碼學(xué)的開篇之作。為是現(xiàn)代密碼學(xué)的開篇之作。 22235.1.3 RSA公開密鑰體系公開密鑰體系 1978年美國麻省理工大學(xué)的年美國麻省理工大學(xué)的 Ron.Rivest、Adi.Shamir 和和 Len.Adleman 提出提出RSA

19、公鑰密碼體公鑰密碼體系。系。 它是它是第一個具有實(shí)用價值的公鑰密碼算法第一個具有實(shí)用價值的公鑰密碼算法. . 它是應(yīng)用最廣泛的公鑰密碼算法。它是應(yīng)用最廣泛的公鑰密碼算法。 它的原理是根據(jù)數(shù)論的歐拉定理。它的原理是根據(jù)數(shù)論的歐拉定理。 它的安全性是基于大數(shù)分解因數(shù)的復(fù)雜性。它的安全性是基于大數(shù)分解因數(shù)的復(fù)雜性。240、介紹-模運(yùn)算模運(yùn)算 模運(yùn)算：簡單的說，就是求余數(shù)。模運(yùn)算：簡單的說，就是求余數(shù)。 設(shè)設(shè)r是是a除以除以b的余數(shù)，的余數(shù)，a與與b的關(guān)系可表示為的關(guān)系可表示為a=r(mod b)，這就是，這就是模運(yùn)算模運(yùn)算。 例：例：23=11(mod12) 29 (mod 26) = 3 10 (

20、mod 26) = 3 -1 (mod 26) = 25模運(yùn)算在數(shù)論和程序設(shè)計模運(yùn)算在數(shù)論和程序設(shè)計中都有著廣泛的應(yīng)用，從中都有著廣泛的應(yīng)用，從奇偶數(shù)的判別到素數(shù)的判奇偶數(shù)的判別到素數(shù)的判別，從模冪運(yùn)算到最大公別，從模冪運(yùn)算到最大公約數(shù)的求法，從孫子問題約數(shù)的求法，從孫子問題到凱撒密碼問題，無不充到凱撒密碼問題，無不充斥著模運(yùn)算的身影。斥著模運(yùn)算的身影。 250、介紹-同余同余 一般地，兩個整數(shù)一般地，兩個整數(shù)a和和b，除以一個大于，除以一個大于1的自然的自然數(shù)數(shù)m所得的余數(shù)相同，就稱所得的余數(shù)相同，就稱a和和b對于模對于模m同余或同余或a和和b在模在模m下同余，記為下同余，記為ab(mod

21、m) 讀作a與b(模m)同余，“”讀作讀作“同余于同余于”。 如，如，1811(mod 7) 可用模將全體整數(shù)分類?？捎媚⑷w整數(shù)分類。 如用如用4來將整數(shù)分類，由于余數(shù)可為來將整數(shù)分類，由于余數(shù)可為0、1、2、3共四種，因而可分為四類：共四種，因而可分為四類：0，4，8，12，161，5，9，13，172，6，10，14，183，7，11，15，19260、介紹-模逆元模逆元 在公鑰密碼體制中，往往需要求解模逆元。在公鑰密碼體制中，往往需要求解模逆元。 求模逆元，即尋找一個求模逆元，即尋找一個x，使得，使得 a*x=1(mod n) 或或 1=(a*x) mod n 其中其中a和和n是正整

22、數(shù)，是正整數(shù)，x稱為稱為a的模的模n逆元。逆元。 也寫作：也寫作：a-1=x mod n例：例：4-1mod7=? 5-1mod14=? 2-1mod14=?4*2(mod 7)=123沒有逆元！沒有逆元！求解模逆元問題很困難，有時有結(jié)果，有時沒有結(jié)果。270 0、介、介紹-分解分解 因子分解就是對合數(shù)的分解。因子分解就是對合數(shù)的分解。 例：例：18=2*32，96=25*3，110=2*5*11 較好的因子分解方法：試除法、數(shù)域篩選法、橢圓曲較好的因子分解方法：試除法、數(shù)域篩選法、橢圓曲線法等。線法等。 但對于很大的數(shù)（但對于很大的數(shù)（1024bit以上的數(shù)）進(jìn)行因子分解，以上的數(shù)）進(jìn)行因子

23、分解，所需計算時間在目前條件下是一個天文數(shù)字。所需計算時間在目前條件下是一個天文數(shù)字。 所以，已知兩個大素數(shù)所以，已知兩個大素數(shù)p和和q，求其積很容易；，求其積很容易； 反之，知道反之，知道n求求p和和q就很困難。就很困難。RSARSA公鑰密碼體制公鑰密碼體制這樣的分解是獨(dú)一無二這樣的分解是獨(dú)一無二281、RSA算法原理 設(shè)設(shè)p和和q為兩個大素數(shù)，計算為兩個大素數(shù)，計算 n = pq 在小于在小于n的的 n- -1個正整數(shù)中個正整數(shù)中: 有有p- -1個正整數(shù)：個正整數(shù)：q, 2q, 3q, , (p-1)q 含因子含因子q； 有有q-1個正整數(shù)：個正整數(shù)：p, 2p, 3p, , (q-1)

24、p含因子含因子p； 除此之外的數(shù)（同余類）都與除此之外的數(shù)（同余類）都與n互素，其數(shù)目為：互素，其數(shù)目為： (n-1)-(p-1)-(q-1) = n-p-q+1 = pq-p-q+1 = (p-1)(q-1)； 令：令：(n) = (p-1)(q-1) 叫做歐拉數(shù)，代表小于叫做歐拉數(shù)，代表小于n且與且與n互素的數(shù)（同余類）的個數(shù)?；ニ氐臄?shù)（同余類）的個數(shù)。 注：嚴(yán)謹(jǐn)?shù)谋硎鰬?yīng)當(dāng)是同余類注：嚴(yán)謹(jǐn)?shù)谋硎鰬?yīng)當(dāng)是同余類-凡除以凡除以n后余數(shù)相同的整后余數(shù)相同的整 數(shù)為一個同余類）。數(shù)為一個同余類）。29 Euler(歐拉) 定理： 若若m與與n為互素的正整數(shù)，為互素的正整數(shù)， 則： m (n) 1 (

25、mod n) 若若k是任意整數(shù)是任意整數(shù),則則 mk也與也與n互素，于是有：互素，于是有： m k (n) 1 (mod n) m k (n) +1 m (mod n) （對任意（對任意 0 m n） 只要選擇只要選擇e,d, 滿足滿足ed 1 mod (n) ，（叫做在模，（叫做在模 (n) 運(yùn)算下運(yùn)算下d 和和e互為模逆元）互為模逆元） 即有：即有： ed=k(n)+1, 于是上式變?yōu)椋河谑巧鲜阶優(yōu)椋?med =m (mod n)得到得到d、e、n后，后，p、q、 (n)都銷毀都銷毀2930設(shè)設(shè)m為明文，由為明文，由：med = =m mod mod n出發(fā)出發(fā)可以設(shè)計出一種加、可以設(shè)計出

26、一種加、解密方案：解密方案：如果用如果用 me mod mod n作為加密計算結(jié)果，作為加密計算結(jié)果， 就可用就可用( (me) )d = = m mod mod n來解密；來解密；如果用如果用 md mod n作為加密計算結(jié)果，作為加密計算結(jié)果， 就可用就可用 (m d )e = =m mod n來解密。來解密。一般取一般取 (n, e) 為公鑰，為公鑰， 對明文對明文m進(jìn)行加密得到密文進(jìn)行加密得到密文 ：c=me mod n d d為私鑰，解密算法是：為私鑰，解密算法是： m=cd mod n 當(dāng)然也可以用私鑰加密：當(dāng)然也可以用私鑰加密： c=md mod n用公鑰解密：用公鑰解密： m=

27、c e mod n 31例例1取兩個小素數(shù)取兩個小素數(shù)p=11，q=3來演示來演示RSA的加、解密過程。的加、解密過程。解：先求出：解：先求出：n=pq=33,(n)=(p-1)(q-1)=20； 在在1 e (n)中中,取取e=7為公鑰為公鑰(與與20互素即可互素即可) 不難看到不難看到: 73 mod 20=1 d= 3（為私鑰）；（為私鑰）；設(shè)明文設(shè)明文m= (010)2 = 2，則，則: 密文密文 c = 2 7 =128 mod 33 mod 33 =29； 解密：解密：m = 293 mod 33 =24389 mod 33 =2； 32 因?yàn)橐驗(yàn)閑和和d是在模是在模(n) )運(yùn)算

28、下的互為倒數(shù)，當(dāng)運(yùn)算下的互為倒數(shù)，當(dāng)e與與d被被確定后，應(yīng)當(dāng)把確定后，應(yīng)當(dāng)把 p、q 和和(n) )都銷毀，僅留下都銷毀，僅留下n，e和和d是無法互相推導(dǎo)的。是無法互相推導(dǎo)的。 除非能將除非能將n分解，求出分解，求出p和和q，而大數(shù)的分解因數(shù)是，而大數(shù)的分解因數(shù)是Np類難題。因此類難題。因此RSA的安全得到保證。的安全得到保證。 2 2、RSARSA的安全性的安全性33提提 綱綱公公鑰鑰密密碼碼體制體制介介紹紹公鑰密碼體制特點(diǎn)公鑰密碼體制特點(diǎn)密密鑰鑰分配分配與與管理管理123 33345.2.1 公鑰密碼體制的特點(diǎn)1. 從形式上講：由對稱單鑰制到非對稱的雙鑰制加密和解密所用的算法和密鑰不同，而

29、且二加密和解密所用的算法和密鑰不同，而且二者不可互相推導(dǎo)。者不可互相推導(dǎo)。加密過程：加密過程：C = Ek1 M解密過程：解密過程：M = Dk2 C 352. 從使用上講：由隱蔽密鑰制到公開密鑰制 雙鑰制的出現(xiàn)引入了一個新觀念：一對不對雙鑰制的出現(xiàn)引入了一個新觀念：一對不對稱的密鑰中，可以只私密保密一把密鑰，稱稱的密鑰中，可以只私密保密一把密鑰，稱為為私鑰私鑰；另一把公開，叫做；另一把公開，叫做公鑰公鑰，就解決了，就解決了密鑰交換難題。密鑰交換難題。 N個用戶的系統(tǒng)，雖然每個用戶需要各自建個用戶的系統(tǒng)，雖然每個用戶需要各自建立一對公鑰與私鑰，但網(wǎng)絡(luò)管理員只須保管立一對公鑰與私鑰，但網(wǎng)絡(luò)管理員

30、只須保管（不必隱藏）（不必隱藏）N把公鑰，私鑰由用戶個人保把公鑰，私鑰由用戶個人保管，也解除了網(wǎng)管的負(fù)擔(dān)。管，也解除了網(wǎng)管的負(fù)擔(dān)。 點(diǎn)擊此處添加標(biāo)題文字用于保密功能用于認(rèn)證功能發(fā)信人用發(fā)信人用收信人的公鑰收信人的公鑰加密加密，收信人用自己的收信人用自己的私鑰解密私鑰解密。其他人因沒。其他人因沒有密文所要求的私鑰而有密文所要求的私鑰而不能解密。不能解密。發(fā)信人用自己的私鑰加發(fā)信人用自己的私鑰加密，收信人用發(fā)信人的密，收信人用發(fā)信人的公鑰解密公鑰解密，只要能解譯，只要能解譯密文，就表明這個密文密文，就表明這個密文是掌握私鑰的那個人發(fā)是掌握私鑰的那個人發(fā)出，別人做不出這樣的出，別人做不出這樣的密文。

31、密文。3. 從功能上講：由單純保密功能到保密認(rèn)證雙重功能 37基于公開密鑰的加密過程38 每個用戶擁有自己的密鑰對每個用戶擁有自己的密鑰對(KP , KS) 公鑰公鑰KP公開公開, 私鑰私鑰KS保密；保密； 當(dāng)當(dāng)AB通信時，用通信時，用B的公鑰的公鑰KPB加密加密: C=EKPB(M) B收密信后，用自己私鑰收密信后，用自己私鑰KSB解密解密: DKSB(C)= DKSB(EKPB(M)=M用公鑰密碼實(shí)現(xiàn)保密用公鑰密碼實(shí)現(xiàn)保密39基于公開密鑰的認(rèn)證過程40用公鑰密碼實(shí)現(xiàn)認(rèn)證 A為了向別人表明所發(fā)信息是自己的，應(yīng)當(dāng)用自己為了向別人表明所發(fā)信息是自己的，應(yīng)當(dāng)用自己私鑰私鑰KSA加密信息加密信息:

32、C=DKSA(M) 凡是拿到凡是拿到A的公鑰的公鑰KPA的人都可以解密這個信息：的人都可以解密這個信息： EKPA(C)=EKPA(DKSA(M)=M 由此表明此信息是由此表明此信息是A所簽發(fā)。所簽發(fā)。而而B進(jìn)行雙重解進(jìn)行雙重解密密: EKPA(DKSB(Z)=M如果如果A 只想讓只想讓B驗(yàn)證所發(fā)信息，驗(yàn)證所發(fā)信息，應(yīng)雙重加密應(yīng)雙重加密:Z= EKPB(DKSA(M)用公鑰密碼實(shí)現(xiàn)認(rèn)證和加密小結(jié)小結(jié) 公鑰密碼體制的出現(xiàn)，解決了對稱密碼體制很公鑰密碼體制的出現(xiàn)，解決了對稱密碼體制很難解決的一些問題，主要體現(xiàn)三個方面：難解決的一些問題，主要體現(xiàn)三個方面： 密鑰分發(fā)問題密鑰分發(fā)問題 密鑰管理問題密鑰

33、管理問題 數(shù)字簽名問題數(shù)字簽名問題 42435.2.2公開密鑰體制的構(gòu)建公開密鑰體制的構(gòu)建單鑰制密碼體系中，單鑰制密碼體系中，解密使用的密鑰與加密密鑰解密使用的密鑰與加密密鑰相同；能加密的人就能解密。因而又稱為相同；能加密的人就能解密。因而又稱為對稱密對稱密鑰制鑰制。而公鑰密碼體系中，加密與解密使用的密鑰不同，而公鑰密碼體系中，加密與解密使用的密鑰不同，并且無法從一把密鑰推導(dǎo)出另一把密鑰；故又稱并且無法從一把密鑰推導(dǎo)出另一把密鑰；故又稱為為非對稱密鑰制非對稱密鑰制。44單鑰制密碼體系中，解密是加密的逆運(yùn)算，數(shù)學(xué)單鑰制密碼體系中，解密是加密的逆運(yùn)算，數(shù)學(xué)上兩個算法互為反函數(shù)；上兩個算法互為反函數(shù)

34、；而公鑰密碼體系中，加密算法的反函數(shù)應(yīng)當(dāng)是不而公鑰密碼體系中，加密算法的反函數(shù)應(yīng)當(dāng)是不可行的。可行的?？梢姌?gòu)建公鑰密碼體系，需要找到除了反函數(shù)之可見構(gòu)建公鑰密碼體系，需要找到除了反函數(shù)之外的另外一種逆運(yùn)算方法。外的另外一種逆運(yùn)算方法。這個方法的實(shí)現(xiàn)還需要使用不同于加密算法的另這個方法的實(shí)現(xiàn)還需要使用不同于加密算法的另外一把密鑰。外一把密鑰。數(shù)學(xué)上是否存在這樣的算法？數(shù)學(xué)上是否存在這樣的算法？45單向陷門函數(shù)（one way trapdoor function ） 單向陷門函數(shù)是滿足下列條件的函數(shù)單向陷門函數(shù)是滿足下列條件的函數(shù)f(x)：(1) 給定給定x，計算，計算y=f(x)是容易的；是容易

35、的；(加密可行加密可行)(2) 給定給定y, 計算計算x=f -1(y)是不可行的是不可行的; (安全有保障安全有保障)(3) 對給定的任何對給定的任何y，還存在另一種計算，還存在另一種計算x 的方法的方法 xgk(y)，在已知，在已知 k 的情況下完成計算是容易的的情況下完成計算是容易的. k 就是密鑰。就是密鑰。(合法用戶得以解密合法用戶得以解密)46 而逆運(yùn)算即求而逆運(yùn)算即求 的整數(shù)解十分復(fù)的整數(shù)解十分復(fù)雜。表明它是單向函數(shù)，逆運(yùn)算不可行。雜。表明它是單向函數(shù)，逆運(yùn)算不可行。 對于已知密鑰對于已知密鑰 d 的人，還存在另一種計算的人，還存在另一種計算 m 的方的方法：法： m=c d (

36、mod n) RSA的安全性在于攻擊者用逆運(yùn)算求解不可行，由的安全性在于攻擊者用逆運(yùn)算求解不可行，由公鑰公鑰e和和n出發(fā)計算私鑰出發(fā)計算私鑰d 也是不可行的。（指計算也是不可行的。（指計算 復(fù)雜到不可行的程度）復(fù)雜到不可行的程度） RSA就是一種單向陷門函數(shù)就是一種單向陷門函數(shù). .計算計算c=me (mod n)是容易的。是容易的。(mod)emcn47 RSA公鑰密碼體制公鑰密碼體制 安全性基于大整數(shù)的素分解問題的安全性；安全性基于大整數(shù)的素分解問題的安全性；ElGamal公鑰密碼體制公鑰密碼體制 安全性基于有限域上的離散對數(shù)問題的困難性；安全性基于有限域上的離散對數(shù)問題的困難性；Mene

37、zes-Vanstone公鑰密碼體制公鑰密碼體制 安全性基于橢圓曲線上的離散對數(shù)問題的困難性；安全性基于橢圓曲線上的離散對數(shù)問題的困難性；目前大部分的公鑰密碼體制都是基于這三類問題，已經(jīng)提目前大部分的公鑰密碼體制都是基于這三類問題，已經(jīng)提出的許多公鑰密碼學(xué)的標(biāo)準(zhǔn)，譬如出的許多公鑰密碼學(xué)的標(biāo)準(zhǔn)，譬如IEEE P1363等，也大都等，也大都建立在這三類問題之上。建立在這三類問題之上。485.2.3 現(xiàn)代密碼學(xué)的新理念現(xiàn)代密碼學(xué)的新理念 1. 1. 從基于算法的神秘性到基于算法的復(fù)雜性從基于算法的神秘性到基于算法的復(fù)雜性 傳統(tǒng)的保密觀念，寄托安全性于某種鮮為人知的奇妙算法傳統(tǒng)的保密觀念，寄托安全性于

38、某種鮮為人知的奇妙算法上。其安全是暫時的，僥幸的，脆弱的。上。其安全是暫時的，僥幸的，脆弱的。 現(xiàn)代密碼學(xué)基于算法的復(fù)雜性，現(xiàn)代密碼學(xué)基于算法的復(fù)雜性，不靠神奇靠麻煩不靠神奇靠麻煩。其安全其安全是牢固的，可信的，科學(xué)的。是牢固的，可信的，科學(xué)的。 從基于算法的神秘性到基于算法的復(fù)雜性是現(xiàn)代密碼學(xué)設(shè)從基于算法的神秘性到基于算法的復(fù)雜性是現(xiàn)代密碼學(xué)設(shè)計理念上一次重大轉(zhuǎn)變。密文能否被破譯的關(guān)鍵不再是從計理念上一次重大轉(zhuǎn)變。密文能否被破譯的關(guān)鍵不再是從密文中提取信息有無可能性，而是從密文中提取信息有無密文中提取信息有無可能性，而是從密文中提取信息有無可行性?？尚行?。492.2.算法可公開性算法可公開性

39、 由于算法失去了保密價值，算法可以公開，讓它在攻由于算法失去了保密價值，算法可以公開，讓它在攻擊中不斷改進(jìn)和完善，并以此顯示其安全的堅(jiān)固性。擊中不斷改進(jìn)和完善，并以此顯示其安全的堅(jiān)固性。 算法公開了，合法用戶與非法用戶的區(qū)別在那里呢？算法公開了，合法用戶與非法用戶的區(qū)別在那里呢？ 合法用戶擁有密鑰，解譯密文十分容易；非法用戶沒合法用戶擁有密鑰，解譯密文十分容易；非法用戶沒有密鑰，破譯密文談何容易；有密鑰，破譯密文談何容易；不藏算法藏密鑰不藏算法藏密鑰是設(shè)計是設(shè)計理念上一致的觀點(diǎn)。理念上一致的觀點(diǎn)。 503 3 安全的相對性安全的相對性 當(dāng)然，應(yīng)充分估計破譯者的計算能力和計算技術(shù)當(dāng)然，應(yīng)充分估計

40、破譯者的計算能力和計算技術(shù)未來的發(fā)展，從這個意義講，破譯只是時間和金未來的發(fā)展，從這個意義講，破譯只是時間和金錢的問題。錢的問題。 如果破譯工作所花的代價大于秘密本身的價值，如果破譯工作所花的代價大于秘密本身的價值，或破譯花費(fèi)的時間大于秘密的有效期，則破譯失或破譯花費(fèi)的時間大于秘密的有效期，則破譯失去意義，而該保密系統(tǒng)就可以認(rèn)為是安全的。這去意義，而該保密系統(tǒng)就可以認(rèn)為是安全的。這才是實(shí)事求是的科學(xué)的保密觀和破譯觀。才是實(shí)事求是的科學(xué)的保密觀和破譯觀。不保絕不保絕對保相對對保相對是密碼設(shè)計理念上的又一個轉(zhuǎn)變。是密碼設(shè)計理念上的又一個轉(zhuǎn)變。 比較比較 公鑰密碼體制與對稱密碼體制相比公鑰密碼體制與

41、對稱密碼體制相比： 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 密鑰的分發(fā)相對容易；密鑰的分發(fā)相對容易； 密鑰管理簡單；密鑰管理簡單； 可以有效地實(shí)現(xiàn)數(shù)字簽名?？梢杂行У貙?shí)現(xiàn)數(shù)字簽名。 缺點(diǎn)：缺點(diǎn)： 與對稱密碼體制相比，加解密速度比較慢；與對稱密碼體制相比，加解密速度比較慢； 同等安全強(qiáng)度下，要求的密鑰位數(shù)要多一些；同等安全強(qiáng)度下，要求的密鑰位數(shù)要多一些； 密文的長度往往大于明文長度。密文的長度往往大于明文長度。51521.公開密鑰體制的新理念： (1)(1)系統(tǒng)安全基于計算復(fù)雜性，算法可以公開。系統(tǒng)安全基于計算復(fù)雜性，算法可以公開。 (2)(2)加密解密使用非對程的雙密鑰，一把可以公開。加密解密使用非對程的雙密鑰，一把可

42、以公開。 (3)(3)科學(xué)的可靠的系統(tǒng)設(shè)計思想。科學(xué)的可靠的系統(tǒng)設(shè)計思想。2.公鑰密碼的功能： (1)(1)用于保密：用接收方的公鑰加密，私鑰解密。用于保密：用接收方的公鑰加密，私鑰解密。 (2)(2)用于認(rèn)證：用發(fā)送方的私鑰加密，公鑰驗(yàn)證。用于認(rèn)證：用發(fā)送方的私鑰加密，公鑰驗(yàn)證。3.RSA公鑰密碼的原理與方法： (1) (1) 系統(tǒng)搭建：系統(tǒng)搭建：n=pq, (n)=(p-1)(q-1), de=1 mod (n) (2)(2)加、解密方法：加、解密方法：c=me mod n, m=cd mod n內(nèi)容要點(diǎn)（小結(jié)）內(nèi)容要點(diǎn)（小結(jié)）5253提提 綱綱公公鑰鑰密密碼碼體制體制概概述述公鑰密碼體制

43、的特點(diǎn)公鑰密碼體制的特點(diǎn)密密鑰鑰分配分配與與管理管理123 53545.3密鑰分配方案密鑰分配方案 要使要使常規(guī)加密常規(guī)加密有效地進(jìn)行，信息交互的雙方必須共享有效地進(jìn)行，信息交互的雙方必須共享一個密鑰，并且這個密鑰還要防止被其他人獲得。一個密鑰，并且這個密鑰還要防止被其他人獲得。 要使要使公開加密公開加密有效地進(jìn)行，信息接收的一方必須發(fā)布有效地進(jìn)行，信息接收的一方必須發(fā)布其公開密鑰，同時要防止其私有密鑰被其他人獲得。其公開密鑰，同時要防止其私有密鑰被其他人獲得。 密鑰還需密鑰還需經(jīng)常更換經(jīng)常更換，以便在攻擊者知道密鑰的情況下，以便在攻擊者知道密鑰的情況下使得泄漏的數(shù)據(jù)量最小化。對于通信的雙方使

44、得泄漏的數(shù)據(jù)量最小化。對于通信的雙方A和和B，密密鑰的分配可以有以下的幾種方法：鑰的分配可以有以下的幾種方法：55密鑰分配的四種方法密鑰分配的四種方法(1)密鑰可以由密鑰可以由A選定，然后通過選定，然后通過物理的方法物理的方法安全地傳遞給安全地傳遞給B。(2) 密鑰可以由可信任的第三方密鑰可以由可信任的第三方C選定，然后通過選定，然后通過物理的方法物理的方法安全地傳安全地傳遞給遞給A和和B。 (3) 如果如果A和和B都有一個到可信任的第三方都有一個到可信任的第三方C的的加密連接加密連接，那，那么么C就可以通過加密連接將密鑰安全地傳遞給就可以通過加密連接將密鑰安全地傳遞給A和和B。 采用的是采用

45、的是密鑰分配中心技術(shù)密鑰分配中心技術(shù)，可信任的第三方，可信任的第三方C就是密鑰就是密鑰分配中心分配中心 KDC (key distribute center) ，常常用于常規(guī)加密常常用于常規(guī)加密密鑰的分配。密鑰的分配。上述方法由于需要對密鑰進(jìn)行上述方法由于需要對密鑰進(jìn)行人工傳遞人工傳遞，對于大量連接的現(xiàn)代通信而，對于大量連接的現(xiàn)代通信而言，顯然不適用。言，顯然不適用。56(4) 如果如果A和和B都在可信任的第三方發(fā)布自己的公開密鑰，都在可信任的第三方發(fā)布自己的公開密鑰，那么它們都可以用彼此的公開密鑰加密進(jìn)行通信。那么它們都可以用彼此的公開密鑰加密進(jìn)行通信。 采用的是密鑰認(rèn)證中心技術(shù)，可信任的第

46、三方采用的是密鑰認(rèn)證中心技術(shù)，可信任的第三方C就是證就是證書授權(quán)中心書授權(quán)中心 C A (certificate authority)C A (certificate authority)，更多用更多用于公開加密密鑰的分配。于公開加密密鑰的分配。主要講主要講(3) KDC (4) CA方式方式575.3.1常規(guī)加密密鑰的分配常規(guī)加密密鑰的分配1. 集中式密鑰分配方案集中式密鑰分配方案 由一個中心節(jié)點(diǎn)或者由一組節(jié)點(diǎn)組成層次結(jié)構(gòu)負(fù)責(zé)由一個中心節(jié)點(diǎn)或者由一組節(jié)點(diǎn)組成層次結(jié)構(gòu)負(fù)責(zé)密鑰的產(chǎn)生并分配給通信的雙方，在這種方式下，用密鑰的產(chǎn)生并分配給通信的雙方，在這種方式下，用戶不需要保存大量的會話密鑰，只需

47、要保存同中心節(jié)戶不需要保存大量的會話密鑰，只需要保存同中心節(jié)點(diǎn)的加密密鑰，用于安全傳送點(diǎn)的加密密鑰，用于安全傳送由中心節(jié)點(diǎn)產(chǎn)生的即將由中心節(jié)點(diǎn)產(chǎn)生的即將用于與第三方通信的會話密鑰用于與第三方通信的會話密鑰。這種方式缺點(diǎn)是通信。這種方式缺點(diǎn)是通信量大，同時需要較好的鑒別功能以鑒別中心節(jié)點(diǎn)和通量大，同時需要較好的鑒別功能以鑒別中心節(jié)點(diǎn)和通信方。信方。 目前這方面的主流技術(shù)是目前這方面的主流技術(shù)是密鑰分配中心密鑰分配中心KDC技術(shù)。技術(shù)。58 其中的第三方通常其中的第三方通常是一個負(fù)責(zé)為用戶分配密鑰的密鑰分是一個負(fù)責(zé)為用戶分配密鑰的密鑰分配中心配中心(KDC)。 這時每一用戶必須和密鑰分配中心有一個

48、共享密鑰，稱這時每一用戶必須和密鑰分配中心有一個共享密鑰，稱為為主密鑰。（可通過第二種方法）主密鑰。（可通過第二種方法） 通過主密鑰分配給一對用戶的密鑰通過主密鑰分配給一對用戶的密鑰Ks稱為會話密鑰稱為會話密鑰，用，用于這一對用戶之間的保密通信。于這一對用戶之間的保密通信。 通信完成后，會話密鑰即被銷毀通信完成后，會話密鑰即被銷毀。如上所述，如果用戶。如上所述，如果用戶數(shù)為數(shù)為n，則會話密鑰數(shù)為，則會話密鑰數(shù)為n(n-1)/2。但主密鑰數(shù)卻只需。但主密鑰數(shù)卻只需n個，所以個，所以主密鑰可通過物理手段發(fā)送主密鑰可通過物理手段發(fā)送。59密鑰分配中心密鑰分配中心KDC的密鑰分配方案的密鑰分配方案(1

49、) AKDC：IDA | IDB | N1(2) KDC A ：EKA Ks | IDA| IDB |N1|EKbKs|IDA(3) AB： EKBKs|IDA(4) BA： EKsN2(5) A B： EKsf(N2)60 實(shí)際上，到第實(shí)際上，到第(3)步已經(jīng)完成步已經(jīng)完成密鑰的分配密鑰的分配過程，通過程，通信的雙方已經(jīng)共享了當(dāng)前的會話密鑰信的雙方已經(jīng)共享了當(dāng)前的會話密鑰Ks，第第(4)步步和第和第(5)步完成的是步完成的是鑒別功能鑒別功能。 第第2項(xiàng)項(xiàng)N1， Nonce 現(xiàn)時，現(xiàn)時，是這次業(yè)務(wù)的惟一識別是這次業(yè)務(wù)的惟一識別符符N1，稱，稱N1為一次性隨機(jī)數(shù)，可以是時戳、計數(shù)器為一次性隨機(jī)數(shù)

50、，可以是時戳、計數(shù)器或隨機(jī)數(shù)或隨機(jī)數(shù) 每次的每次的N1都應(yīng)不同，且為防止假冒，都應(yīng)不同，且為防止假冒，應(yīng)使敵手對應(yīng)使敵手對N1難以猜測難以猜測。因此用隨機(jī)數(shù)作為這個識別符最為。因此用隨機(jī)數(shù)作為這個識別符最為合適。合適。61問題問題單個密鑰分配中心單個密鑰分配中心KDC無法支持大型的通信網(wǎng)絡(luò)。每無法支持大型的通信網(wǎng)絡(luò)。每兩個可能要進(jìn)行安全通信的終端都必須同某個密鑰分兩個可能要進(jìn)行安全通信的終端都必須同某個密鑰分配中心共享主密鑰。當(dāng)通信的終端數(shù)量很大時，將出配中心共享主密鑰。當(dāng)通信的終端數(shù)量很大時，將出現(xiàn)這樣的情況：現(xiàn)這樣的情況：每個終端都要同許多密鑰分配中心共享主密鑰，增加了終每個終端都要同許多

51、密鑰分配中心共享主密鑰，增加了終端的成本和人工分發(fā)密鑰分配中心和終端共享的主密鑰的端的成本和人工分發(fā)密鑰分配中心和終端共享的主密鑰的成本。成本。需要幾個特別大的密鑰分配中心，每個密鑰分配中心都同需要幾個特別大的密鑰分配中心，每個密鑰分配中心都同幾乎所有終端共享主密鑰。然而各個單位往往希望自己來幾乎所有終端共享主密鑰。然而各個單位往往希望自己來選擇或建立自己的密鑰分配中心。選擇或建立自己的密鑰分配中心。62解決辦法解決辦法 網(wǎng)絡(luò)中如果用戶數(shù)目非常多且分布的地域非常廣，則使用網(wǎng)絡(luò)中如果用戶數(shù)目非常多且分布的地域非常廣，則使用多個多個KDC的分層結(jié)構(gòu)的分層結(jié)構(gòu): 在每個小范圍（如一個在每個小范圍（如

52、一個LAN或一個建筑物）內(nèi)，都建立一個本或一個建筑物）內(nèi)，都建立一個本地地KDC。同一范圍的用戶在進(jìn)行保密通信時，由本地。同一范圍的用戶在進(jìn)行保密通信時，由本地KDC為他為他們分配密鑰們分配密鑰; 如果兩個不同范圍的用戶想獲得共享密鑰，則可通過各自的本如果兩個不同范圍的用戶想獲得共享密鑰，則可通過各自的本地地KDC，而兩個本地，而兩個本地KDC的溝通又需經(jīng)過一個全局的溝通又需經(jīng)過一個全局KDC。這樣。這樣就建立了兩層就建立了兩層KDC; 根據(jù)網(wǎng)絡(luò)中用戶的數(shù)目及分布的地域，可建立根據(jù)網(wǎng)絡(luò)中用戶的數(shù)目及分布的地域，可建立3層或多層層或多層KDC. 分層結(jié)構(gòu)可減少主密鑰的分布，因?yàn)榇蠖鄶?shù)主密鑰是在本

53、分層結(jié)構(gòu)可減少主密鑰的分布，因?yàn)榇蠖鄶?shù)主密鑰是在本地地KDC和本地用戶之間共享。和本地用戶之間共享。 分層結(jié)構(gòu)還可將虛假分層結(jié)構(gòu)還可將虛假KDC的危害限制到一個局部區(qū)域，但的危害限制到一個局部區(qū)域，但 會降低信任度。會降低信任度。632. 無中心的密鑰控制無中心的密鑰控制 用密鑰分配中心為用戶分配密鑰時，用密鑰分配中心為用戶分配密鑰時，要求所有用戶要求所有用戶都信任都信任KDC，同時，同時還要求對還要求對KDC加以保護(hù)加以保護(hù)。如果密。如果密鑰的分配是無中心的，則不必有以上兩個要求鑰的分配是無中心的，則不必有以上兩個要求 然而如果每個用戶都能和自己想與之建立聯(lián)系的另一用然而如果每個用戶都能和自

54、己想與之建立聯(lián)系的另一用戶安全地通信，則對有戶安全地通信，則對有n個用戶的網(wǎng)絡(luò)來說，主密鑰應(yīng)多個用戶的網(wǎng)絡(luò)來說，主密鑰應(yīng)多達(dá)達(dá)n(n-1)/2個。個。 當(dāng)當(dāng)n很大時，這種方案無實(shí)用價值很大時，這種方案無實(shí)用價值; 但但在整個網(wǎng)絡(luò)的局部范圍卻非常有用在整個網(wǎng)絡(luò)的局部范圍卻非常有用.64發(fā)起方響應(yīng)方（1）（2）（3）1.AB：IDa|N1 無中心的密鑰分配時，兩個用戶無中心的密鑰分配時，兩個用戶A和和B建立會話密鑰需經(jīng)過建立會話密鑰需經(jīng)過以下以下3步：步： A向向B發(fā)出建立會話密鑰的請求和一個一次性隨機(jī)數(shù)發(fā)出建立會話密鑰的請求和一個一次性隨機(jī)數(shù)N1 B用與用與A共享的主密鑰共享的主密鑰MKm對應(yīng)答

55、的消息加密，并發(fā)送給對應(yīng)答的消息加密，并發(fā)送給A 應(yīng)答的消息中有應(yīng)答的消息中有B選取的會話密鑰選取的會話密鑰KS、B的身份的身份IDb、f(N1)和另一和另一個一次性隨機(jī)數(shù)個一次性隨機(jī)數(shù)N2 A使用新建立的會話密鑰使用新建立的會話密鑰KS對對f(N2)加密后返回給加密后返回給B2.BA：EMKmKs|IDa|IDb|f(N1)|N23.AB：EKsf(N2)優(yōu)點(diǎn)：每個通信方都優(yōu)點(diǎn)：每個通信方都必須保存多達(dá)必須保存多達(dá)(n一一1)個主密鑰，但是需要個主密鑰，但是需要多少會話密鑰就可以多少會話密鑰就可以產(chǎn)生多少。產(chǎn)生多少。655.3.2公鑰加密體制的密鑰管理公鑰加密體制的密鑰管理 密鑰可根據(jù)其不同

56、用途分為會話密鑰和主密鑰兩種類密鑰可根據(jù)其不同用途分為會話密鑰和主密鑰兩種類型型 會話密鑰會話密鑰又稱為數(shù)據(jù)加密密鑰又稱為數(shù)據(jù)加密密鑰 主密鑰主密鑰又稱為密鑰加密密鑰又稱為密鑰加密密鑰 由于密鑰用途不同，對密鑰的使用方式也希望加以某種控由于密鑰用途不同，對密鑰的使用方式也希望加以某種控制制 如果主密鑰泄露了，則相應(yīng)的會話密鑰也將泄露，因如果主密鑰泄露了，則相應(yīng)的會話密鑰也將泄露，因此主密鑰的安全性應(yīng)高于會話密鑰的安全性此主密鑰的安全性應(yīng)高于會話密鑰的安全性 一般在密鑰分配中心以及終端系統(tǒng)中主密鑰都是物理上安一般在密鑰分配中心以及終端系統(tǒng)中主密鑰都是物理上安全的全的 如果把主密鑰當(dāng)作會話密鑰注入

57、加密設(shè)備，那么其安全性如果把主密鑰當(dāng)作會話密鑰注入加密設(shè)備，那么其安全性則降低則降低66 本節(jié)介紹兩方面內(nèi)容：本節(jié)介紹兩方面內(nèi)容： 一是公鑰密碼體制所用的一是公鑰密碼體制所用的公開密鑰的分配公開密鑰的分配 二是如何用公鑰體制來二是如何用公鑰體制來分配單鑰密碼體制所分配單鑰密碼體制所需的密鑰需的密鑰 這是公鑰加密的一個主要用途這是公鑰加密的一個主要用途PGP介紹 PGP：全名：全名：Pretty Good Privacy，一種混合加密算，一種混合加密算法（綜合了對稱加密算法法（綜合了對稱加密算法IDEA，非對稱加密算法，非對稱加密算法RSA，MD5、以及偽隨機(jī)數(shù)產(chǎn)生器等）。通常只理解、以及偽隨機(jī)

58、數(shù)產(chǎn)生器等）。通常只理解為是為是PGP公司的系列軟件。能對郵件、文件、文件夾公司的系列軟件。能對郵件、文件、文件夾、整個硬盤加密，全網(wǎng)段加密權(quán)限和訪問權(quán)限控制等、整個硬盤加密，全網(wǎng)段加密權(quán)限和訪問權(quán)限控制等。PGP的使用 加密時加密時：PGP用的是用的是RSA和傳統(tǒng)加密的雜合算法，因?yàn)楹蛡鹘y(tǒng)加密的雜合算法，因?yàn)镽SA算算法計算量極大在速度上不適合加密大量數(shù)據(jù)，所以法計算量極大在速度上不適合加密大量數(shù)據(jù)，所以PGP用來加用來加密信息的不是密信息的不是RSA，而是對稱加密算法，而是對稱加密算法IDEA 。 數(shù)字簽名：數(shù)字簽名：PGP還可以只簽名而不加密，這適用于公開發(fā)表聲還可以只簽名而不加密，這適

59、用于公開發(fā)表聲明時，聲明人為了證實(shí)自己的身份，可以用自己的私鑰簽名。明時，聲明人為了證實(shí)自己的身份，可以用自己的私鑰簽名。 PGP 通過單向散列算法通過單向散列算法MD5(message digest 5)對郵件處理，對郵件處理，生成一個生成一個128位的二進(jìn)制數(shù)作為位的二進(jìn)制數(shù)作為“郵件文摘郵件文摘” ，一旦郵件有任，一旦郵件有任何改變這個何改變這個digest都會變化，那么這個數(shù)加上作者的名字（實(shí)都會變化，那么這個數(shù)加上作者的名字（實(shí)際上在作者的密匙里）還有日期等等，就可以作為一個簽名。際上在作者的密匙里）還有日期等等，就可以作為一個簽名。 數(shù)字簽名和認(rèn)證數(shù)字簽名和認(rèn)證：甲用自己的私鑰將上

60、述的：甲用自己的私鑰將上述的128位的摘要加密位的摘要加密，附加在郵件上，再用乙的公鑰將整個郵件加密。乙收到這份，附加在郵件上，再用乙的公鑰將整個郵件加密。乙收到這份密文以后，乙用自己的私鑰將郵件解密，得到甲的原文和簽名密文以后，乙用自己的私鑰將郵件解密，得到甲的原文和簽名，乙的，乙的PGP也從原文計算出一個也從原文計算出一個128位的摘要，再與用甲的公位的摘要，再與用甲的公鑰解密簽名得到的數(shù)比較，如果符合就說明這份郵件確實(shí)是甲鑰解密簽名得到的數(shù)比較，如果符合就說明這份郵件確實(shí)是甲寄來的。這樣既實(shí)現(xiàn)了保密又實(shí)現(xiàn)了認(rèn)證。寄來的。這樣既實(shí)現(xiàn)了保密又實(shí)現(xiàn)了認(rèn)證。 691. 公開密鑰的公開宣布公開密鑰