計算機網(wǎng)絡-密碼學簡介.ppt

1、第2章 密碼學,2,2020年8月6日星期四,參考文獻,W. Stallings（楊明等譯），編碼密碼學與網(wǎng)絡安全-原理與實踐，電子工業(yè)出版社。2001年4月。 Bruce Chneier, 應用密碼學，機械工業(yè)出版社，2000年1月。 馮登國，密碼分析學，清華大學出版社，2000年8月。 陳魯生，沈世鎰，現(xiàn)代密碼學，科學出版社，2002年7月。,3,2020/8/6,1. 基本概念術語,消息被稱為明文（plain text）。 用某種方法偽裝消息以隱藏它的內(nèi)容的過程稱為加密(encryption, encipher)。 加了密的消息稱為密文(cipher text)。 而把密文轉(zhuǎn)變?yōu)槊魑牡倪^

2、程稱為解密(decryption, decipher)。,4,2020/8/6,1. 基本概念術語,使消息保密的技術和科學叫做密碼編碼學(cryptography)。 從事此行的叫密碼編碼者（cryptographer）。 破譯密文的科學和技術叫做密碼分析學（cryptanalysis）。 從事密碼分析的專業(yè)人員叫做密碼分析者（cryptanalyst）。 密碼學包括密碼編碼學和密碼分析學兩者?，F(xiàn)代的密碼學家通常也是理論數(shù)學家。,5,2020/8/6,1. 基本概念密碼學的其它作用,鑒別 消息的接收者應該能夠確認消息的來源；入侵者不可能偽裝成他人。 完整性 消息的接收者應該能夠驗證在傳送過程中

3、消息沒有被修改；入侵者不可能用假消息代替合法消息。 抗抵賴 發(fā)送者事后不可能虛假地否認他發(fā)送的消息。,6,2020/8/6,1. 基本概念算法和密鑰,密碼算法也叫密碼，是用于加密和解密的數(shù)學函數(shù)。通常情況下，有兩個相關的函數(shù)：一個用作加密，另一個用作解密。 明文用M（消息），密文用C表示，加密函數(shù)E作用于M得到密文C，用數(shù)學表示為： E（M）=C. 相反地，解密函數(shù)D作用于C產(chǎn)生M D（C）=M. 先加密后再解密消息，原始的明文將恢復出來，下面的等式必須成立： D（E（M）=M,7,2020/8/6,1. 基本概念受限制的算法,如果算法的保密性是基于保持算法的秘密，這種算法稱為受限制的算法。

4、如果有人無意暴露了這個秘密，所有人都必須改變他們的算法。,8,2020/8/6,1. 基本概念現(xiàn)代密碼學,現(xiàn)代密碼學用密鑰解決了這個問題，密鑰用K表示。 密鑰K的可能值的范圍叫做密鑰空間。 加密和解密運算都使用這個密鑰，加/解密函數(shù)現(xiàn)在變成：,EK1（M）=C DK2（C）=M DK2（EK1（M）=M,EK（M）=C DK（C）=M DK（EK（M）=M,9,2020/8/6,10,2020/8/6,1. 基本概念對稱算法和非對稱算法,對稱算法 加密密鑰能夠從解密密鑰中推算出來，反過來也成立。 公開密鑰算法 公開密鑰算法用作加密的密鑰不同于用作解密的密鑰，而且解密密鑰不能根據(jù)加密密鑰計算出來

5、。,11,2020/8/6,1. 基本概念密碼分析,密碼分析學是在不知道密鑰的情況下?；謴统雒魑牡目茖W。 對密碼進行分析的嘗試稱為攻擊。 密碼分析的一個基本假設：密碼分析者已有密碼算法及其實現(xiàn)的全部詳細資料。在實際的密碼分析中并不總是有這些詳細信息的應該如此假設。如果其他人不能破譯算法，即便了解算法如何工作也是徒然，如果連算法的知識都沒有，那就肯定不可能破譯它。,12,2020/8/6,（1）唯密文攻擊,密碼分析者有一些消息的密文 這些消息都用同一加密算法加密 密碼分析者的任務是恢復盡可能多的明文 或者最好是能推算出加密消息的密鑰來 已知：C1=EK（P1），C2=EK（P2）， 推導出：P1

