2011網(wǎng)絡(luò)安全與對(duì)抗(第二章密碼學(xué)理論)-1

1、第二章 密碼學(xué)理論密碼技術(shù)在網(wǎng)絡(luò)安全中的作用信息竊取信息傳遞信息冒充信息篡改信息抵賴加密技術(shù)完整性技術(shù)認(rèn)證技術(shù)數(shù)字簽名主要內(nèi)容2.1 密碼學(xué)基本知識(shí)2.2.1 古典密碼體制2.2.2 對(duì)稱密碼技術(shù)2.2.3 公鑰密碼技術(shù)2.2.4 報(bào)文鑒別和HASH函數(shù)2.2.5 數(shù)字簽名2.2 密碼學(xué)基本技術(shù)2.1 密碼學(xué)基礎(chǔ)知識(shí)2.1.1 密碼學(xué)發(fā)展歷史2.1.2 密碼學(xué)的基本概念2.1.3 密碼體制的分類2.1.4 密碼分析學(xué)2.1.5 密碼體制的安全性2.1 密碼學(xué)基礎(chǔ)知識(shí)2.1.1 密碼學(xué)發(fā)展歷史2.1.2 密碼學(xué)的基本概念2.1.3 密碼體制的分類2.1.4 密碼分析學(xué)2.1.5 密碼體制的安全性

2、2.1.1 密碼學(xué)發(fā)展歷史古典密碼時(shí)期近代密碼時(shí)期現(xiàn)代密碼時(shí)期密碼學(xué)發(fā)展大致分為三個(gè)階段：古典密碼時(shí)期起始時(shí)間：從古代到19世紀(jì)末，長(zhǎng)達(dá) 幾千年密碼體制：紙、筆或者簡(jiǎn)單器械實(shí)現(xiàn)的替代及換位通信手段：信使隱寫術(shù)（古希臘:公元前440年）舉例： 王先生： 來(lái)信收到，盛情難以 報(bào)答，我 已在昨天到達(dá)廣州。秋雨綿綿，每 天需備傘才能上街，苦矣。大約本 月中旬返鄉(xiāng)，到時(shí)再聯(lián)絡(luò)。 Scytale（斯巴達(dá):公元前400年）黑幫行話、藏頭詩(shī)、網(wǎng)格式密碼等舉例： 王先生： 來(lái)信收到，盛情難以 報(bào)答，我 已在昨天到達(dá)廣州。秋雨綿綿，每 天需備傘才能上街，苦矣。大約本 月中旬返鄉(xiāng)，到時(shí)再聯(lián)絡(luò)。 建立一張表，使每一個(gè)

3、字符對(duì)應(yīng)一對(duì),， 是該字符所在行標(biāo)號(hào)，是列標(biāo)號(hào)。這樣 將明文變成形式為一串?dāng)?shù)字的密文。 1 2345 1 A BCDE 2 F GHI JK 3 L MNOP 4 Q RSTU 5 V WXYZ棋盤密碼近代密碼時(shí)期起始時(shí)間：從20世紀(jì)初到20世紀(jì)50年代，即一戰(zhàn)及二戰(zhàn)時(shí)期密碼體制：手工或電動(dòng)機(jī)械實(shí)現(xiàn)的復(fù)雜的替代及換位（單表、多表、轉(zhuǎn)輪密碼等）通信手段：電報(bào)通信現(xiàn)代密碼時(shí)期起始時(shí)間：從20世紀(jì)50年代至今密碼體制：分組密碼、序列密碼以及公開(kāi)密鑰密碼，有堅(jiān)實(shí)的數(shù)學(xué)理論基礎(chǔ)通信手段：無(wú)線通信、有線通信、計(jì)算網(wǎng)絡(luò)等現(xiàn)代密碼學(xué)的重要事件1949年，Shannon發(fā)表了保密通信的信息理論，首先用信息論的觀

4、點(diǎn)對(duì)信息保密問(wèn)題作了全面的論述，為密碼系統(tǒng)建立了理論基礎(chǔ)，從此密碼學(xué)成了一門科學(xué)。1977年，美國(guó)國(guó)家標(biāo)準(zhǔn)局公布實(shí)施了數(shù)據(jù)加密標(biāo)準(zhǔn)（DES），公開(kāi)其加密算法，批準(zhǔn)用于非機(jī)密單位和商業(yè)上的保密通信。DES的公布使密碼學(xué)的研究公開(kāi)，密碼學(xué)得到了迅速發(fā)展。（第一次飛躍）1976年，Diffie和Hellman提出公開(kāi)密鑰的密碼體制，保密通信問(wèn)題得到廣泛研究。研究領(lǐng)域擴(kuò)展到數(shù)字簽名、消息認(rèn)證、身份識(shí)別、抗欺騙協(xié)議等。1978年,由Rivest、Shamire和Adleman 提出第一個(gè)比較完善的公鑰密碼體制算法RSA。1984年，C.H.Bennett和G.Brassard首次提出量子密碼技術(shù)（現(xiàn)稱為

