計(jì)算機(jī)網(wǎng)絡(luò)-密碼學(xué)簡介.ppt

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

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

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

4、如果有人無意暴露了這個(gè)秘密，所有人都必須改變他們的算法。,8,2020/8/6,1. 基本概念現(xiàn)代密碼學(xué),現(xiàn)代密碼學(xué)用密鑰解決了這個(gè)問題，密鑰用K表示。 密鑰K的可能值的范圍叫做密鑰空間。 加密和解密運(yùn)算都使用這個(gè)密鑰，加/解密函數(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. 基本概念對(duì)稱算法和非對(duì)稱算法,對(duì)稱算法 加密密鑰能夠從解密密鑰中推算出來，反過來也成立。 公開密鑰算法 公開密鑰算法用作加密的密鑰不同于用作解密的密鑰，而且解密密鑰不能根據(jù)加密密鑰計(jì)算出來

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

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

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

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

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

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

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

12、字母可以任意一個(gè)密文字母代替，則有26！中不同的密鑰， 大約4*10 26密鑰，比的DES的256 =7.2*1016個(gè)密鑰大10個(gè)數(shù)量級(jí)。,27,2020/8/6,多表代替密碼,Vigenere密碼是由法國密碼學(xué)家Blaise de Vigenere于1858年提出的一種密碼，它是一種以移位代換為基礎(chǔ)的周期代換密碼。d個(gè)代換表f(f1，f2，fd)由d個(gè)字母序列給定的密鑰k(kl，k2，kd)ZdN決定，其中ki (i=1，2，d) 確定明文的第i+td個(gè)字母(t為正整數(shù))的移位次數(shù)。,28,2020/8/6,多表代替密碼的例子,例1 設(shè)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)點(diǎn),在多表代換下，原來明文中的統(tǒng)計(jì)特性通過多個(gè)表的平均作用而被隱蔽了起來。多表代換密碼的破譯要比單表代替密碼的破譯難得多。,31,2020/8/6,多表代替密碼的破解（1）,1863年，普魯士軍官F.Kasiski發(fā)明了通過

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

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

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

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

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

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

20、/8/6,Enigma(10),下一步謝爾比烏斯在鍵盤和第一轉(zhuǎn)子之間增加了一個(gè)連接板。這 塊連接板允許使用者用一根連線把某個(gè)字母和另一個(gè)字母連接起來， 這樣這個(gè)字母的信號(hào)在進(jìn)入轉(zhuǎn)子之前就會(huì)轉(zhuǎn)變?yōu)榱硪粋€(gè)字母的信號(hào)。 這種連線最多可以有六根（后期的ENIGMA具有更多的連線），這樣 就可以使對(duì)字母的信號(hào)互換，其他沒有插上連線的字母保持不變。 當(dāng)然連接板上的連線狀況也是收發(fā)信息的雙方需要預(yù)先約定的。 連接板上兩兩交換6對(duì)字母的可能性數(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)在操作員可以開始對(duì)明文加密了。但是我們看 到每天只有一個(gè)密鑰，如果這一天的幾百封電報(bào)都以這個(gè)密鑰加密發(fā) 送的話，暗中截聽信號(hào)的敵方就會(huì)取得大量的以同一密鑰加密的信息， 這對(duì)保密工作來說不是個(gè)好兆頭。我們記得在簡單替換密碼的情況下， 如果密碼分析專家能得到大量的密文，就可以使用統(tǒng)計(jì)方法將其破解。,48,2020/8/6,Enigma(12),盡管不知道對(duì)ENIGMA是否可以采用類似的統(tǒng)計(jì)方法，德國人還是 留了個(gè)心眼。他們決定在按當(dāng)日密鑰調(diào)整好ENIGMA機(jī)后并不直接加密 要發(fā)送的明文。相反地，首先發(fā)送的是一個(gè)新的密鑰。連

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

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

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

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

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

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

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

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

30、地分解出素?cái)?shù)因子 6 = 2 3 999999 = 3337111337 27641 = 131121 從2 開始試驗(yàn)每一個(gè)小于等于27641 的素?cái)?shù)。,64,2020/8/6,素因子分解的速度,整數(shù)n的十進(jìn)制位數(shù) 因子分解的運(yùn)算次數(shù) 所需計(jì)算時(shí)間（每微秒一次） 501.4x10103.9小時(shí) 759.0 x1012104天 1002.3x101574年 2001.2x10233.8x109年 3001.5x10294.0 x1015年 5001.3x10394.2x1025年,65,2020/8/6,定義,RSA的密鑰 p和q是素?cái)?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是一個(gè)固定的正整數(shù)，則當(dāng)m能夠整除a-b時(shí)，稱a,b對(duì)模m同余，記為ab(mod m),66,2020/8/6,模運(yùn)算及其性質(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是一個(gè)大數(shù) 加密：C = M e mod n 解密：M = C d mod n =M ed mod n 條件： 能找到e,d,n使得對(duì)所有的M，當(dāng)Mn時(shí)， M ed=M mod n 對(duì)所有的M，計(jì)算M e 和C d 的容易的。 給定e、n推導(dǎo)d是困難的。,68,2020/8/6,RSA 公開密鑰密碼算法（續(xù)）,p、q是素?cái)?shù) 秘密地選擇 n = p q， 公開n 選擇e: e與(n)是互素的(n)=(p-1)(q-1)； 公開選擇 計(jì)算d, 使得ed=1 mod (n); 秘密

33、地計(jì)算 即：ed=1 +s(n); 根據(jù)歐拉定理的推廣 對(duì)于任意的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 生成密鑰對(duì)：令e=3, 則d=3, ( d e = 1 mod (n) ) 加密： 設(shè)M=7， C=7e mod n

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

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

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