6、，P2，,13,2020/8/6,（2）已知明文攻擊,密碼分析者不僅可得到一些消息的密文，而且也知道這些消息的明文。 分析者的任務就是用加密信息推出用來加密的密鑰或?qū)С鲆粋€算法，此算法可以對用同一密鑰加密的任何新的消息進行解密。 已知：P1，C1=Ek（P1），P2，C2=Ek（P2），Pi，Ci=Ek（Pi） 推導出：密鑰k，或從Ci+1= Ek（Pi+1）推出Pi+1的算法。,14,2020/8/6,（3）選擇明文攻擊,分析者不僅可得到一些消息的密文和相應的明文，而且他們也可選擇被加密的明文。 這比已知明文攻擊更有效。因為密碼分析者能選擇特定的明文塊去加密，那些塊可能產(chǎn)生更多關于密鑰的信息

7、，分析者的任務是推出用來加密消息的密鑰或?qū)С鲆粋€算法，此算法可以對用同一密鑰加密的任何新的消息進行解密。,15,2020/8/6,（4）選擇密文攻擊,密碼分析者能選擇不同的被加密的密文，并可得到對應的解密的明文，例如密碼分析者存取一個防竄改的自動解密盒，密碼分析者的任務是推出密鑰。已知：C1，P1=Dk（C1），C2，P2=Dk（C2），Ci，Pi=Dk（Ci），推導出： k。,16,2020/8/6,（5）軟磨硬泡攻擊,密碼分析者威脅、勒索，或者折磨某人，直到他給出密鑰為止。行賄有時稱為購買密鑰攻擊。這些是非常有效的攻擊，并且經(jīng)常是破譯算法的最好途徑。,17,2020/8/6,最好的算法是那

8、些已經(jīng)公開的，并經(jīng)過世界上最好的密碼分析家們多年的攻擊，但還是不能破譯的算法。 美國國家安全局對外保持他們的算法的秘密，但他們有很好的密碼分析家在內(nèi)部工作，他們互相討論他們的算法，通過執(zhí)著的審查發(fā)現(xiàn)他們工作中的弱點。,18,2020/8/6,密碼分析者不是總能知道算法的。例如在二戰(zhàn)中美國人破譯日本人的外交密碼紫密（PURPLE）794就是例子，而且美國人一直在做這種事。如果算法用于商業(yè)安全程序中，那么拆開這個程序，把算法恢復出來只是時間和金錢問題。如果算法用于軍隊的通訊系統(tǒng)中，購買（或竊?。┻@種設備，進行逆向工程恢復算法也只是簡單的時間和金錢的問題。,19,2020/8/6,2. 古典密碼算法

9、,在計算機出現(xiàn)前，密碼學由基于字符的密碼算法構成。不同的密碼算法是字符之間互相代換或者是互相之間換位，好的密碼算法是結合這兩種方法，每次進行多次運算。 現(xiàn)在事情變得復雜多了，但原理還是沒變。重要的變化是算法對比特而不是對字母進行變換，實際上這只是字母表長度上的改變，從26個元素變?yōu)?個元素。大多數(shù)好的密碼算法仍然是代替和換位的元素組合。,20,2020/8/6,代替密碼,代替密碼就是明文中每一個字符被替換成密文中的另外一個字符。接收者對密文進行逆替換就恢復出明文來。 在經(jīng)典密碼學中，有四種類型的代替密碼 簡單代替密碼：就是明文的一個字符用相應的一個密文字符代替。報紙中的密報就是簡單的代替密碼。