5、BB84協(xié)議），它是一種基于量子定律的密碼技術(shù)，可以發(fā)現(xiàn)竊聽(tīng)，抗擊具有無(wú)限計(jì)算能力的攻擊。1989年，R.Mathews等首次將混沌理論用于序列密碼中，為序列密碼的研究開(kāi)辟了一條新的途徑。（第二次飛躍）1997年,美國(guó)國(guó)家標(biāo)準(zhǔn)局征集高級(jí)加密加密標(biāo)準(zhǔn)（AES），選擇比利時(shí)密碼學(xué)家設(shè)計(jì)Rijndael算法作為標(biāo)準(zhǔn)草案。公鑰密碼領(lǐng)域中，橢圓曲線由于安全性高、計(jì)算速度快引起人們的普遍關(guān)注。1991年,美國(guó)國(guó)家標(biāo)準(zhǔn)局制定數(shù)字簽名標(biāo)準(zhǔn)，1995年，又制定安全Hash算法。未來(lái)，混沌密碼、量子密碼逐步走向?qū)嵱没?.1.2 密碼學(xué)的基本概念密碼編碼學(xué)(Cryptography): 主要研究對(duì)信息進(jìn)行編碼,實(shí)

6、現(xiàn)對(duì)信息的加密或認(rèn)證等要求。密碼分析學(xué)(Cryptanalytics):主要研究加密消息的破譯或消息的偽造。這兩個(gè)分支既相互對(duì)立又相互依存，正是由于這種對(duì)立統(tǒng)一關(guān)系，才推動(dòng)了密碼學(xué)自身的發(fā)展。密碼學(xué)（Cryptology）是結(jié)合數(shù)學(xué)、計(jì)算機(jī)科學(xué)、電子與通訊等諸多學(xué)科于一體的交叉學(xué)科，是研究信息系統(tǒng)安全保密的一門科學(xué)。加密通信模型密碼系統(tǒng)（體制）五元組（M,C,K,E,D)滿足條件:明文（Plaintext）空間M：所有可能明文的集合密文（Ciphertext)空間C：所有可能密文的集合密鑰（Key）空間K：所有可能密鑰的集合,k=(ke,kd)加密（Encryption）算法: 所有 集合，