10、 多名碼代替密碼 它與簡單代替密碼系統(tǒng)相似，唯一的不同是單個字符明文可以映射成密文的幾個字符之一，例如A可能對應于5、13、25或56，“B”可能對應于7、19、31或42，等等。,21,2020/8/6,多字母代替密碼 字符塊被成組加密，例如“ABA”可能對應于“RTQ”，ABB可能對應于“SLL”等。 多表代替密碼 由多個簡單的代替密碼構成，例如，可能有5個被使用的不同的簡單代替密碼，單獨的一個字符用來改變明文的每個字符的位置。,22,2020/8/6,簡單代替密碼,著名的凱撒密碼就是一種簡單的代替密碼，它的每一個明文字符都由其右邊第3個（模26）字符代替（A由D代替，B由E代替W由Z代替

11、X由A代替，Y由B代替，Z由C代替）。它實際上更簡單，因為密文字符是明文字符的環(huán)移，并且不是任意置換。 ABCDEFGHIJKLMNOPQRSTUVWXYZ DEFGHIJKLMNOPQRSTUVWXYZABC,23,2020/8/6,凱撒密碼僅有25個可能的密鑰，非常不安全。 但是英文的明文有一個特點，不同的英文字母在文章中出現(xiàn)的頻率不同。,24,2020/8/6,字母頻率表,25,2020/8/6,單表代替密碼的缺點,在單表代替下字母的頻度、重復字母模式、字母結合方式等統(tǒng)計特性除了字母名稱改變以外，都未發(fā)生變化，依靠這些不變的統(tǒng)計特性就能破譯單表代換；,26,2020/8/6,如果一個明文

12、字母可以任意一個密文字母代替，則有26！中不同的密鑰， 大約4*10 26密鑰，比的DES的256 =7.2*1016個密鑰大10個數(shù)量級。,27,2020/8/6,多表代替密碼,Vigenere密碼是由法國密碼學家Blaise de Vigenere于1858年提出的一種密碼，它是一種以移位代換為基礎的周期代換密碼。d個代換表f(f1，f2，fd)由d個字母序列給定的密鑰k(kl，k2，kd)ZdN決定，其中ki (i=1，2，d) 確定明文的第i+td個字母(t為正整數(shù))的移位次數(shù)。,28,2020/8/6,多表代替密碼的例子,例1 設d=6, k=cipher, 明文串: this cr

13、yptosystem is not secure m=(19,7,8,18,2,17,24,15,19,14,18,24,18,19,4,12,8,18,13,14,19,18,4,2,20,1,4)。 密鑰：k=(2,8,15,7,4,17),29,2020/8/6,密文串為：VPXZGIAXIVWPUBTTMJPWIZITWZT,30,2020/8/6,多表代替密碼的優(yōu)點,在多表代換下，原來明文中的統(tǒng)計特性通過多個表的平均作用而被隱蔽了起來。多表代換密碼的破譯要比單表代替密碼的破譯難得多。,31,2020/8/6,多表代替密碼的破解（1）,1863年，普魯士軍官F.Kasiski發(fā)明了通過

14、分析密文中的字母重復的情況來確定周期多表代替密碼的準確周期的方法。 例：密鑰：dog，明文：to be or not to be,32,2020/8/6,多表代替密碼的破解（2）,在密文中字符串wchh重復了兩次，其間個為9個字符。 這個距離是密鑰長度的倍數(shù)，可能的密鑰長度是1, 3, 9。 判定了長度之后就可以用頻率分析法來破譯各個單表代替密碼了。 多表代替密碼的破解的原因：密鑰的長度太短。,33,2020/8/6,密鑰長度的確定 設x=x1x2.xn, x的重合指數(shù)定義為x中兩個隨機字母相同的概率，記為Ic(x)。 我們期望Ic(x)=p1p2.p25=0.065。,34,2020/8/6

15、,密鑰字的確定 設x=x1x2.xn, y=y1y2.yn, x和y的重合互指數(shù)定義為x中的一個隨機字母等于y的一個隨機字母相同的概率，記為MIc(x)。 可以根據(jù)重合互指數(shù)分析出密鑰字。參見： 馮登國，密碼分析學，清華大學出版社，1.4節(jié)。,35,2020年8月6日星期四,Enigma,直到第一次世界大戰(zhàn)結束為止，所有密碼都是使用手工來編碼的，就是鉛筆加紙的方式。 考慮到不能多次重復同一 種明文到密文的轉(zhuǎn)換方式，和民用的電報編碼解碼不同，加密人員并不能把轉(zhuǎn)換方式牢記于心。轉(zhuǎn)換通常是采用查表的方法，所查表又每日不同，所以解碼速度極慢。,36,2020/8/6,Enigma(1),解密一方當時正

16、值春風得意之時，幾百年來被認為堅不可破的維吉耐爾(Vigenere)密碼和它的變種也被破解。 而無線電報的發(fā)明，使得截獲密文易如反掌。無論是軍事方面還是民用商業(yè)方面都需要一種可靠而又有效的方法來保證通訊的安全。,37,2020/8/6,Enigma(2),1918年，德國發(fā)明家亞瑟謝爾比烏斯(Arthur Scherbius)和他的朋友理查德里特(Richard Ritter)創(chuàng)辦了謝爾比烏斯和里特公司。這是一 家專營把新技術轉(zhuǎn)化為應用方面的企業(yè)，很象現(xiàn)在的高新技術公司。 謝爾比烏斯負責研究和開發(fā)方面，緊追 當時的新潮流。他的一個想 法就是要用二十世紀的電氣技術來取代那種過時的鉛筆加紙的加密方

17、 法。,38,2020/8/6,Enigma(3),謝爾比烏斯發(fā)明的加密電子機械名叫ENIGMA，在以后的年代里， 它將被證明是有史以來最為可靠的加密系統(tǒng)之一，而對這種可靠性的 盲目樂觀，又使它的使用者遭到了滅頂之災。,39,2020/8/6,Enigma(4),ENIGMA它可以被分解成相當簡單的幾部分。下 面的圖是它的最基本部分的示意圖，我們可以看見它的三個部分：鍵盤、轉(zhuǎn)子和顯示器。,40,2020/8/6,Enigma(5),41,2020/8/6,Enigma(6),照片左方是一個完整的轉(zhuǎn)子，右方是轉(zhuǎn)子的分解，我們可以看到安裝在轉(zhuǎn)子中的電線,42,2020/8/6,Enigma(7),

18、當?shù)?一個轉(zhuǎn)子轉(zhuǎn)動整整一圈以后，它上面有一個齒撥動第二個轉(zhuǎn)子，使得 它的方向轉(zhuǎn)動一個字母的位置。,43,2020/8/6,Enigma(7),在此基礎上謝爾比烏斯十分巧妙地在三個轉(zhuǎn)子的一端加上了一個 反射器，而把鍵盤和顯示器中的相同字母用電線連在一起。反射器和 轉(zhuǎn)子一樣，把某一個字母連在另一個字母上，但是它并不轉(zhuǎn)動。這么一個固定的反射器它并不增加可以使用的編 碼數(shù)目。它和解碼聯(lián)系起來了。,44,2020/8/6,Enigma(8),發(fā)信人首先要調(diào)節(jié)三個轉(zhuǎn) 子的方向，使它們處于26*26*26 = 17576個方向中的一個（事實上轉(zhuǎn)子的初始方向 就是密匙，這是收發(fā)雙方必須預先約定好的） 依次鍵入