7、任意ke,有一個(gè)加密算法，使得eke(M)=C 解密（Decryption）算法:所有 集合， 任意kd,有一個(gè)解密算法，使得dkd(C)=M，且滿足dkd(eke(M)=M。Kerchhoff假設(shè) 這是現(xiàn)代密碼學(xué)中針對(duì)信息保密的一個(gè)重要的假設(shè)：這意味著算法細(xì)節(jié)可以公開(kāi)，甚至可以當(dāng)成一個(gè)標(biāo)準(zhǔn)加以公布。 算法難以改變,同一算法要使用很長(zhǎng)一段時(shí)間 沒(méi)人為兩個(gè)用戶建立一個(gè)密碼系統(tǒng) 防止設(shè)計(jì)者竊密 公開(kāi)的算法更安全假設(shè)敵手知道使用的密碼算法，即 密碼體制的安全性在于密鑰!一個(gè)密碼系統(tǒng)要實(shí)際可用，必須滿足如下特性：（1）加密和解密過(guò)程都能有效的計(jì)算； （2）破譯者取得密文后將不能在有效的時(shí)間內(nèi)破譯密鑰和

8、明文。具體加密的手段有硬件加密和軟件加密。 硬件加密的效率和安全性高，但硬件設(shè)備需要專用件，成本較高； 軟件加密的優(yōu)點(diǎn)是使用靈活、成本低，但安全性一般不如硬件高。注：一個(gè)密碼系統(tǒng)是安全的必要條件是窮舉搜索密鑰不可行，即密鑰空間足夠大。2.1.3 密碼體制的分類 按對(duì)明文的劃分（加密的方式）分為： 分組密碼： 把明文分成等長(zhǎng)的組分別加密 流密碼 按字符和位處理按密鑰對(duì)密碼體制的分類對(duì)稱密碼體制（Symmetric System） 加密密鑰和解密密鑰相同，或者雖然不相同，但由其中的任意一個(gè)可以很容易地推出另一個(gè)，又稱傳統(tǒng)密碼體制、秘密密鑰體制或單密鑰體制。 非對(duì)稱密碼體制（Asymmetric S

9、ystem） 加密密鑰和解密密鑰不相同，且從一個(gè)很難推出另一 個(gè)，其中加密密鑰可以公開(kāi)，成為公開(kāi)密鑰(pulic key)，簡(jiǎn)稱公鑰；解密密鑰保密,成為私人密鑰 （private key）,簡(jiǎn)稱私鑰。因此又稱公開(kāi)密鑰體制或 雙密鑰體制。 對(duì)稱密碼體制對(duì)稱密碼體制主要研究問(wèn)題：密鑰產(chǎn)生(Key generation)密鑰管理(Key management)分類：流密碼(Stream cipher)分組密碼(Block cipher)對(duì)稱密碼體制不僅可用于數(shù)據(jù)加密，也可用于消息的認(rèn)證。非對(duì)稱密碼體制（公鑰密碼體制）每個(gè)用戶都有一對(duì)選定的密鑰(公鑰k1；私鑰k2)，公開(kāi)的密鑰k1可以像電話號(hào)碼一樣進(jìn)

10、行注冊(cè)公布無(wú)需事先分配密鑰，加密和解密能力分開(kāi)可以實(shí)現(xiàn)多個(gè)用戶加密的消息只能由一個(gè)用戶解讀（用于公共網(wǎng)絡(luò)中實(shí)現(xiàn)保密通信）只能由一個(gè)用戶加密消息而使多個(gè)用戶可以解讀（可用于認(rèn)證系統(tǒng)中對(duì)消息進(jìn)行數(shù)字簽名）2.1.4 密碼分析學(xué) 密碼分析學(xué)：研究如何分析或破解各種密碼編碼體制的一門科學(xué)。 根據(jù)攻擊者擁有的信息分為以下4類： 唯密文攻擊 （ciphertextonly attack） 已知明文攻擊（knownplaintext attack） 選擇明文攻擊（chosenplaintext attack） 選擇密文攻擊（chosenciphertext attack）唯密文攻擊 密碼破譯者除了擁有截獲的

11、密文，以及對(duì)密碼體制和密文信息的一般了解外，沒(méi)有什么其它可以利用的信息用于破譯密碼。在這種情況下進(jìn)行密碼破譯是最困難的，經(jīng)不起這種攻擊的密碼體制被認(rèn)為是完全不保密的。已知明文攻擊密碼破譯者不僅掌握了相當(dāng)數(shù)量的密文，還有一些已知的明-密文對(duì)（通過(guò)各種手段得到的）可供利用?，F(xiàn)代的密碼體制（基本要求）不僅要經(jīng)受得住唯密文攻擊，而且要經(jīng)受得住已知明文攻擊。選擇明文攻擊 密碼破譯者不僅能夠獲得一定數(shù)量的明-密文對(duì)，還可以用它選擇的任何明文，在同一未知密鑰的情況下能加密相應(yīng)的密文。 密碼破譯者暫時(shí)控制加密機(jī)。選擇密文攻擊密碼破譯者能選擇不同的被加密的密文，并還可得到對(duì)應(yīng)的解密的明文，據(jù)此破譯密鑰及其它密文

12、。 密碼破譯者暫時(shí)控制解密機(jī)。破譯算法的分類（遞減）全部破譯 密碼分析者找到密鑰Key。全盤推導(dǎo) 密碼分析者找到一個(gè)代替算法A，在不知道密鑰Key的情況下，等價(jià)于Dkey(C)=P。實(shí)例（或局部）推導(dǎo) 密碼分析者從截獲的密文中找出明文。信息推導(dǎo) 密碼分析者獲得一些有關(guān)密鑰或明文的信息。這些信息可能是密鑰的幾個(gè)位、有關(guān)明文格式的信息等。 攻擊密碼方法窮舉破譯法統(tǒng)計(jì)分析法數(shù)學(xué)分析法 窮舉破譯法 對(duì)截收的密文依次用各種可能的密鑰試譯，直到得到有意義的明文；或在不變密鑰下，對(duì)所有可能的明文加密直到得到與截獲密報(bào)一致為止，此法又稱為完全試湊法(Complete trial-and-error Metho

13、d)。只要有足夠多的計(jì)算時(shí)間和存儲(chǔ)容量，原則上窮舉法總是可以成功的。但實(shí)際中，任何一種能保障安全要求的實(shí)用密碼都通過(guò)增大密鑰量和加大解密算法的復(fù)雜度來(lái)使這一方法在實(shí)際上是不可行的。 統(tǒng)計(jì)分析法 利用明文的已知統(tǒng)計(jì)規(guī)律進(jìn)行破譯的方法。密碼破譯者對(duì)截收的密文進(jìn)行統(tǒng)計(jì)分析，總結(jié)出其間的統(tǒng)計(jì)規(guī)律，并與明文的統(tǒng)計(jì)規(guī)律進(jìn)行對(duì)照比較，從中提取出明文和密文之間的對(duì)應(yīng)或變換信息。 密碼設(shè)計(jì)者可使明文的統(tǒng)計(jì)特性不帶入到密文中來(lái)對(duì)抗統(tǒng)計(jì)分析攻擊。 數(shù)學(xué)分析法針對(duì)密碼算法的所使用的數(shù)學(xué)依據(jù)通過(guò)數(shù)學(xué)求解的方法來(lái)破譯。密碼算法的設(shè)計(jì)者通過(guò)構(gòu)造數(shù)學(xué)難題來(lái)抵御分析攻擊。2.1.5 密碼體制的安全性 無(wú)條件安全 計(jì)算上安全 可

14、證明安全無(wú)條件安全又稱為絕對(duì)不可破譯不論提供的密文有多少，密文中所包含的信息都不足以惟一地確定其對(duì)應(yīng)的明文；具有無(wú)限計(jì)算資源（諸如時(shí)間、空間、資金和設(shè)備等）的密碼分析者也無(wú)法破譯某個(gè)密碼系統(tǒng)。計(jì)算上安全計(jì)算出和估計(jì)出破譯它的計(jì)算量下限，利用已有的最好的方法破譯該密碼系統(tǒng)所需要的努力超出了破譯者的破譯能力（諸如時(shí)間、空間、資金等資源）。 破譯算法的代價(jià)大于加密數(shù)據(jù)的價(jià)值 破譯算法所需的時(shí)間比數(shù)據(jù)保密的時(shí)間更長(zhǎng) 用同一密鑰加密的數(shù)據(jù)量比破譯算法需要的數(shù)據(jù)量少的多可證明的安全從理論上證明破譯它的計(jì)算量不低于解已知難題的計(jì)算量。注：是一種特殊的計(jì)算上的安全。密碼體制的基本原則密碼體制的安全性是依賴密鑰

15、的保密，而不是依賴于對(duì)加密算法的保密；加密和解密算法適用于密鑰空間中的所有元素；密碼體制既易于實(shí)現(xiàn)又便于使用。密碼體制是不可破的（理論上不可破，實(shí)際上不可破）；密鑰空間應(yīng)足夠大，使得試圖通過(guò)窮舉密鑰空間進(jìn)行搜索的方式在計(jì)算上不可行。2.2 密碼學(xué)基本技術(shù)2.2.1 古典密碼體制2.2.2 對(duì)稱密碼體制2.2.3 公鑰密碼體制2.2.4 報(bào)文鑒別和哈希函數(shù)2.2.5 數(shù)字簽名2.2 密碼學(xué)基本技術(shù)2.2.1 古典密碼體制2.2.2 對(duì)稱密碼體制2.2.3 公鑰密碼體制2.2.4 報(bào)文鑒別和哈希函數(shù)2.2.5 數(shù)字簽名2.2.1 古典密碼體制古典密碼體制是指那些比較簡(jiǎn)單的、大多數(shù)采用手工或機(jī)械操作

16、對(duì)明文進(jìn)行加密、對(duì)密文進(jìn)行解密的密碼體制。其技術(shù)、思想以及破譯方法雖然很簡(jiǎn)單，但是反映了密碼設(shè)計(jì)和破譯的思想，是學(xué)習(xí)密碼學(xué)的基本入口，對(duì)于理解、設(shè)計(jì)和分析現(xiàn)代密碼仍然具有借鑒的價(jià)值。兩個(gè)基本方法 置換（Permutation）:保持明文中所有字母不變，利用置換打亂明文字母的位置和次序，即在消息內(nèi)變換字母的位置。 代替（Substitution）:明文中每一個(gè)字符被替換成密文中的另外一個(gè)字符。接收者對(duì)密文進(jìn)行逆替換就恢復(fù)出明文來(lái)。1.置換密碼（permutation） (1)列置換加密 明文以固定的寬度水平寫出，密文按垂直方向讀出。 明文：COMPUTERSYSTEMSECURITY密文：CTS

17、ETOETCYMREUPSMRUYSI COMPU TERSY STEMS ECURI TY（2）雙重置換明文：attack at tomorrow密文：atkcmootowrrtata(3)周期置換加密 分組倒置 明文: This is not secure thi sis not sec ure 密文: ihtsistonceseru 2.代替密碼(subtitution) 單表代替密碼：將明文的一個(gè)字符用相應(yīng)的一個(gè)密文字符代替。 多表代替密碼：?jiǎn)蝹€(gè)明文字符可以映射成幾個(gè)密文字符之一，由多個(gè)單表代替密碼構(gòu)成，例如，可能有4個(gè)不同的簡(jiǎn)單代替密碼。例如A可能對(duì)應(yīng)于5、13、25或56，“B”可