19、明文， 并把閃亮的字母依次記下來(密文) 然后就可以把加密后的消息用比如電報 的方式發(fā)送出去。 當收信方收到電文后，使用一臺相同的ENIGMA， 按照原來的約定，把轉(zhuǎn)子的方向調(diào)整到和發(fā)信方相同的初始方向上； 依次鍵入收到的密文，并把閃亮的字母依次記下來，就得到了明文。,45,2020/8/6,Enigma(9),當然謝爾比烏斯還可以再多加轉(zhuǎn)子，但是我們看見每加一個轉(zhuǎn)子 初始方向的可能性只是乘以了26。尤其是，增加轉(zhuǎn)子會增加ENIGMA 的體積和成本。 謝爾比烏斯希望他的加密機器是便于攜帶的； 首先他把三個轉(zhuǎn)子做得可以拆卸下來互相交換，這樣一來初 始方向的可能性變成了原來的六倍。,46,2020

20、/8/6,Enigma(10),下一步謝爾比烏斯在鍵盤和第一轉(zhuǎn)子之間增加了一個連接板。這 塊連接板允許使用者用一根連線把某個字母和另一個字母連接起來， 這樣這個字母的信號在進入轉(zhuǎn)子之前就會轉(zhuǎn)變?yōu)榱硪粋€字母的信號。 這種連線最多可以有六根（后期的ENIGMA具有更多的連線），這樣 就可以使對字母的信號互換，其他沒有插上連線的字母保持不變。 當然連接板上的連線狀況也是收發(fā)信息的雙方需要預先約定的。 連接板上兩兩交換6對字母的可能性數(shù)目非常巨大，有 100391791500種 密鑰：1.連接板的連接：A/L-P/R-T/D-B/W-K/F-O/Y 2.轉(zhuǎn)子的順序：2,3,1 3.轉(zhuǎn)子的初始方向：Q-

21、C-W,47,2020/8/6,Enigma(11),調(diào)整好ENIGMA，現(xiàn)在操作員可以開始對明文加密了。但是我們看 到每天只有一個密鑰，如果這一天的幾百封電報都以這個密鑰加密發(fā) 送的話，暗中截聽信號的敵方就會取得大量的以同一密鑰加密的信息， 這對保密工作來說不是個好兆頭。我們記得在簡單替換密碼的情況下， 如果密碼分析專家能得到大量的密文，就可以使用統(tǒng)計方法將其破解。,48,2020/8/6,Enigma(12),盡管不知道對ENIGMA是否可以采用類似的統(tǒng)計方法，德國人還是 留了個心眼。他們決定在按當日密鑰調(diào)整好ENIGMA機后并不直接加密 要發(fā)送的明文。相反地，首先發(fā)送的是一個新的密鑰。連

22、接板的連線順 序和轉(zhuǎn)子的順序并不改變，和當日通用的密鑰相同；想反地，轉(zhuǎn)子的初 始方向?qū)⒈桓淖儭?操作員首先按照上面所說的方法按當日密鑰調(diào)整好 ENIGMA，然后隨機地選擇三個字母，比如說PGH。他把PGH在鍵盤上 連打兩遍，加密為比如說KIVBJE（注意到兩次PGH被加密為不同的形式， 第一次KIV，第二次BJE，這正是ENIGMA的特點，它是一種復式替換密 碼）。然后他把KIVBJE記在電文的最前面。接著他重新調(diào)整三個轉(zhuǎn)子的 初始方向到PGH，然后才正式對明文加密。,49,2020/8/6,Enigma(13),1929年1月，波茲南大學數(shù)學系主任茲德齊斯羅克里格羅夫斯基 (Zdzislaw

23、 Kryglowski)教授開列了一張系里最優(yōu)秀的數(shù)學家的名單，在這 張名單上，有以后被稱為密碼研究“波蘭三杰”的馬里安雷杰夫斯基 (Marian Rejewski)，杰爾茲羅佐基(Jerzy Rozycki)和亨里克佐加爾斯 基(Henryk Zygalski)。 雷杰夫斯基深知“重復乃密碼大敵”。在ENIGMA密碼中，最明顯 的重復莫過于每條電文最開始的那六個字母它由三個字母的密鑰 重復兩次加密而成。德國人沒有想到這里會是看似固若金湯的ENIGMA 防線的弱點。,50,2020/8/6,Enigma(14),漢斯提羅施密特(Hans-Thilo Schimdt) 于1888年出生在柏林的