18、能對(duì)應(yīng)于7、19、31或42，等等。 多字母代替密碼：字符塊被成組的加密，例如“ABA”可能對(duì)應(yīng)于“RTQ”，ABB可能對(duì)應(yīng)于“SLL”等。 單表密碼（愷撒密碼,乘積密碼,仿射密碼） 多表密碼(維吉尼亞） 多字母代換密碼 (希爾密碼）(1) 同余理論1)模運(yùn)算:即求余,記為mod（即5+10000除以7的余數(shù)）即：10000天后是星期二 2)同余定義:m正整數(shù),m除a,b余數(shù)同,稱 a,b為模m同余,記為a=b mod m例:假設(shè)今天是星期五，請(qǐng)問(wèn)10000天后是星期幾？3)同余滿足自反性、對(duì)稱性、傳遞性； a=a mod n； 若a=b mod n，則b=a mod n； 若a=b mod

19、n，b=c mod n，則a=c mod n4)所有與a同余的整數(shù)所組成的集合稱為a的同余類 所有同余類所形成的集合記為 5)同余的性質(zhì)：若a =b mod n， c =d mod n，則 （1）a+c=b+d mod n （2） ac=bd mod n(a mod n) +(b mod n)mod n=(a + b) mod n； - - * * 6)若ax mod n =1，則稱a與x對(duì)于模n互為逆元。 (用Euclid算法求乘法逆元) 例：152 mod 12=(3*3)mod 12=9注：若a和n互素，則a在模n下有逆元。(2)單表密碼1)愷撒密碼(加法密碼、移位密碼)明文 26個(gè)字母

20、密文 26個(gè)字母加密 Ek(m)=m+k=c mod n (n=26)當(dāng)k=3,每個(gè)字母使用其后第3個(gè)(循環(huán))代替明文 meet me after class密文 PHHW PH DIWHU FODVV解密 Dk(c)=c-k=m mod n密鑰量為n-1應(yīng)用同余性質(zhì)（1）2) 乘法密碼加密: c (m X k) mod n 解密: m (c X k-1) mod n 要求k和n互素 (n=26)Euler函數(shù)：(n)=與n互素的、小于n的正整數(shù)的個(gè)數(shù)，n1。 例：(3)= (4) = (6) =2，(5)=4，(7) =6 ,(12)=4 密鑰量為Euler函數(shù)(n)-1應(yīng)用同余性質(zhì)（2）以

21、及逆元的定義加密:選取k1，k2兩個(gè)參數(shù)，其中 k1 與 n 互素 c(k1m + k2)mod n解密: mk1-1 (c - k2)mod n (n=26)密鑰量為(n)-1)*(n-1)3) 仿射密碼4)單表代替密碼（單表置換）加密函數(shù):abcdefghijklmDKVQFIBJWPESCnopqrstuvwxyzXHTMYAUOLRGZN解密函數(shù): 明文: if we wish to replace letters密文: WI RF RWAJ UH YFTSDVF SFUUFYANOPQRSTUVWXYZzujdwlptcinryABCDEFGHIJKLMsgmakexofhbvq密鑰

22、量：26！ 1025（約109年，接近宇宙年齡1010年）明文中各個(gè)字母出現(xiàn)的統(tǒng)計(jì)概率字母組合概率雙字母組合：th、he、in、er三字母組合：the、ing、and單表代替無(wú)法抵御統(tǒng)計(jì)分析攻擊！(2) 多表密碼（維吉尼亞）多表密碼是利用多個(gè)單表代替密碼構(gòu)成的密碼體制。它在對(duì)明文進(jìn)行加密的過(guò)程中依照密鑰的指示輪流使用多個(gè)單表代替密碼。M=(m1,m2,mn) K=(k1,k2,kn) C=(c1,c2,cn)加密變換：ci=Eki(mi)=mi+ki mod n解密變換： mi=Dki(mi)=ci - ki mod nwearediscoveredeceptivedecepZICVTWQNG

23、RZGVTdsaveyourselftivedeceptiveWAVZHCQYGLMGJ(3)多字母代換密碼（希爾密碼）加密變換：cKm mod n解密變換：m=cK-1 mod n 其中c和m分別是密文(c1,c2,cn)和明文=(m1,m2,mn)向量，K是密鑰矩陣 c1k11 k12 k13 m1 c2 k21 k22 k32 m2 c3k31 k32 k33 m3即：c1 = k11*m1 + k12*m2 + k13*m3 mod n c2 = k21*m1 + k22*m2 + k32*m3 mod n c3 = k31*m1 + k32*m2 + k33*m3 mod n 注：矩

24、陣K得有逆KK-1=K-1K=I (K的行列式為非零)定理：k-1 存在等價(jià)于gcd|k|，261對(duì)于二階矩陣 ，|A|例： ，|A|=27=27*1=1mod 26,則 注：a+b=0 mod 26, 即 a=-b mod 26 Hill密碼舉例密匙產(chǎn)生：首先決定所用矩陣的大小，譬如是22, 其中E的行列式值detE必須與26互質(zhì)，否則不存在E的反矩陣。明文m=Hill 矩陣形態(tài)加密過(guò)程：密文c=pbwz 解密矩陣計(jì)算加密矩陣的反矩陣，再進(jìn)行模運(yùn)算（mod 26），得解密矩陣 解密過(guò)程 用唯密文攻擊法分析多字母代換密碼如Hill密碼是比較困難的。Hill密碼可抵抗頻率分析，不能抵抗已知明文攻

25、擊。 若得到n個(gè)不同的明密文對(duì)時(shí)，有明文：Friday , n=2密文：pocfkuHill密碼已知明文攻擊舉例2.2.2 對(duì)稱密碼體制對(duì)稱密碼算法有時(shí)又叫傳統(tǒng)密碼算法，就是加密密鑰和解密密鑰相同，或者能夠從一個(gè)密鑰中推算出來(lái)另一個(gè)密鑰。在大多數(shù)對(duì)稱算法中，加密解密密鑰是相同的。這些算法也叫秘密密鑰算法或單密鑰算法，它要求發(fā)送者和接收者在安全通信之前，商定一個(gè)密鑰。對(duì)稱算法的安全性依賴于密鑰，泄漏密鑰就意味著任何人都能對(duì)消息進(jìn)行加密解密。只要通信需要保密，密鑰就必須保密。 對(duì)稱密碼算法的分類序列密碼分組密碼1. 序列密碼序列密碼主要用于政府、軍事、外交等領(lǐng)域。序列密碼的加密過(guò)程是先把明文轉(zhuǎn)換成