24、一個中產(chǎn)階級家庭里，一次大戰(zhàn)時當過兵打過仗。根據(jù)凡爾賽條約， 戰(zhàn)敗后的德國進行了裁軍，施密特就在被裁之列。退了伍后他開了個 小肥皂廠，心想下海從商賺點錢。結果戰(zhàn)后的經(jīng)濟蕭條和通貨膨脹讓 他破了產(chǎn)。此時他不名一文，卻還有一個家要養(yǎng)。,51,2020/8/6,Enigma(15),魯?shù)婪蚪o他的二弟在密碼處(Chiffrierstelle)找了 個位置。這是專門負責德國密碼通訊的機構ENIGMA的指揮中心， 擁有大量絕密情報。 漢斯提羅把一家留在巴伐利亞，因為在那里生活 費用相對較低，勉強可以度日。就這樣他一個人孤零零地搬到了柏林， 拿著可憐的薪水，對大哥又羨又妒，對拋棄他的社會深惡痛絕。,52,2

25、020/8/6,Enigma(16),接下來的事情可想而知。如果把自己可以輕松搞到的絕密情報出 賣給外國情報機構，一方面可以賺取不少自己緊缺的錢，一方面可以 以此報復這個拋棄了他的國家。 1931年11月8日，施密特化名為艾斯克 (Asche)和法國情報人員在比利時接頭，在旅館里他向法國情報人員提 供了兩份珍貴的有關ENIGMA操作和轉(zhuǎn)子內(nèi)部線路的資料，得到一萬馬 克?？窟@兩份資料，盟國就完全可以復制出一臺軍用的ENIGMA機。,53,2020/8/6,Enigma(17),雷杰夫斯基每天都會收到一大堆截獲的德國電報，所以一天中可 以得到許多這樣的六個字母串，它們都由同一個當日密鑰加密而成。

26、比如說他收到四個電報，其中每封電報的開頭的六個字母為 1 2 3 4 5 6 第一封電報：L O K R G M 第二封電報：M V T X Z E 第三封電報：J K T M P E 第四封電報：D V Y P Z X,54,2020/8/6,Enigma(18),對于每封電報來說， 第一個字母和第四個字母 第二個字母和第五個字母 第三個字母和第六個字母 都是分別 由同一個字母加密而來。,55,2020/8/6,Enigma(19),第一個字母：ABCDEFGHIJKLMNOPQRSTUVWXYZ 第四個字母： _P_M_RX_ 如果雷杰夫斯基每天可以得到充分多的電報，他就可以把上面這 個關

27、系表補充完整 第一個字母：ABCDEFGHIJKLMNOPQRSTUVWXYZ 第四個字母：FQHPLWOGBMVRXUYCZITNJEASDK,56,2020/8/6,Enigma(20),雷杰夫斯基對這樣的 表格進行了仔細觀察。從字母A開始看，它被對應成F；而F在此表中 又被對應成W，接下去它被對應成A，我們又回到了最先開始的字母， 于是就有了一個循環(huán)的字母圈AFWA。 如果考慮所有的字母， 雷杰夫斯基就能寫出關于此對應表的所有的循環(huán)圈： AFWA3個字母的循環(huán)圈 BQZKVELRIB 9個字母的循環(huán)圈 CHGOYDPC7個字母的循環(huán)圈 JMXSTNUJ 7個字母的循環(huán)圈,57,2020/