26、二進(jìn)制序列，然后同密鑰序列進(jìn)行逐位加密生成密文序列發(fā)送給接收者。接收者用相同的密鑰序列對(duì)密文序列進(jìn)行逐位解密以恢復(fù)出明文序列。例：Aice欲將明文m=OK，加密成密文c，傳遞給Bob。假設(shè)密鑰為k=DA。加密：明文密鑰密文解密：密文密鑰明文表示XOR運(yùn)算序列密碼加解密框圖序列密碼特點(diǎn)安全強(qiáng)度取決于密鑰序列的隨機(jī)性和不可預(yù)測(cè)性，核心問(wèn)題是密鑰流生成器的設(shè)計(jì)。理論上能夠產(chǎn)生周期為2|K|-1-1的偽隨機(jī)序列，基于混沌理論產(chǎn)生的序列密碼具有良好的隨機(jī)性?？蓪?shí)現(xiàn)一次一密，達(dá)到理論上的安全性。加解密端的需要精確同步，不存在數(shù)據(jù)擴(kuò)展和錯(cuò)誤轉(zhuǎn)播。實(shí)時(shí)性好，運(yùn)算速度快，加密、解密易實(shí)現(xiàn)。目前流密鑰序列的產(chǎn)生大

27、多數(shù)是基于硬件的移位寄存器來(lái)實(shí)現(xiàn)，其結(jié)構(gòu)簡(jiǎn)單。2.分組密碼分組密碼（block cipher）是現(xiàn)代密碼學(xué)中的重要體制之一，也是應(yīng)用最為廣泛、影響最大的一種密碼體制。加密原理是將明文按照某一規(guī)定的n bit長(zhǎng)度分組（最后一組長(zhǎng)度不夠時(shí)要用規(guī)定的值填充，使其成為完整的一組），然后使用相同的密鑰對(duì)每一分組分別進(jìn)行加密。分組密碼框圖明文空間:0,1序列,為2n密文空間:0,1序列,為2m通常取m=n。若mn，則為有數(shù)據(jù)擴(kuò)展的分組密碼；若mn，則為有數(shù)據(jù)壓縮的分組密碼。加密變換:0,1,2, 2n-1上的一個(gè)置換,不同可逆變換的個(gè)數(shù)有2n!個(gè)。分組密碼算法要求 (1)分組長(zhǎng)度n足夠大。若分組太小,比如

28、只有8位,則和單表代替一樣.對(duì)于大的分組類似于多字母代替方法,能抵抗頻率分析。另外,使分組代換字母表中的元素個(gè)數(shù)2n足夠大，防止明文窮舉攻擊法奏效,目前長(zhǎng)度一般取128bit。（2）密鑰量足夠大。抵抗窮舉攻擊。但密鑰又不能過(guò)長(zhǎng)，以便于密鑰的管理,一般取128bit 。（3）密碼變換足夠復(fù)雜。使攻擊者除窮舉攻擊外，找不到其他快捷破譯方法。 (4)加密和解密運(yùn)算簡(jiǎn)單，易于軟件和硬件高速實(shí)現(xiàn)。如將分組n化分為子段，每段長(zhǎng)為8、16或者32，設(shè)計(jì)的算法采用規(guī)則的模塊結(jié)構(gòu)，如多輪迭代等，以便于軟件和VLSI快速實(shí)現(xiàn)。用軟件實(shí)現(xiàn)時(shí)，應(yīng)選用簡(jiǎn)單的運(yùn)算，使作用于子段上的密碼運(yùn)算易于以標(biāo)準(zhǔn)處理器的基本運(yùn)算，如加

29、、乘、移位等實(shí)現(xiàn)。用硬件實(shí)現(xiàn)，加密和解密過(guò)程之間的差別應(yīng)僅在于由秘密密鑰所生成的密鑰表不同而已。這樣，加密和解密就可用同一器件實(shí)現(xiàn)。分組密碼設(shè)計(jì)思想擴(kuò)散混亂擴(kuò)散所謂擴(kuò)散（diffusion），是指要將算法設(shè)計(jì)得使每一比特明文的變化盡可能多地影響到輸出密文序列的變化，以便隱蔽明文的統(tǒng)計(jì)特性；擴(kuò)散的另一層意思是將每一位密鑰的影響也盡可能迅速地?cái)U(kuò)展到較多的輸出密文比特中去。即擴(kuò)散的目的是希望密文中的任一比特都要盡可能與明文、密鑰相關(guān)聯(lián)，或者說(shuō)，明文和密鑰中任何一比特值得改變，都會(huì)在某種程度上影響到密文值的變化，以防止統(tǒng)計(jì)分析攻擊。擴(kuò)散的舉例說(shuō)明無(wú)擴(kuò)散技術(shù)的加密 p1:00000000 c1:0000

30、0010 p2:00000001 c2:00000011有擴(kuò)散技術(shù)的加密 p1:00000000 c1:01011010 p2:00000001 c2:11101011混亂所謂混亂(confusion)，是指在加密變換過(guò)程中是明文、密鑰以及密文之間的關(guān)系盡可能地復(fù)雜化，使得輸出是輸入的非線性函數(shù)。通過(guò)復(fù)雜的非線性代替法實(shí)現(xiàn)，以防密碼破譯者采用統(tǒng)計(jì)分析法進(jìn)行破譯攻擊?；靵y可以用“攪拌機(jī)”來(lái)形象地解釋，將一組明文和一組密文輸入到算法中，經(jīng)過(guò)充分混合，最后變成密文。同時(shí)要求，執(zhí)行這種“混亂”作業(yè)的每一步都必須是可逆的，即明文混亂以后能得到密文，反之，密文經(jīng)過(guò)逆向的混亂操作以后能恢復(fù)出明文。混亂的舉例

31、說(shuō)明典型的分組密碼結(jié)構(gòu):Feistel結(jié)構(gòu)(1973年）置換:代替過(guò)程完成后，再交換左、右兩半數(shù)據(jù)。乘積密碼:每輪結(jié)構(gòu)相同,但以不同的子密鑰Ki作為參數(shù)。代替:每輪中右半數(shù)據(jù)被作用于輪函數(shù)F后，再與左半數(shù)據(jù)進(jìn)行異或運(yùn)算。是Shannon提出的代替置換網(wǎng)絡(luò)（substitution-permutation network, SPN）的特有形式。特點(diǎn)是每次只處理明文的一半。算法說(shuō)明Ki：每級(jí)密鑰不同 Li-1LiRi-1Ri Li-1 f(Ri-1 , Ki) （a）加密加密：F(Li-1Ri-1)=LiRi Li= Ri-1 Ri= Li-1 f(Ri-1,Ki)Li-1LiRi-1Ri Ri

32、f(Ri-1 , Ki) （b）解密RiRi-1LiLi-1 Ri f(Li , Ki) （c）等效解密P=兩個(gè)子塊左右交換Li-1Ri-1=PFP(LiRi)解密：Li-1Ri-1=F-1(LiRi)Ri-1=LiLi-1 = Ri f(Li,Ki)加密：F(Li-1Ri-1)=LiRi Li= Ri-1 Ri= Li-1 f(Ri-1,Ki)Feistel算法要求 （1）分組長(zhǎng)度n足夠大。（2）密鑰量足夠大。（3）循環(huán)次數(shù)越多越安全。（4）輪函數(shù)變換足夠復(fù)雜。（5）子密鑰產(chǎn)生算法。（6）快速軟件實(shí)現(xiàn)。（4）算法容易分析，這樣可容易發(fā)現(xiàn)弱點(diǎn)，并給出對(duì)其的更高安全級(jí)別的保障措施。Feistel

33、結(jié)構(gòu)的加密和解密+K16+ K2+ K1+ K1+ K2+ K16L0R16L1R0R1L16L16R16R15L15R0L0數(shù)據(jù)加密標(biāo)準(zhǔn)DES DES（Data Encryption Standard）是對(duì)稱分組密碼體制典型代表。它于1977由美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所NIST在IBM公司的LUCIFER算法基礎(chǔ)上進(jìn)行修正制定而成。1981年，DES被美國(guó)商業(yè)組織所采納，作為美國(guó)國(guó)家標(biāo)準(zhǔn)數(shù)據(jù)加密算法。該算法很快被用于政府的機(jī)密性目的和金融工業(yè)界的完整性目的，并被廣泛地應(yīng)用于各個(gè)領(lǐng)域。 數(shù)據(jù)加密標(biāo)準(zhǔn)DES的特點(diǎn)分組加密算法：明文和密文為64位分組長(zhǎng)度。對(duì)稱算法：加密和解密除密鑰編排不同外，使用同一

34、算法。密鑰長(zhǎng)度：56位，但每個(gè)第8位為奇偶校驗(yàn)位，可忽略。密鑰可為任意的56位數(shù)，但存在弱密鑰，容易避開(kāi)。采用混亂和擴(kuò)散的組合，每個(gè)組合先替代后置換，共16輪。只使用了標(biāo)準(zhǔn)的算術(shù)和邏輯運(yùn)算，易于實(shí)現(xiàn)。DES加密算法框圖DES中的子密鑰的生成循環(huán)移位壓縮置換初始置換IP和初始逆置換IP-1 IP和IP-1直接置換DES的一輪迭代Li-1（32比特）Ri-1（32比特）Li（32比特）48比特寄存器選擇擴(kuò)展運(yùn)算E48比特寄存器子密鑰Ki（48比特）32比特寄存器選擇壓縮運(yùn)算S置換運(yùn)算PRi（32比特）Li=Ri-1擴(kuò)展置換-盒32位擴(kuò)展到48位加密函數(shù)f(Ri-1,Ki)壓縮替代S-盒48位壓縮到

35、32位共8個(gè)S盒S盒的規(guī)則S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8S-盒的輸入和輸出S盒是DES的最敏感部分，除此之外的計(jì)算都是線性的。S盒作為該密碼體制的非線性組件對(duì)安全性至關(guān)重要。其原理至今未公開(kāi)。美國(guó)國(guó)家安全局透露了S盒的幾條設(shè)計(jì)準(zhǔn)則：每行是015的一個(gè)排列,是列輸入的非線性函數(shù)。1 .所有的S盒都不是它輸入的線性仿射函數(shù)。就是沒(méi)有一個(gè)線性方程能將四個(gè)輸出比特表示成六個(gè)比特輸入的函數(shù)。2 .改變S盒的1位輸入，輸出至少改變2位。這意味著S盒是經(jīng)過(guò)精心設(shè)計(jì)的，它最大程度上增大了擴(kuò)散量。3 .S盒的任意一位輸入保持不變時(shí)，0 和1個(gè)數(shù)之差極小。即如果保持一位不變而改變

36、其它五位，那么其輸出0和1的個(gè)數(shù)不應(yīng)相差太多。置換p-盒的構(gòu)造DES性能 1） DES雪崩效應(yīng)：明文或密鑰的微小變化引起密文的較大變化.若變化太小,會(huì)導(dǎo)致減小待搜索明文和密鑰空間的大小。明文變化 密鑰變化 循環(huán) 不同比特個(gè)數(shù) 循環(huán)不同比特個(gè)數(shù) 01001612221214335328163416252)對(duì)稱性：3)存在弱密鑰(4個(gè))和半弱密鑰 (12個(gè))弱密鑰：半弱密鑰：4)運(yùn)算效率:硬件:數(shù)字設(shè)備公司DEC開(kāi)發(fā)DES芯片,加解密速度高達(dá)1GB/s,相當(dāng)于1560萬(wàn)組每秒.軟件:在IBM3090大型機(jī)可達(dá)到3.2萬(wàn)次每秒 DES算法的安全性分析1)窮舉攻擊 1997年開(kāi)始，RSA公司發(fā)起了一個(gè)