28、8/6,Enigma(21),雖然這些循環(huán)圈是由當日密鑰，也就是轉(zhuǎn)子的位置，它 們的初始方向以及連接板上字母置換造成的，但是每組循環(huán)圈的 個數(shù)和每個循環(huán)圈的長度，卻僅僅是由轉(zhuǎn)子的位置和它們的初始 方向決定的，和連接板上字母交換的情況無關！,58,2020/8/6,Enigma(22),首先要取得足夠的當日電文來構 造字母對應表并且寫出字母循環(huán)圈； 然后根據(jù)循環(huán)圈的數(shù)目和它們的 長度從記錄表中檢索出相對應的轉(zhuǎn)子位置和初始方向； 這就是當日的 密鑰（連接板的情況還未知）。 循環(huán)圈的個數(shù)和長度可以看作是這個 密鑰的“指紋”通過建立密鑰“指紋”檔案，雷杰夫斯基就能及 時地把當天的密鑰找出來。,59,2

29、020/8/6,Enigma(23),每個密鑰僅對一個消息使用一次。發(fā)方對所發(fā)的消息加密，然后銷毀亂碼本中用過的一頁或用過的磁帶部分。收方有一個同樣的亂碼本，并依次使用亂碼本上的每個密鑰去解密密文的每個字符。收方在解密消息后銷毀亂碼本中用過的一頁或用過的磁帶部分。新的消息則用亂碼本的新的密鑰加密。,1.6 公開密鑰密碼學,61,2020/8/6,公開密鑰系統(tǒng)的的特性,加密和解密運算是計算上容易的問題，即應該屬于P類問題。 密碼分析應該屬于NP完全問題。,62,2020/8/6,RSA公開密鑰算法,63,2020/8/6,素數(shù),素數(shù)：只能被1和它本身整除的自然數(shù)；否則為合數(shù)。 每個合數(shù)都可以唯一

30、地分解出素數(shù)因子 6 = 2 3 999999 = 3337111337 27641 = 131121 從2 開始試驗每一個小于等于27641 的素數(shù)。,64,2020/8/6,素因子分解的速度,整數(shù)n的十進制位數(shù) 因子分解的運算次數(shù) 所需計算時間（每微秒一次） 501.4x10103.9小時 759.0 x1012104天 1002.3x101574年 2001.2x10233.8x109年 3001.5x10294.0 x1015年 5001.3x10394.2x1025年,65,2020/8/6,定義,RSA的密鑰 p和q是素數(shù) （秘密的） r = pq (r) = (p-1)(q-1)

31、 （秘密的） SK是秘密密鑰（解密密鑰） （秘密的） PK是公開密鑰（加密密鑰） X是明文 （秘密的） Y是密文 PK滿足：(PK, (r) )=1; SK滿足：SKPK = 1 mod (r) 同余 如果a和b都是整數(shù)，而m是一個固定的正整數(shù)，則當m能夠整除a-b時，稱a,b對模m同余，記為ab(mod m),66,2020/8/6,模運算及其性質(zhì),a (mod n) +b (mod n) mod n = (a+b) mod n a (mod n) -b (mod n) mod n = (a-b) mod n a (mod n) b (mod n) mod n = (a b) mod n 如

32、果a 與n互素，則存在b使得 a b = 1 mod n,67,2020/8/6,RSA 公開密鑰密碼算法,M是明文，n是一個大數(shù) 加密：C = M e mod n 解密：M = C d mod n =M ed mod n 條件： 能找到e,d,n使得對所有的M，當Mn時， M ed=M mod n 對所有的M，計算M e 和C d 的容易的。 給定e、n推導d是困難的。,68,2020/8/6,RSA 公開密鑰密碼算法（續(xù)）,p、q是素數(shù) 秘密地選擇 n = p q， 公開n 選擇e: e與(n)是互素的(n)=(p-1)(q-1)； 公開選擇 計算d, 使得ed=1 mod (n); 秘密

33、地計算 即：ed=1 +s(n); 根據(jù)歐拉定理的推廣 對于任意的m, 0 m n， m ed = m s (n)+1 m (mod n),69,2020/8/6,RSA 公開密鑰密碼算法（續(xù)）,公開密鑰(e,n) 秘密密鑰(d,n) 加密算法：me mod n = E(e,m) 解密算法：(me)d mod n = E(d, me) m= E(d, E(e,m) ) m= E(e, E(d,m) ),70,2020/8/6,例,例： n=15, p=3, q=5, (n)=8 生成密鑰對：令e=3, 則d=3, ( d e = 1 mod (n) ) 加密： 設M=7， C=7e mod n

34、 =73 mod 15= 13 解密： M= Cd mod n = 133 mod 15 = 7,71,2020/8/6,問題,如何計算 me mod n 如何判定一個給定的整數(shù)是素數(shù)？ 如何找到足夠大的素數(shù)p和q ?,72,2020/8/6,對RSA的攻擊方法,強力攻擊（窮舉法）：嘗試所有可能的私有密鑰 數(shù)學分析攻擊：各種數(shù)學方法，等價與兩個素數(shù)乘積的因子分解 時間性攻擊：取決于解密算法的運算時間,1.7 報文鑒別與散列函數(shù),74,2020/8/6,參考文獻,W. Stallings（楊明等譯），編碼密碼學與網(wǎng)絡安全-原理與實踐，電子工業(yè)出版社。2001年4月。,75,2020/8/6,內(nèi)容

35、,報文鑒別的基本概念； 散列函數(shù)； 密碼散列報文鑒別碼,1. 基本概念,77,2020/8/6,鑒別的需求,網(wǎng)絡通信環(huán)境中會受到下列攻擊 泄露; 加密 通信量分析：連接的頻率和持續(xù)的時間、報文數(shù)量等。 加密 偽裝：假源點; 報文鑒別 內(nèi)容篡改:修改內(nèi)容; 報文鑒別 序號篡改:增刪內(nèi)容; 報文鑒別 計時篡改：報文回放; 報文鑒別 抵賴：終點否認收到、源點否認發(fā)送過。數(shù)字簽名,78,2020/8/6,鑒別函數(shù),鑒別函數(shù)：用來產(chǎn)生用于鑒別一個報文的值：鑒別符。 鑒別符用于鑒別報文在通信過程中是否被篡改、刪除和修改等。 產(chǎn)生鑒別符的幾類函數(shù)： 報文加密 報文鑒別碼 散列函數(shù),79,2020/8/6,鑒

36、別函數(shù)-報文加密,對稱加密：以整個報文作為它的鑒別符號 提供保密：僅源點和終點共享K。 一定程度的鑒別：僅來自源點。 不提供簽名：接收人可以偽造、發(fā)送人可以否認。,E,M,M,D,K,K,Ek(M),80,2020/8/6,鑒別函數(shù)-報文加密,私鑰加密：以整個報文作為它的鑒別符號 提供鑒別和簽名：僅源點有私鑰KS。 任何一方都能用公開密鑰Kp脫密。,E,M,M,D,Ks,Kp,E Ks(M),81,2020/8/6,鑒別函數(shù)-報文加密,公開密鑰加密：以整個報文作為它的鑒別符號 提供報密：僅終點有脫密的私鑰KS。 不提供簽名：接收人可以偽造、發(fā)送人可以否認。,E,M,M,D,Kp,KS,E Kp(M),82,2020/8/6,鑒別函數(shù)-報文加密,對稱密鑰加密：以整個報文作為它的鑒別符號 提供保密： BKp 鑒別與簽名： AKs,E,M,M,D,AKs,BKs,E BKp(E AKs(M),E,BKp,A,B,D,AKp,83,2020/8/6,為什么需要報文鑒別,如果M是可執(zhí)行代碼、X光片,E,M,M,D,K,K,Y=Ek(M),ZEk(M),N,D,K,84,2020/8/6,差錯控制,外部差錯控制,內(nèi)部差錯控制,85,2020/8/6,鑒別函數(shù)-報文鑒別碼,報文鑒別Message Authe