37、稱作“向DES挑戰(zhàn)”的競(jìng)技賽。1997年1月，用了96天時(shí)間，成功地破解了用DES加密的一段信息；一年之后，在第二屆賽事上，這一記錄41天 ；1998年7月， “第2-2屆DES挑戰(zhàn)賽（DES Challenge II-2）” 把破解DES的時(shí)間縮短到了只需56個(gè)小時(shí)； “第三屆DES挑戰(zhàn)賽（DES Challenge III）”把破解DES的時(shí)間縮短到了只需22.5小時(shí) 。這意味著隨著計(jì)算能力的增長(zhǎng)，必須相應(yīng)地增加密鑰的長(zhǎng)度。2）差分分析(1990,Biham和Shamir以色列) 選擇明文攻擊,通過(guò)分析特定明文對(duì)的差值對(duì)密文對(duì)差值的影響來(lái)獲得可能性最大的密鑰, 嘗試247次明文密文對(duì),在分

38、析過(guò)程中經(jīng)過(guò)237次DES運(yùn)算?？捎糜谠u(píng)估算法安全性。（對(duì)破譯17/18輪的DES所需時(shí)間與窮舉搜索大致相等，但對(duì)8輪DES只需幾分鐘）3）線性分析(1993,Mitsuru Matsui日本) 已知明文攻擊,通過(guò)選擇充分多的明文密文對(duì)，尋找一個(gè)明文密文密鑰之間近似的線性表達(dá)式來(lái)破解密鑰, 嘗試243次明文密文對(duì)。對(duì)DES更有效。1）二重DES （二個(gè)密鑰，有效長(zhǎng)度128-16=112位） 加密：C=Ek2Ek1(M) 解密：M=Dk1Dk2(C)對(duì)264個(gè)輸入分組，總映射個(gè)數(shù)為 ,另一方面，對(duì)每個(gè)不同的密鑰，DES都定義了一個(gè)映射，總映射數(shù)為2561017。因此，可假定用兩個(gè)不同的密鑰兩次使用DES，可得一個(gè)新映射，而且這一新映射不出現(xiàn)在單重DES定義的映射中。這一假定已于1992年被證明。DES的發(fā)展即二重DES產(chǎn)生的映射不會(huì)等價(jià)于單重DES加密。但二重DES存在稱為中途相遇攻擊的攻擊方案，這種攻擊不依賴于DES的任何特性，可用于攻擊任何分組密碼。如果有 ,那么若已知一個(gè)明文密文對(duì)(P,C)，首先，用256個(gè)所有可能的K1對(duì)P加密，將加密結(jié)果存入一表，然后用256個(gè)所有可能的K2對(duì)C解密，在上述表中查找與C解密結(jié)果相匹配的項(xiàng)，如果找