《密碼學(xué)》教案(很有價(jià)值)

《密碼學(xué)》教案張煥國，唐明，伍前紅武漢大學(xué)計(jì)算機(jī)學(xué)院教學(xué)目的本課程是計(jì)算機(jī)科學(xué)與技術(shù)、信息安全專業(yè)的專業(yè)選修課。開設(shè)本課程的目的是使學(xué)生了解并掌握計(jì)算機(jī)安全保密所涉及的基本理論和方法，具備保障信息安全的基本能力。教學(xué)要求通過講授、討論、實(shí)踐，使學(xué)生了解計(jì)算機(jī)安全的威脅、密碼學(xué)算法、安全技術(shù)的發(fā)展，熟悉計(jì)算機(jī)安全保密的基本概念、操作系統(tǒng)安全和網(wǎng)絡(luò)安全，掌握計(jì)算機(jī)密碼學(xué)的基本理論、基本方法、常見加密算法及其實(shí)現(xiàn)技術(shù)、應(yīng)用方法，重點(diǎn)掌握傳統(tǒng)加密算法、DES算法、AES算法、背包算法、RSA算法、ECC算法、DSA算法等。

第一講密碼學(xué)的基本概念一、信息安全學(xué)科概論1、信息安全學(xué)科建設(shè)2001年經(jīng)教育部批準(zhǔn)武漢大學(xué)創(chuàng)建了全國第一個(gè)信息安全本科專業(yè)；2007年全國信息安全本科專業(yè)已達(dá)70多所高校；2003年經(jīng)國務(wù)院學(xué)位辦批準(zhǔn)武漢大學(xué)建立信息安全碩士點(diǎn)、博士點(diǎn)、博士后流動(dòng)站2007年1月成立國家信息安全教指委2006年武漢大學(xué)信息安全專業(yè)獲湖北省“品牌專業(yè)”武漢大學(xué)成為我國信息安全科學(xué)研究和人才培養(yǎng)的重要基地。2、信息安全學(xué)科特點(diǎn)信息安全學(xué)科是交叉學(xué)科：計(jì)算機(jī)、通信、數(shù)學(xué)、物理、生物、管理、法律等；具有理論與實(shí)際相結(jié)合的特點(diǎn)；信息安全技術(shù)強(qiáng)調(diào)整體性、系統(tǒng)性、底層性；對(duì)信息安全來說，法律、管理、教育的作用很大，必須高度重視。人才是關(guān)鍵，人的綜合素質(zhì)是關(guān)鍵的關(guān)鍵！3、武漢大學(xué)的辦專業(yè)思路以學(xué)信息安全為主，兼學(xué)計(jì)算機(jī)、通信，同時(shí)加強(qiáng)數(shù)學(xué)、物理、法律等基礎(chǔ)，掌握信息安全的基本理論與技能，培養(yǎng)良好的品德素質(zhì)。二、信息安全的基本概念1、信息安全事關(guān)國家安全信息成為社會(huì)發(fā)展的重要戰(zhàn)略資源，信息技術(shù)改變著人們的生活和工作方式。信息產(chǎn)業(yè)成為新的經(jīng)濟(jì)增長點(diǎn)。社會(huì)的信息化已成為當(dāng)今世界發(fā)展的潮流。信息獲取、處理和安全保障能力成為綜合國力的重要組成部分。信息安全事關(guān)國家安全，事關(guān)社會(huì)穩(wěn)定。2、信息系統(tǒng)安全的概念 能源、材料、信息是支撐現(xiàn)代社會(huì)大廈的三根支柱。 信息是邏輯的、抽象的，不能脫離系統(tǒng)而獨(dú)立存在?、傩畔⑾到y(tǒng)安全包括四個(gè)層面信息系統(tǒng)安全＝設(shè)備安全＋數(shù)據(jù)安全＋內(nèi)容安全＋行為安全 簡稱信息系統(tǒng)安全為信息安全！②中文詞安全＝Security+Safety–中文安全的含義等于英文Security加上Safety的含義。–Security是指阻止人為的對(duì)安全的危害。–Safety是指阻止非人為的對(duì)安全的危害。③信息系統(tǒng)設(shè)備安全的概念信息系統(tǒng)設(shè)備的安全是信息系統(tǒng)安全的首要問題和基礎(chǔ)之一。三個(gè)側(cè)面：設(shè)備的穩(wěn)定性(Stability)，設(shè)備的可靠性(Reliability)，設(shè)備的可用性(Availabity)。設(shè)備：硬設(shè)備，軟設(shè)備④數(shù)據(jù)安全的概念I(lǐng)BM公司的定義：采取措施確保數(shù)據(jù)免受未授權(quán)的泄露、篡改和毀壞。–說明：這個(gè)定義明確了信息安全的三個(gè)側(cè)面：數(shù)據(jù)的秘密性(Secrecy)，數(shù)據(jù)的真實(shí)性(Authenticity)，數(shù)據(jù)的完整性(Integrity)。–這個(gè)定義還說明了，為了信息安全必須采取措施，必須付出代價(jià)，代價(jià)就是資源（時(shí)間和空間）。⑤內(nèi)容安全的概念內(nèi)容安全是信息安全在法律、政治、道德層次上的要求。政治上健康符合國家法律、法規(guī)符合中華民族道德規(guī)范⑥行為安全的概念行為安全是信息安全的終極目的。符合哲學(xué)上，實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)的原理。從過去的僅看身份，發(fā)展為既看身份更看行為。三個(gè)側(cè)面：行為的秘密性；行為的完整性；行為的可控性。3、信息安全措施◆信息安全措施＝{法律措施，教育措施，管理措施，技術(shù)措施，注意：決不能低估法律、教育、管理的作用，許多時(shí)候它們的作用大于技術(shù)。①信息安全的技術(shù)措施信息安全技術(shù)措施＝{硬件系統(tǒng)安全、操作系統(tǒng)安全、密碼技術(shù)、通信安全、網(wǎng)絡(luò)安全、數(shù)據(jù)庫安全、病毒防治技術(shù)，防電磁輻射技術(shù)，信息隱藏技術(shù)，數(shù)字資源保護(hù)技術(shù)，電子對(duì)抗技術(shù)，···}。注意：硬件結(jié)構(gòu)的安全和操作系統(tǒng)安全是基礎(chǔ)，密碼、網(wǎng)絡(luò)安全等是關(guān)鍵技術(shù)。②信息安全的管理措施信息安全管理措施既包括信息設(shè)備、機(jī)房的安全管理，又包括對(duì)人的安全管理，其中對(duì)人的管理是最主要的。目前，計(jì)算機(jī)網(wǎng)絡(luò)系統(tǒng)安全的最大威脅之一是缺少有效的計(jì)算機(jī)網(wǎng)絡(luò)安全監(jiān)管。③信息安全的法律措施信息安全措施包括各級(jí)政府關(guān)于信息安全的各種法律、法規(guī)。商用密碼管理?xiàng)l例；計(jì)算機(jī)安全管理?xiàng)l例；因特網(wǎng)安全管理?xiàng)l例等。④信息安全的教育措施對(duì)人的思想品德教育、安全意識(shí)教育、安全法律法規(guī)的教育等。國內(nèi)外的計(jì)算機(jī)犯罪事件都是人的思想品德出問題造成的。信息安全是一個(gè)系統(tǒng)工程必須綜合采取各種措施才能奏效。4、計(jì)算機(jī)系統(tǒng)的安全服務(wù)功能：身份認(rèn)證服務(wù)，訪問控制服務(wù)，數(shù)據(jù)加密服務(wù)，數(shù)據(jù)完整性服務(wù)，不可否認(rèn)服務(wù)，安全審計(jì)。三、密碼學(xué)的基本概念密碼技術(shù)是一門古老的技術(shù)。世界各國都視密碼為武器。戰(zhàn)爭(zhēng)的刺激和科學(xué)技術(shù)的發(fā)展推動(dòng)了密碼學(xué)的發(fā)展。信息技術(shù)的發(fā)展和廣泛應(yīng)用為密碼學(xué)開辟了廣闊的天地。我國的密碼分級(jí)：①核心密碼： 用于保護(hù)黨、政、軍的核心機(jī)密。②普通密碼：用于保護(hù)國家和事企業(yè)單位的低于核心機(jī)密而高于商用的機(jī)密信息。③商用密碼：用于保護(hù)國家和事企業(yè)單位的非機(jī)密的敏感信息。④個(gè)人密碼：用于保護(hù)個(gè)人的隱私信息。前三種密碼均由國家密碼管理局統(tǒng)一管理！我國商用密碼政策：①統(tǒng)一領(lǐng)導(dǎo)： 國家密碼管理局統(tǒng)一領(lǐng)導(dǎo)。②集中管理：國家密碼管理局辦公室集中管理。③定點(diǎn)研制： 只允許定點(diǎn)單位進(jìn)行研制。④?？亟?jīng)營：經(jīng)許可的單位才能經(jīng)營。⑤滿足使用：國內(nèi)各單位都可申請(qǐng)使用。1、密碼的基本思想偽裝信息，使未授權(quán)者不能理解它的真實(shí)含義。所謂偽裝就是對(duì)信息進(jìn)行一組可逆的數(shù)學(xué)變換。偽裝前的原始信息稱為明文,偽裝后的信息稱為密文，偽裝的過程稱為加密。去掉偽裝還原明文的過程成為解密。加密在加密密鑰的控制下進(jìn)行。解密在解密密鑰的控制下進(jìn)行。用于加密的一組數(shù)學(xué)變換稱為加密算法。用于解密的一組數(shù)學(xué)變換稱為解密算法。2、密碼體制(Cryptosystem)的構(gòu)成密碼體制由以下五部分組成：①明文空間M：全體明文的集合②密文空間C：全體密文的集合③密鑰空間K：全體密鑰的集合，K＝<Ke,Kd>④加密算法E：一族由MC的加密變換⑤解密算法D：一族由CM的解密變換。解密變換是加密變換的逆。對(duì)于一個(gè)確定的密鑰，加密算法將確定出一個(gè)具體的加密變換，解密算法將確定出一個(gè)具體的解密變換，而且解密變換就是加密變換的逆變換。 對(duì)于明文空間的每一個(gè)明文M，加密算法E在密鑰Ke的控制下將明文M加密成密文C： C＝E(M,Ke)。而解密算法D在密鑰Kd的控制下將密文解出同一明文M。 M＝D(C,Kd)=D(E(M,Ke),Kd)3、密碼體制的分類從加密鑰與解密鑰是否相等劃分：⑴傳統(tǒng)密碼：⑵公開密鑰密碼：從密鑰的使用方式劃分：⑴序列密碼：①明文、密文、密鑰以位（字符）為單位加解密；②核心密碼的主流；⑵分組密碼：①明文、密文、密鑰以分組為單位加解密；②商用密碼的主流：①傳統(tǒng)密碼：分組：DESIDEAEESAESMS4序列：RC4②公開密鑰密碼：RSAELGamalECC新型密碼：(1)演化密碼①密碼算法不斷演化變化，越來越強(qiáng)的密碼。②密碼設(shè)計(jì)自動(dòng)化的一種方法。③借鑒生物進(jìn)化，將密碼學(xué)與演化計(jì)算結(jié)合(2)量子密碼①在唯密文攻擊下絕對(duì)安全的密碼。②逐步走向?qū)嵱?。?007年我國宣布，國際上首個(gè)量子密碼通信網(wǎng)絡(luò)由我國科學(xué)家在北京測(cè)試運(yùn)行成功。這是迄今為止國際公開報(bào)道的唯一無中轉(zhuǎn)、可同時(shí)、任意互通的量子密碼通信網(wǎng)絡(luò)，標(biāo)志著量子保密通信技術(shù)從點(diǎn)對(duì)點(diǎn)方式向網(wǎng)絡(luò)化邁出了關(guān)鍵一步。(3)DNA密碼DNA密碼基于生物學(xué)中的某種困難問題。由于DNA密碼的安全不依賴于計(jì)算困難問題，所以不管未來的電子計(jì)算機(jī)、量子計(jì)算機(jī)和DNA計(jì)算機(jī)具有多么強(qiáng)大的計(jì)算能力，DNA密碼對(duì)于它們的計(jì)算攻擊都是免疫的。4、密碼學(xué)的組成①研究密碼編制的科學(xué)稱為密碼編制學(xué)(Cryptography),②研究密碼破譯的科學(xué)稱為密碼分析學(xué)(Cryptanalysis)，③而密碼編制學(xué)和密碼分析學(xué)共同組成密碼學(xué)(Cryptology)。5、密碼分析①如果能夠根據(jù)密文系統(tǒng)地確定出明文或密鑰，或者能夠根據(jù)明文-密文對(duì)系統(tǒng)地確定出密鑰，則我們說這個(gè)密碼是可破譯的。②一個(gè)密碼，如果無論密碼分析者截獲了多少密文和用什么方法進(jìn)行攻擊都不能被攻破，則稱為是絕對(duì)不可破譯的。③絕對(duì)不可破譯的密碼學(xué)在理論上是存在的——“一次一密”1)窮舉攻擊密碼分析者采用依次試遍所有可能的密鑰對(duì)所獲密文進(jìn)行解密，直至得到正確的明文；或者依次用一個(gè)確定的密鑰對(duì)所有可能的明文進(jìn)行加密，直至得到所獲得的密文。顯然，理論上，對(duì)于任何實(shí)用密碼只要有足夠的資源，都可以用窮舉攻擊將其改破。實(shí)例：1997年美國一個(gè)密碼分析小組宣布：1萬多人參加，通過INTERNET網(wǎng)絡(luò)，利用數(shù)萬臺(tái)微機(jī)，歷時(shí)4個(gè)多月，通過窮舉攻破了DES的一個(gè)密文。美國現(xiàn)在已有DES窮舉機(jī)，多CPU并行處理，24小時(shí)窮舉出一個(gè)密鑰。2)統(tǒng)計(jì)分析攻擊所謂統(tǒng)計(jì)分析攻擊就是指密碼分析者通過分析密文和明文的統(tǒng)計(jì)規(guī)律來破譯密碼。統(tǒng)計(jì)分析攻擊在歷史上為破譯密碼作出過極大的貢獻(xiàn)。許多古典密碼都可以通過統(tǒng)計(jì)分析而破譯。3)數(shù)學(xué)分析攻擊所謂數(shù)學(xué)分析攻擊是指密碼分析者針對(duì)加密算法的數(shù)學(xué)依據(jù)通過數(shù)學(xué)求解的方法來破譯密碼。為了對(duì)抗這種數(shù)學(xué)分析攻擊，應(yīng)當(dāng)選用具有堅(jiān)實(shí)數(shù)學(xué)基礎(chǔ)和足夠復(fù)雜的加密算法。根據(jù)占有的數(shù)據(jù)資源分類：A)僅知密文攻擊（Ciphertext-onlyattack）所謂僅知密文攻擊是指密碼分析者僅根據(jù)截獲的密文來破譯密碼。因?yàn)槊艽a分析者所能利用的數(shù)據(jù)資源僅為密文，因此這是對(duì)密碼分析者最不利的情況。密碼學(xué)的基本假設(shè)：攻擊者總能獲得密文。攻擊者總能知道密碼算法。攻擊者不知道密鑰。根據(jù)占有的數(shù)據(jù)資源分類：B)已知明文攻擊（Known-plaintextattack）所謂已知明文攻擊是指密碼分析者根據(jù)已經(jīng)知道的某些明文-密文對(duì)來破譯密碼。攻擊者總是能獲得密文，并猜出部分明文。計(jì)算機(jī)程序文件加密特別容易受到這種攻擊。根據(jù)占有的數(shù)據(jù)資源分類：C)選擇明文攻擊（Chosen-plaintextattack）所謂選擇明文攻擊是指密碼分析者能夠選擇明文并獲得相應(yīng)的密文。計(jì)算機(jī)文件加密和數(shù)據(jù)庫加密特別容易受到這種攻擊。這是對(duì)攻擊者最有利的情況！6、密碼學(xué)的理論基礎(chǔ)⑴商農(nóng)信息論①從信息在信道傳輸中可能受到攻擊，引入密碼理論；②提出以擴(kuò)散和混淆兩種基本方法設(shè)計(jì)密碼；③闡明了密碼系統(tǒng)，完善保密，理論保密和實(shí)際保密等概念。⑵計(jì)算復(fù)雜性理論①密碼的安全性以計(jì)算復(fù)雜度來度量；②現(xiàn)代密碼往往建立在一個(gè)數(shù)學(xué)難題之上，而難是計(jì)算復(fù)雜度的概念；③計(jì)算復(fù)雜度只能為密碼提供一個(gè)必要條件。7、密碼設(shè)計(jì)的基本方法⑴公開設(shè)計(jì)原則密碼的安全應(yīng)僅依賴于對(duì)密鑰的保密，不依賴于對(duì)算法的保密。⑵擴(kuò)散和混淆①擴(kuò)散(diffusion)：將明文和密鑰的每一位的影響散布到盡量多的密文位中；理想情況下達(dá)到完備性。②混淆(confusion):使明文、密鑰和密文之間的關(guān)系復(fù)雜化。⑶迭代與乘積①迭代：設(shè)計(jì)一個(gè)輪函數(shù)，然后迭代。②乘積：將幾種密碼聯(lián)合應(yīng)用。8、密碼學(xué)的一些結(jié)論：①公開設(shè)計(jì)原則：密碼的安全只依賴于密鑰的保密，不依賴于算法的保密；②理論上絕對(duì)安全的密碼是存在的：一次一密；③理論上，任何實(shí)用的密碼都是可破的；④我們追求的是計(jì)算上的安全。⑤計(jì)算上的安全：使用可利用的計(jì)算資源不能破譯。復(fù)習(xí)題解釋信息安全的含義。密碼的基本思想是什么？密碼體制分哪些類型？各有什么優(yōu)缺點(diǎn)？什么是密碼分析？密碼分析有哪些類型？為什么說理論上，任何實(shí)用的密碼都是可破的？計(jì)算機(jī)的程序文件和數(shù)據(jù)庫文件加密容易受到什么攻擊？為什么？

第二講古典密碼一、主要古典密碼C.D.Shannon:采用混淆、擴(kuò)散和乘積的方法來設(shè)計(jì)密碼混淆：使密文和明文、密鑰之間的關(guān)系復(fù)雜化擴(kuò)散：將每一位明文和密鑰的影響擴(kuò)大到盡可能多的密文位中。乘積和迭代：多種加密方法混合使用對(duì)一個(gè)加密函數(shù)多次迭代古典密碼編碼方法：置換，代替，加法1、置換密碼把明文中的字母重新排列，字母本身不變，但其位置改變了，這樣編成的密碼稱為置換密碼。最簡單的置換密碼是把明文中的字母順序倒過來，然后截成固定長度的字母組作為密文。明文：明晨5點(diǎn)發(fā)動(dòng)反攻。MINGCHENWUDIANFADONGFANGONG密文：GNOGNAFGNODAFNAIDUWNEHCGNIM理論上：①、置換密碼的加密鑰是置換矩陣p，解密鑰是置換矩陣p-1。②、置換密碼經(jīng)不起已知明文攻擊。⑴單表代替密碼①、加法密碼A和B是有n個(gè)字母的字母表。定義一個(gè)由A到B的映射：f:A→Bf(ai)=bi=ajj=i+kmodn加法密碼是用明文字母在字母表中后面第k個(gè)字母來代替。K=3時(shí)是著名的凱撒密碼。②、乘法密碼A和B是有n個(gè)字母的字母表。定義一個(gè)由A到B的映射：f:A→Bf(ai)=bi=ajj=ikmodn其中，(n,k)=1。注意：只有(n,k)=1，才能正確解密。③密鑰詞組代替密碼：隨機(jī)選一個(gè)詞語，去掉其中的重復(fù)字母，寫到矩陣的第一行，從明文字母表中去掉這第一行的字母，其余字母順序?qū)懭刖仃嚒Ｈ缓蟀戳腥〕鲎帜笜?gòu)成密文字母表。舉例：密鑰：HONGYE矩陣：HONGYE選出順序：按列ABCDFIJKLMPQ改變密鑰、矩陣大小RSTUVW和取出序列，得到不同的XZ密文字母表。密文字母表:B={HAJRXOBKSZNCLTGDMUYFPVEIQW}⑵、多表代替密碼單表代替密碼的安全性不高，一個(gè)原因是一個(gè)明文字母只由一個(gè)密文字母代替。構(gòu)造多個(gè)密文字母表，在密鑰的控制下用相應(yīng)密文字母表中的一個(gè)字母來代替明文字母表中的一個(gè)字母。一個(gè)明文字母有多種代替。Vigenere密碼：著名的多表代替密碼3、代數(shù)密碼：①Vernam密碼明文、密文、密鑰都表示為二進(jìn)制位：M=m1,m2,…,mnK=k1,k2,…,knC=c1,c2,…,cn②加密：c1=mi⊕ki,i=1,2,…,n解密：m1=ci⊕ki,i=1,2,…,n③因?yàn)榧咏饷芩惴ㄊ悄?加，所以稱為代數(shù)密碼。④對(duì)合運(yùn)算：f=f-1，模2加運(yùn)算是對(duì)合運(yùn)算。密碼算法是對(duì)和運(yùn)算，則加密算法＝解密算法，工程實(shí)現(xiàn)工作量減半。⑤Vernam密碼經(jīng)不起已知明文攻擊。⑥如果密鑰序列有重復(fù)，則Vernam密碼是不安全的。⑦一種極端情況：一次一密?密鑰是隨機(jī)序列。?密鑰至少和明文一樣長。?一個(gè)密鑰只用一次。⑧一次一密是絕對(duì)不可破譯的，但它是不實(shí)用的。⑨一次一密給密碼設(shè)計(jì)指出一個(gè)方向，人們用序列密碼逼近一次一密。二、古典密碼的窮舉分析1、單表代替密碼分析①加法密碼因?yàn)閒(ai)=bi=ajj=i+kmodn所以k=1,2，...,n-1,共n-1種可能，密鑰空間太小。以英文為例，只有25種密鑰。經(jīng)不起窮舉攻擊。②乘法密碼因?yàn)閒(ai)=bi=ajj=ikmodn，且（k,n）=1。所以k共有（n）種可能，密鑰空間更小。對(duì)于英文字母表，n=26，k=1,3,5,7,9,11,15,17,19,21,23,25取掉1，共11種，比加法密碼更弱。經(jīng)不起窮舉攻擊。③密鑰詞語代替密碼因?yàn)槊荑€詞語的選取是隨機(jī)的，所以密文字母表完全可能窮盡明文字母表的全排列。以英文字母表為例，n=26，所以共有26！種可能的密文字母表。26！≈41026用計(jì)算機(jī)也不可能窮舉攻擊。注意：窮舉不是攻擊密鑰詞語代替密碼的唯一方法。三、古典密碼的統(tǒng)計(jì)分析1、密鑰詞組單表代替密碼的統(tǒng)計(jì)分析任何自然語言都有自己的統(tǒng)計(jì)規(guī)律。如果密文中保留了明文的統(tǒng)計(jì)特征，就可用統(tǒng)計(jì)方法攻擊密碼。由于單表代替密碼只使用一個(gè)密文字母表，一個(gè)明文字母固定的用一個(gè)密文字母來代替，所以密文的統(tǒng)計(jì)規(guī)律與明文相同。因此，單表代替密碼可用統(tǒng)計(jì)分析攻破。2、英語的統(tǒng)計(jì)規(guī)律每個(gè)單字母出現(xiàn)的頻率穩(wěn)定。最高頻率字母E次高頻率字母TAOINSHR中高頻率字母DL低頻率字母CUMWFGYPB最低頻率字母VKJXQZ頻率最高的雙字母組：THHEINERANREEDONESSTENATTONTHANDOUEANGASORTIISETITARTESEHIOF頻率最高的三字母組：THEINGANDHEREREENTTHAWASETHFORDHTHATSHEIONHISERSVER其中THE的頻率是ING的3倍！英文單詞以E，S，D，T為結(jié)尾的超過一半。英文單詞以T，A，S，W為起始字母的約占一半。還有其它統(tǒng)計(jì)規(guī)律！教科書上有一個(gè)完整的統(tǒng)計(jì)分析例子。經(jīng)得起統(tǒng)計(jì)分析是對(duì)近代密碼的基本要求！復(fù)習(xí)題①已知置換如下： 123456351642明文＝642135,密文＝？密文＝214365，明文＝？②使加法密碼算法稱為對(duì)合運(yùn)算的密鑰k稱為對(duì)合密鑰，以英文為例求出其對(duì)合密鑰。③已知一個(gè)加法密碼的密文如下：BEEAKFYDJXUQYHYJIQRYHTYJIQFBQDUYJIIKFUHCQD用窮舉法求出明文。④以英文為例，用加法密碼，取密鑰常數(shù)k=7,對(duì)明文INFORMATIONSECURITY，進(jìn)行加密，求出密文。⑤證明，在置換密碼中，置換p是對(duì)合的，當(dāng)且僅當(dāng)對(duì)任意的i和j(i,j=1,2,3,…,n)，若p(i)=j，則必有p(j)=i。⑥編程實(shí)現(xiàn)Vigenre密碼。⑦分析仿射密碼的安全性。

第三講數(shù)據(jù)加密標(biāo)準(zhǔn)DES一、DES的概況1、重要時(shí)間：1973年美國國家標(biāo)準(zhǔn)局（NBS）向社會(huì)公開征集加密算法，以制定加密算法標(biāo)準(zhǔn)；1974年第二次征集；1975年選中IBM的算法，公布征求意見；1977年1月15日正式頒布；1998年底以后停用。1999年頒布3DES為新標(biāo)準(zhǔn)。2、標(biāo)準(zhǔn)加密算法的目標(biāo)①用于加密保護(hù)政府機(jī)構(gòu)和商業(yè)部門的非機(jī)密的敏感數(shù)據(jù)。②用于加密保護(hù)靜態(tài)存儲(chǔ)和傳輸信道中的數(shù)據(jù)。③安全使用10~15年。3、整體特點(diǎn)①分組密碼:明文、密文和密鑰的分組長度都是64位。②面向二進(jìn)制的密碼算法:因而能夠加解密任何形式的計(jì)算機(jī)數(shù)據(jù)。③對(duì)合運(yùn)算:因而加密和解密共用同一算法，使工程實(shí)現(xiàn)的工作量減半。④綜合運(yùn)用了置換、代替、代數(shù)等多種密碼技術(shù)。4、應(yīng)用①許多國際組織采用為標(biāo)準(zhǔn)。②在全世界范圍得到廣泛應(yīng)用。③產(chǎn)品形式：軟件（嵌入式，應(yīng)用軟件）；硬件（芯片，插卡）5、結(jié)論用于其設(shè)計(jì)目標(biāo)是安全的。設(shè)計(jì)精巧、實(shí)現(xiàn)容易、使用方便，堪稱典范。二、算法1、DES加密過程的數(shù)學(xué)描述：Li=Ri-1Ri=Li-1⊕f(Ri-1,Ki)i=1,2,3,…162、置換選擇1：①、作用去掉密鑰中的8個(gè)奇偶校驗(yàn)位。打亂重排，形成C0(左28位)，D0(右28位)。3、循環(huán)移位：①、作用對(duì)C0，D0分別循環(huán)移位。4、置換選擇2：①、作用從Ci和Di（56位）中選擇出一個(gè)48位的子密鑰Ki。5、初始置換IP①、作用把64位明文打亂重排。左一半為L0(左32位)，右一半為R0(右32位)。例：把輸入的第1位置換到第40位，把輸入的第58位置換到第1位。6、逆初始置換IP－1①、作用把64位中間密文打亂重排。形成最終的64位密文。7、加密函數(shù)f①作用DES的核心。加密數(shù)據(jù)。數(shù)據(jù)處理寬度32位。②選擇運(yùn)算E把32位輸入擴(kuò)充為48位中間數(shù)據(jù)；重復(fù)使用數(shù)據(jù)實(shí)現(xiàn)擴(kuò)充。③選擇替換S（S盒）S盒是DES唯一的非線性變換。S盒是DES安全的關(guān)鍵。共有8個(gè)S盒。每個(gè)S盒有6個(gè)輸入，4個(gè)輸出，是一種非線性壓縮變換。設(shè)輸入為b1b2b3b4b5b6,則以b1b6組成的二進(jìn)制數(shù)為行號(hào)，b2b3b4b5組成的二進(jìn)制數(shù)為列號(hào)。行列交點(diǎn)處的數(shù)（二進(jìn)制）為輸出。④置換運(yùn)算P把數(shù)據(jù)打亂重排。8、DES的解密過程DES的運(yùn)算是對(duì)和運(yùn)算，解密和加密可共用同一個(gè)運(yùn)算。不同點(diǎn)：子密鑰使用的順序不同。第一次解密迭代使用子密鑰K16，第二次解密迭代使用子密鑰K15，第十六次解密迭代使用子密鑰K1。DES解密過程的數(shù)學(xué)描述：Ri-1=LiLi-1=Ri⊕f(Li,Ki)i=16,15,14，...，19、DES的對(duì)和性證明1、可逆性證明①定義T是把64位數(shù)據(jù)的左右兩半交換位置：T（L，R）＝（R，L）因?yàn)?，T2（L，R）＝（L，R）＝I，其中I為恒等變換，于是，T=T–1，所以T變換是對(duì)合運(yùn)算。②記DES第i輪中的主要運(yùn)算為，即Fi（Li–1，Ri-1）＝（Li-1⊕f（Ri-1,Ki），Ri-1）Fi2＝Fi（Li-1⊕f（Ri-1,Ki），Ri-1）＝（Li-1⊕f（Ri-1,Ki）⊕f（Ri-1,Ki），Ri-1）＝（Li–1，Ri-1）＝I所以，F(xiàn)i＝Fi–1。所以Fi變換也是對(duì)合運(yùn)算。③結(jié)合①、②，便構(gòu)成DES的輪運(yùn)算Hi＝FiT因?yàn)椋‵iT）（TFi）=（Fi（TT）Fi）=FiFi=I，所以（FiT）－1＝（TFi）（FiT）＝（TFi）－1④加解密表示⑴DES(M)＝IP-1(F16)(TF15)…(TF2)(TF1)IP（M）＝C⑵DES-1(C)＝IP-1(F1)(TF2)(TF3)…(TF15)(TF16)IP（C）把⑴式代入⑵式可證：DES-1(DES(M))＝M所以，DES是可逆的。2、對(duì)合性證明DES＝IP-1(F16)(TF15)(TF14)…(TF3)(TF2)(TF1)IPDES-1＝IP-1(F1)(TF2)(TF3)…(TF14)(TF15)(TF16)IPDES和DES-1除了子密鑰的使用順序相反之外是相同的，所以DES的運(yùn)算是對(duì)合運(yùn)算。10、DES的安全性①攻擊窮舉攻擊。目前最有效的方法。差分攻擊。線性攻擊。11、3重DES①美國NIST在1999年發(fā)布了一個(gè)新版本的DES標(biāo)準(zhǔn)（FIPSPUB46-3）：DES只用于遺留系統(tǒng)。3DES將取代DES成為新的標(biāo)準(zhǔn)。國際組織和我國銀行都接受3DES。②3DES的優(yōu)勢(shì)：3密鑰的3DES：密鑰長度是168位。2密鑰的3DES：密鑰長度是112位。安全：密鑰足夠長；經(jīng)過最充分的分析和實(shí)踐檢驗(yàn)。兼容性好。12、DES的歷史回顧DES的出現(xiàn)標(biāo)志著商業(yè)密碼需求的增加。DES體現(xiàn)商農(nóng)的密碼設(shè)計(jì)理論。體現(xiàn)了公開設(shè)計(jì)原則，開創(chuàng)公開算法的先例。DES代表當(dāng)時(shí)商業(yè)密碼的最高水平。大作業(yè)1以3DES作為加密算法開發(fā)出文件加密軟件系統(tǒng)：具有文件加密和解密功能；具有加解密速度統(tǒng)計(jì)功能；采用密文反饋鏈接和密文挪用短塊處理技術(shù)；具有較好的人機(jī)界面。復(fù)習(xí)題1、分析DES的弱密鑰。2、證明DES具有互補(bǔ)對(duì)稱性。3、畫出3密鑰3DES的框圖。

第四講高級(jí)數(shù)據(jù)加密標(biāo)準(zhǔn)一、AES的概況1、歷史時(shí)間：1997年美國政府向社會(huì)公開征集高級(jí)數(shù)據(jù)加密標(biāo)準(zhǔn)（AES）；1998年8月20日從應(yīng)征的21個(gè)算法中選出15個(gè)。1999年8月又選中其中5個(gè)算法。2000年10月2日再選出1個(gè)算法。2001年11月26日接受其作為標(biāo)準(zhǔn)。2001年12月4日正式公布：FIPS－197。2、AES產(chǎn)生的背景①1984年12月里根總統(tǒng)下令由國家保密局研制新密碼標(biāo)準(zhǔn)，以取代DES。②1991年新密碼開始試用并征求意見。民眾要求公開算法，并去掉法律監(jiān)督。③1994年頒布新密碼標(biāo)準(zhǔn)（EES）。④1995年5月貝爾實(shí)驗(yàn)室的博士生M.Blaze在PC機(jī)上用45分鐘攻擊法律監(jiān)督字段獲得成功。⑤1995年7月美國政府放棄用EES加密數(shù)據(jù)。 ⑥1997年美國政府向社會(huì)公開征AES。⑦美國商用密碼政策的變化公開征集秘密設(shè)計(jì)公開征集成功不成功預(yù)計(jì)成功3、AES的設(shè)計(jì)要求①安全性：抵抗所有已知攻擊；②實(shí)用性：適應(yīng)各種環(huán)境，速度快；③擴(kuò)展性：分組長度和密鑰長度可擴(kuò)展。4、整體特點(diǎn)①分組密碼:明文長度128,密文長度、密鑰長度可變（128/192/256等,現(xiàn)在一般取128）。②面向二進(jìn)制的密碼算法:能夠加解密任何形式的計(jì)算機(jī)數(shù)據(jù)。③不是對(duì)合運(yùn)算:加、解密使用不同的算法。④綜合運(yùn)用置換、代替、代數(shù)等多種密碼技術(shù)⑤整體結(jié)構(gòu)：基本輪函數(shù)加迭代。圈數(shù)可變，≥105、應(yīng)用①許多國際組織采用為標(biāo)準(zhǔn)。②尚未大范圍應(yīng)用。③產(chǎn)品形式：軟件（嵌入式，應(yīng)用軟件）；硬件（芯片，插卡）6、結(jié)論只有通過實(shí)際應(yīng)用的檢驗(yàn)才能證明其安全。我們相信：經(jīng)過全世界廣泛分析的AES是不負(fù)眾望的。二、AES的基本變換1、AES的數(shù)據(jù)處理方式①字節(jié)②字③狀態(tài)2、狀態(tài)①加解密過程中的中間數(shù)據(jù)。②以字節(jié)為元素的矩陣，或二維數(shù)組。③符號(hào)：Nb－明密文所含的數(shù)據(jù)的字?jǐn)?shù)。Nk－密鑰所含的數(shù)據(jù)的字?jǐn)?shù)。Nr－迭代圈數(shù)。④例：Nb＝4時(shí)的狀態(tài)Nk＝4時(shí)的密鑰數(shù)組a0,0a0,1a0,2a0,3k0,0k0,1k0,2k0,3a1,0a1,1a1,2a1,3k1,0k1,1k1,2k1,3a2,0a2,1a2,2a2,3k2,0k2,1k2,2k2,3a3,0a3,1a3,2a3,3k3,0k3,1k3,2k3,3⑤Nb、Nk、Nr之間的關(guān)系：NrNb=4Nb=6Nb=8Nk=4101214Nk=6121214Nk=81414143、圈變換－加密輪函數(shù)①標(biāo)準(zhǔn)圈變換：Round(State,RoundKey)ByteSub(State);S盒變換ShiftRow(State);行移位變換MixColumn(State);列混合變換AddRoundKey(State,RoundKey)圈密鑰加變換②最后一圈的圈變換：Round(State,RounKey)ByteSub(State);S盒變換ShiftRow(State);行移位變換AddRoundKey(State,RoundKey)圈密鑰加變換注：最后一圈的圈變換中沒有列混合變換。4、S盒變換ByteSub(State)①S盒變換是AES的唯一的非線性變換，是AES安全的關(guān)鍵。②AES使用16個(gè)相同的S盒，DES使用8個(gè)不相同的S盒。③AES的S盒有8位輸入8位輸出，DES的S盒有6位輸入4位輸出。④S盒變換:a)將輸入字節(jié)用其GF(28)上的逆來代替；b)對(duì)a)的結(jié)果作如下的仿射變換：（以x0－x7作輸入，以y0－y7作輸出。）y010001111x01y111000111x11y211100011x20y3=11110001x3+0y411111000x40y501111100x51y600111110x61y700011111x71注意：S盒變換的第一步是把字節(jié)的值用它的乘法逆來代替，是一種非線性變換。由于系數(shù)矩陣中每列都含有5個(gè)1，這說明改變輸入中的任意一位，將影響輸出中的5位發(fā)生變化。由于系數(shù)矩陣中每行都含有5個(gè)1，這說明輸出中的每一位，都與輸入中的5位相關(guān)。三、圈密鑰生成W0W1W2…WNk-1WNkWNk+1…用戶密鑰當(dāng)j不是Nk的整數(shù)倍時(shí):Wj＝Wj-Nk⊕Wj-1當(dāng)j是Nk的整數(shù)倍時(shí):Wj＝Wj-Nk⊕ByteSub(Rotl(Wj-1))⊕Rcon[j/Nk];四、AES的解密算法加密算法不是對(duì)合運(yùn)算：(AES)-1≠AES解密算法的結(jié)構(gòu)與加密算法的結(jié)構(gòu)相同解密中的變換為加密算法變換的逆變換，且密鑰擴(kuò)展策略稍有不同。Decryption(State,CipherKey){Inv_KeyExpansion(CipherKey,Inv_RoundKey);AddRoundKey(State,Inv_RoundKey);For(I=1;I<Nr;I++)Inv_Round(State,Inv_RoundKey);{Inv_ByteSub(State);Inv_ShiftRow(State);Inv_MixColumn(State);AddRoundKey(State,Inv_RoundKey；}Inv_FinalRound(State,Inv_RoundKey){InvByteSub(State);InvShiftRow(State);AddRoundKey(State,Inv_RoundKey)；}}五、AES的實(shí)現(xiàn)適應(yīng)多種環(huán)境，高效，方便是AES的突出優(yōu)點(diǎn)。由于AES的基本運(yùn)算由ByteSub、MixColumn、ShiftRow和AddRoundKey變換構(gòu)成，因此AES的實(shí)現(xiàn)主要是這些變換的實(shí)現(xiàn)。其中ShiftRow和AddRoundKey的實(shí)現(xiàn)比較容易，因此主要是ByteSub和MixColumn變換的實(shí)現(xiàn)問題。有了這些基本運(yùn)算的實(shí)現(xiàn)，便可以有效地實(shí)現(xiàn)整個(gè)AES。實(shí)現(xiàn)方法：軟件硬件軟件方法：基于算法描述；基于查表1、基于算法描述的軟件實(shí)現(xiàn)AES的算法描述是一種程序化的描述，便于實(shí)現(xiàn)。AES的四種基本變換都比較簡單，便于實(shí)現(xiàn)。用C語言仿照算法描述，可方便地實(shí)現(xiàn)。這種實(shí)現(xiàn)的速度不是最快的！2、基于查表的軟件實(shí)現(xiàn)用查表實(shí)現(xiàn)算法是一種高效的軟件設(shè)計(jì)方法。時(shí)空折換是信息科學(xué)的基本策略。用查表實(shí)現(xiàn)算法，就是用空間換取時(shí)間。目前計(jì)算機(jī)系統(tǒng)的存儲(chǔ)空間大、而且便宜，為查表實(shí)現(xiàn)算法提供了物資基礎(chǔ)。①S盒的實(shí)現(xiàn)實(shí)現(xiàn)S盒變換的最快方法是，直接計(jì)算出S盒的變換的結(jié)果，并存儲(chǔ)造表，使用時(shí)時(shí)直接查表。因?yàn)锽yteSub變換是字節(jié)函數(shù)，所以表的規(guī)模不大，只含256個(gè)元素。注意：解密時(shí)用的是逆S盒，因此共需要造兩個(gè)S盒表。六、AES的安全性能夠抵抗目前所有的已知攻擊：窮舉攻擊。差分攻擊。線性攻擊。Square攻擊。七、AES的評(píng)說AES體現(xiàn)商農(nóng)的密碼設(shè)計(jì)理論。體現(xiàn)了公開設(shè)計(jì)原則：公開算法AES代表當(dāng)今商業(yè)密碼的最高水平。大作業(yè)以AES作為加密算法開發(fā)出文件加密軟件系統(tǒng)：具有文件加密和解密功能；具有加解密速度統(tǒng)計(jì)功能；采用密文反饋鏈接和密文挪用短塊處理技術(shù)；具有較好的人機(jī)界面。復(fù)習(xí)題1、對(duì)比AES和DES有什么不同？2、AES的解密算法與加密算法有什么不同？3、在GF（28）中，01的逆元素是什么？4、對(duì)于字節(jié)“00”和“01”計(jì)算S盒的輸出。5、證明c(x)與d(x)互逆，模x4+1。6、證明:ximod(x4+1)=ximod4

第五講中國商用密碼SMS4一、我國的密碼分級(jí)：①核心密碼： 用于保護(hù)黨、政、軍的核心機(jī)密。②普通密碼：用于保護(hù)國家和事企業(yè)單位的低于核心機(jī)密而高于商業(yè)機(jī)密的密碼信息。③商用密碼：用于保護(hù)國家和事企業(yè)單位的非機(jī)密的敏感信息。④個(gè)人密碼：用于保護(hù)個(gè)人的隱私信息。前三種密碼均由國家密碼管理局統(tǒng)一管理。二、我國商的業(yè)密碼政策①統(tǒng)一領(lǐng)導(dǎo)： 國家密碼管理局統(tǒng)一領(lǐng)導(dǎo)。②集中管理：國家密碼管理局辦公室集中管理。③定點(diǎn)研制：研制只允許定點(diǎn)單位進(jìn)行。④?？亟?jīng)營：經(jīng)許可的單位才能經(jīng)營。⑤滿足使用：國內(nèi)各單位都可申請(qǐng)使用。三、我國商用密碼概況⑴密碼的公開設(shè)計(jì)原則密碼的安全應(yīng)僅依賴于對(duì)密鑰的保密，不依賴于對(duì)算法的保密。⑵公開設(shè)計(jì)原則并不要求使用時(shí)公開所有的密碼算法 核心密碼不能公布算法；核心密碼的設(shè)計(jì)也要遵循公開設(shè)計(jì)原則。⑶商用密碼應(yīng)當(dāng)公開算法①美國DES開創(chuàng)了公開商用密碼算法的先例；②美國經(jīng)歷DES（公開）→EES（保密）→AES（公開）。③歐洲也公布商用密碼算法⑷我國的商用密碼概況●我國在密碼技術(shù)方面具有優(yōu)勢(shì)： 密碼理論、密碼分析●長期以來不公開密碼算法，只提供密碼芯片 少數(shù)專家設(shè)計(jì)，難免有疏漏；難于標(biāo)準(zhǔn)化，不利于推廣應(yīng)用?！?006年2月我國公布了部分商用密碼算法；☆商用密碼管理更科學(xué)化、與國際接軌；☆將促進(jìn)我國商用密碼的發(fā)展。四、我國商用密碼SMS4①分組密碼： 數(shù)據(jù)分組長度=128位、密鑰長度=128位數(shù)據(jù)處理單位：字節(jié)（8位），字（32位）②密碼算法結(jié)構(gòu)： 基本輪函數(shù)加迭代對(duì)合運(yùn)算：解密算法與加密算法相同五、SMS4密碼算法1、基本運(yùn)算： ①模2加：⊕，32比特異或運(yùn)算②循環(huán)移位：<<<i，把32位字循環(huán)左移i位2、基本密碼部件： ①非線性字節(jié)變換部件S盒：☆8位輸入、8位輸出。☆本質(zhì)上，8位的非線性置換。☆設(shè)輸入位a，輸出位b，表示為： b=S_Box（a）S盒中數(shù)據(jù)為16進(jìn)制數(shù)☆S盒的置換規(guī)則：以輸入的前半字節(jié)為行號(hào)，后半字節(jié)為列號(hào)，行列交叉點(diǎn)處的數(shù)據(jù)即為輸出。舉例：設(shè)輸入為“ef”，則行號(hào)為e，列號(hào)為f，于是S盒的輸出值為表中第e行和第f列交叉點(diǎn)的值，Sbox(‘ef’)=‘84’。②非線性字變換：32位字的非線性變換▼4個(gè)S盒并行置換； ▼設(shè)輸入字A=(a0,a1,a2,a3),輸出字B=(b0,b1,b2,b3),B=(A)=(S_box(a0),S_box(a1),S_box(a2),S_box(a3))③字線性部件L變換： ☆32位輸入、32位輸出。☆設(shè)輸入位B，輸出位C，表為： C=L（B）☆運(yùn)算規(guī)則： C=L（B） =B⊕(B<<<2)⊕(B<<<10)⊕(B<<<18)⊕(B<<<24)④字合成變換T： ☆由非線性變換τ和線性變換L復(fù)合而成；☆T(X)=L(τ(X))。先S盒變換，再L變換。3、輪函數(shù)F：☆輸入數(shù)據(jù)：（X0，X1，X2，X3），128位，四個(gè)32位字?！钶斎胼喢荑€：rk，32位字?！钶敵鰯?shù)據(jù)：32位字?！钶喓瘮?shù)F： F（X0，X1，X2，X3，rk） =X0⊕T（X1⊕X2⊕X3⊕rk)4、加密算法：輸入明文：（X0，X1，X2，X3），128位，四個(gè)字。輸入輪密鑰：rki，i=0,1,…,31，32個(gè)字。輸出密文：（Y0，Y1，Y2，Y3），128位，四個(gè)字。算法結(jié)構(gòu)：輪函數(shù)的32輪迭代，每輪使用一個(gè)輪密鑰。加密算法： Xi+4=F（Xi，Xi+1，Xi+2，Xi+3，rki） =Xi⊕T（Xi+1⊕Xi+2⊕Xi+3⊕rki)，i=0,1…31 （Y0，Y1，Y2，Y3）=（X35，X34，X33，X32）5、解密算法：輸入密文：（X0，X1，X2，X3）輸入輪密鑰：rki，i=31,30，…,1，0輸出明文：（Y0，Y1，Y2，Y3）算法：輪函數(shù)的32輪迭代，每輪使用一個(gè)輪密鑰。解密算法： Xi+4=F（Xi，Xi+1，Xi+2，Xi+3，rki） =Xi⊕T（Xi+1⊕Xi+2⊕Xi+3⊕rki),i=31,…1,0 （Y0，Y1，Y2，Y3）=（X35，X34，X33，X32）6、密鑰擴(kuò)展算法：①常數(shù)FK在密鑰擴(kuò)展中使用一些常數(shù) FK0=(A3B1BAC6)，F(xiàn)K1=(56AA3350)，F(xiàn)K2=(677D9197)，F(xiàn)K3=(B27022DC)。②固定參數(shù)CK32個(gè)固定參數(shù)Cki，i=0,1,2…31 00070e15,1c232a31,383f464d,545b6269, 70777e85,8c939aa1,a8afb6bd,c4cbd2d9, e0e7eef5,fc030a11,181f262d,343b4249, 50575e65,6c737a81,888f969d,a4abb2b9, c0c7ced5,dce3eaf1,f8ff060d,141b2229, 30373e45,4c535a61,686f767d,848b9299, a0a7aeb5,bcc3cad1,d8dfe6ed,f4fb0209, 10171e25,2c333a41,484f565d,646b7279產(chǎn)生規(guī)則：Ckij=(4i+j)×7（mod256），i=0,1,2…31,j=0,1,…3。輸入加密密鑰：MK=（MK0，MK1，MK2，MK3）輸出輪密鑰：rki，i=0，1…,30，31中間數(shù)據(jù)：Ki，i=0，1…,34，35密鑰擴(kuò)展算法：①(K0,K1,K2,K3)=(MK0⊕FK0,MK1⊕FK1,MK2⊕FK2,MK3⊕FK3)②Fori=0，1…,30，31Do iki=Ki+4=Ki⊕T’(Ki+1⊕Ki+2⊕Ki+3⊕CKi)說明：T’變換與加密算法輪函數(shù)中的T基本相同，只將其中的線性變換L修改為以下：L’ L’(B)=B⊕(B<<<13)⊕(B<<<23)7、實(shí)例：明文:0123456789abcdeffedcba9876543210密鑰:0123456789abcdeffedcba9876543210密文:681edf34d206965e86b3e94f536e42468、安全性①國家專業(yè)機(jī)構(gòu)設(shè)計(jì)。算法簡潔，以字和字節(jié)為處理單位，對(duì)合運(yùn)算，符合當(dāng)今分組密碼主流。②專業(yè)機(jī)構(gòu)進(jìn)行了密碼分析，因此是安全的。③民間學(xué)者對(duì)21輪SMS4進(jìn)行了差分密碼分析。④尚需經(jīng)過實(shí)踐檢驗(yàn)。練習(xí)題1、分析SMS4在密碼結(jié)構(gòu)上與DES和AES有何異同？2、編程研究SMS4的S盒的以下特性： ①輸入改變1位，輸出平均改變多少位？②對(duì)于一個(gè)輸入，連續(xù)施加S盒變換，變換多少次時(shí)出現(xiàn)輸出等于輸入？3、我國公布商用密碼算法有何意義？大作業(yè)以SMS4作為加密算法開發(fā)出文件加密軟件系統(tǒng)：具有文件加密和解密功能；具有加解密速度統(tǒng)計(jì)功能；采用密文反饋鏈接和密文挪用短塊處理技術(shù)；具有較好的人機(jī)界面。

第六講分組密碼的應(yīng)用技術(shù)一、計(jì)算機(jī)數(shù)據(jù)的特殊性1、存在明顯的數(shù)據(jù)模式：許多數(shù)據(jù)都具有某種固有的模式。這主要是由數(shù)據(jù)冗余和數(shù)據(jù)結(jié)構(gòu)引起的。各種計(jì)算機(jī)語言的語句和指令都十分有限，因而在程序中便表現(xiàn)為少量的語句和指令的大量重復(fù)。各種語言程序往往具有某種固定格式。數(shù)據(jù)庫的記錄也往往具有某種固定結(jié)構(gòu)。操作系統(tǒng)和網(wǎng)絡(luò)也有同樣的問題。根據(jù)明文相同、密鑰相同，則密文相同的道理，這些固有的數(shù)據(jù)模式將在密文中表現(xiàn)出來。掩蓋明文數(shù)據(jù)模式的方法： 預(yù)處理技術(shù)(隨機(jī)掩蓋) 鏈接技術(shù)如果不能掩蓋數(shù)據(jù)模式，既使采用安全的密碼算法也是徒勞的。二、分組密碼的工作模式1977年DES頒布。1981年美國針對(duì)DES的應(yīng)用制定了四種基本工作模式：電碼本模式（ECB）密文反饋鏈接模式（CBC）密碼反饋模式（CFB）輸出反饋模式（OFB）2000年美國在征集AES的同時(shí)又公開征集AES的工作模式。共征集到15個(gè)候選工作模式。新的工作模式標(biāo)準(zhǔn)還在評(píng)審中。這些新的工作模式將為AES的應(yīng)用作出貢獻(xiàn)。1、電碼本模式（ECB）直接利用分組密碼對(duì)明文的各分組進(jìn)行加密。設(shè)明文M=（M1，M2，…，Mn）, 密鑰為K，密文C＝(C1，C2，…，Cn),其中Ci＝E（Mi，K）,i=1,2,…,n電碼本方式是分組密碼的基本工作模式。缺點(diǎn)：可能出現(xiàn)短塊，這時(shí)需要特殊處理。缺點(diǎn)：暴露明文的數(shù)據(jù)模式。應(yīng)用：適合加密密鑰等短數(shù)據(jù)2、密文反饋鏈接模式（CBC）①明密文鏈接方式（PlaintextandCiphertextBlockChaining）設(shè)明文M=（M1，M2，…，Mn）,密鑰為K，密文C=(C1，C2，…，Cn),其中E（Mi⊕Z，K），i=1E（Mi⊕Mi-1⊕Ci-1，K）,i=2,…,nZ為初始化向量。即使Mi＝Mj，但因一般都有Mi-1⊕Ci-1≠M(fèi)j-1⊕Cj-1，從而使Ci≠Cj，從而掩蓋了明文中的數(shù)據(jù)模式。加密時(shí)，當(dāng)Mi或Ci中發(fā)生一位錯(cuò)誤時(shí)，自此以后的密文全都發(fā)生錯(cuò)誤。這種現(xiàn)象稱為錯(cuò)誤傳播無界。解密時(shí)也是錯(cuò)誤傳播無界。2、密文反饋鏈接模式（CBC）①明密文鏈接方式錯(cuò)誤傳播無界的缺點(diǎn)：當(dāng)磁盤發(fā)生一點(diǎn)損壞時(shí)將導(dǎo)致整個(gè)文件無法解密。錯(cuò)誤傳播無界的優(yōu)點(diǎn)：可用于數(shù)據(jù)完整性、真實(shí)性認(rèn)證。明密文鏈接方式具有加解密錯(cuò)誤傳播無界的特性，而磁盤文件加密和通信加密通常希望解密錯(cuò)誤傳播有界，這時(shí)可采用密文鏈接方式。②密文鏈接方式（CiphertextBlockChaining）設(shè)明文M=（M1，M2，…，Mn）, 密鑰為K，密文C=(C1，C2，…，Cn),其中E（Mi⊕Z，K），i=1E（Mi⊕Ci-1，K）,i=2,…,n加密：錯(cuò)誤傳播無界解密時(shí)：錯(cuò)誤傳播有界D（Ci，K）⊕Z，i=1D（Ci，K）⊕Ci-1,i=2,…,nCi-1發(fā)生了錯(cuò)誤，則只影響Mi-1和Mi發(fā)生錯(cuò)誤，其余不錯(cuò)，因此錯(cuò)誤傳播有界。缺點(diǎn)也是要求數(shù)據(jù)的長度是密碼分組長度的整數(shù)倍，否則最后一個(gè)數(shù)據(jù)塊將是短塊。3、輸出反饋模式(OFB)將一個(gè)分組密碼轉(zhuǎn)換為一個(gè)密鑰序列產(chǎn)生器。從而可以實(shí)現(xiàn)用分組密碼按流密碼的方式進(jìn)行加解密。如果分組密碼是安全的，則產(chǎn)生的密鑰序列也是安全的。加解密都沒有錯(cuò)誤傳播。適于加密冗余度較大的數(shù)據(jù)，如語音和圖象數(shù)據(jù)。為了提高速度可輸出最右邊的8位。但因無錯(cuò)誤傳播而對(duì)密文的篡改難以檢測(cè)。4、密碼反饋模式CFB（CipherFeedback）CFB模式也是用分組密碼產(chǎn)生密鑰序列。與OFB的不同是，把密文反饋到移位寄存器。加密時(shí)若明文錯(cuò)了一位，則影響相應(yīng)的密文錯(cuò)，這一錯(cuò)誤反饋到移位寄存器后將影響到后續(xù)的密鑰序列錯(cuò)，導(dǎo)致后續(xù)的密文都錯(cuò)。解密時(shí)若密文錯(cuò)了一位，則影響相應(yīng)的明文錯(cuò)，但密文的這一錯(cuò)誤反饋到移位寄存器后將影響到后續(xù)的密鑰序列錯(cuò)，導(dǎo)致后續(xù)的明文都錯(cuò)。因錯(cuò)誤傳播無界，可用于檢查發(fā)現(xiàn)對(duì)明密文的篡改。5、XCBC(ExtendedCipherBlockChainingEncryption)模式2000年美國學(xué)者JohnBlack和PhllipRogaway提出XCBC模式，作為CBC模式的擴(kuò)展，被美國政府采納作為標(biāo)準(zhǔn)。XCBC主要是解決了CBC要求明文數(shù)據(jù)的長度是密碼分組長度的整數(shù)倍的限制，可以處理任意長的數(shù)據(jù)。如果用分組密碼是安全的，則密鑰序列就是安全的。設(shè)明文M=（M1，M2，…，Mn-1，Mn），相應(yīng)的密文C=(C1，C2，…，Cn－1，Cn)，而Mn可能是短塊。使用3個(gè)密鑰K1，K2，K3進(jìn)行加密。使用填充函數(shù)Pad（X）對(duì)短塊數(shù)據(jù)進(jìn)行填充。填充函數(shù)Pad（X）定義如下：X，當(dāng)X不是短塊；X10…0，當(dāng)X是短塊。經(jīng)填充函數(shù)Pad（X）填充后的數(shù)據(jù)塊一定是標(biāo)準(zhǔn)塊。令Z＝0，以Z作為初始化向量。加密過程如下：E（Mi⊕Z，K1），i=1E（Mi⊕Ci-1，K1）,i=2,…,n－1E（Mn⊕Cn-1⊕K2，K1），當(dāng)Mn不是短塊；E（PAD（Mn）⊕Cn-1⊕K3，K1），當(dāng)Mn是短塊。XCBC與CBC區(qū)別：CBC要求最后一個(gè)數(shù)據(jù)塊是標(biāo)準(zhǔn)塊，不是短塊。XCBC既允許最后一個(gè)數(shù)據(jù)塊是標(biāo)準(zhǔn)塊，也允許是短塊。最后一個(gè)數(shù)據(jù)塊的加密方法與CBC不同。因?yàn)橛刑畛?，需要傳輸填充長度信息。XCBC模式的主要優(yōu)點(diǎn)：可以處理任意長度的數(shù)據(jù)。適于計(jì)算產(chǎn)生檢測(cè)數(shù)據(jù)完整性的消息認(rèn)證碼MAC。6、CTR（CounterModeEncryption）模式CTR模式是Diffie和Hellman于1979年提出的，在征集AES工作模式的活動(dòng)中由California大學(xué)的PhillipRogaway等人的推薦。設(shè)T1，T2，…，Tn-1，Tn是一給定的計(jì)數(shù)序列，M1，M2，…，Mn-1，Mn是明文，其中M1，M2，…，Mn-1是標(biāo)準(zhǔn)塊，Mn的可能是標(biāo)準(zhǔn)塊，也可能是短塊。設(shè)其長度等于u，u小于等于分組長度。CTR的工作模式的加密過程如下：Oi＝E（Ti，K），i=1,2,…,n.Ci＝Mi⊕Oi，i=1,2,…,n-1.Cn＝Mn⊕MSBu（On）.其中MSBu（On）表示On中的高u位。CTR的工作模式的解密過程如下：Oi＝E（Ti，K），i=1,2,…,n.Mi＝Ci⊕Oi，i=1,2,…,n-1.Mn＝Cn⊕MSBu（On）.CTR的工作模式的優(yōu)點(diǎn)：CTR模式的優(yōu)點(diǎn)是安全、高效、可并行、適合任意長度的數(shù)據(jù)；Oi的計(jì)算可預(yù)處理高速進(jìn)行；加解密過程僅涉及加密運(yùn)算，不涉及解密運(yùn)算，因此不用實(shí)現(xiàn)解密算法。適合隨機(jī)存儲(chǔ)數(shù)據(jù)的解密。CTR模式的缺點(diǎn)是沒有錯(cuò)誤傳播，因此不易確保數(shù)據(jù)完整性。三、短塊加密分組密碼一次只能對(duì)一個(gè)固定長度的明文（密文）塊進(jìn)行加（解）密。稱長度小于分組長度的數(shù)據(jù)塊為短塊。必須采用合適的技術(shù)解決短塊加密問題。短塊處理技術(shù)：1、填充技術(shù)2、密文挪用技術(shù)3、序列加密1、填充技術(shù)用無用的數(shù)據(jù)填充短塊，使之成為標(biāo)準(zhǔn)塊。為了確保加密強(qiáng)度，填充數(shù)據(jù)應(yīng)是隨機(jī)的。但是收信者如何知道哪些數(shù)字是填充的呢？這就需要增加指示信息，通常用最后8位作為填充指示符。填充法適于通信加密而不適于文件和數(shù)據(jù)庫加密。2、密文挪用技術(shù)密文挪用法也需要指示挪用位數(shù)的指示符，否則收信者不知道挪用了多少位，從而不能正確解密。密文挪用加密短塊的優(yōu)點(diǎn)是不引起數(shù)據(jù)擴(kuò)展。缺點(diǎn)是解密時(shí)要先解密Cn、還原挪用后再解密Cn-1，從而使控制復(fù)雜。3、序列加密對(duì)于最后一塊短塊數(shù)據(jù)，直接使用密鑰K與短塊數(shù)據(jù)模2相加。序列加密方法的優(yōu)點(diǎn)是簡單。但是如果短塊太短，則加密強(qiáng)度不高。大作業(yè)以DES、AES或SMS4作為加密算法開發(fā)出文件加密軟件系統(tǒng)：具有文件加密和解密功能；具有加解密速度統(tǒng)計(jì)功能；采用密文反饋鏈接和密文挪用短塊處理技術(shù)；具有較好的人機(jī)界面。復(fù)習(xí)題①計(jì)算機(jī)數(shù)據(jù)加密有些什么特殊問題？②分析CBC和XCBC工作模式的加解密錯(cuò)誤傳播情況。③為什么說填充法不適合計(jì)算機(jī)文件和數(shù)據(jù)庫加密應(yīng)用？④密文挪用方法有什么優(yōu)缺點(diǎn)？

第七講序列密碼一、序列密碼的基本概念①明文、密文、密鑰以位（字符）為單位加解密；②模型③人們用序列密碼模仿“一次一密”密碼；④加密運(yùn)算最簡單，而且是對(duì)合運(yùn)算；⑤安全取決于密鑰序列產(chǎn)生算法；⑥理論和技術(shù)都十分成熟；⑦核心密碼的主流密碼。1、序列密碼的分類①同步序列密碼（SynchronousStreamCipher）密鑰序列產(chǎn)生算法與明文無關(guān)，所產(chǎn)生的密鑰序列也與明文無關(guān)。在通信過程中，通信的雙方必須保持精確的同步，收方才能正確解密，如果失步收方將不能正確解密。例如，如果通信中丟失或增加了一個(gè)密文字符，則收方的解密將一直錯(cuò)誤。設(shè)密文失步c=c1,c3,c4,…cn-1,cn（c2丟失）⊕k=k1,k2,k3,…kn-1,kn（密鑰正確）m=m1,×,×,…×,×（m1后的明文全錯(cuò)）對(duì)失步的敏感性，使我們能夠容易檢測(cè)插入、刪除、重播等主動(dòng)攻擊。另一個(gè)優(yōu)點(diǎn)是沒有錯(cuò)誤傳播，當(dāng)通信中某些密文字符產(chǎn)生了錯(cuò)誤（不是插入和刪除），只影響相應(yīng)字符的解密，不影響其它字符。注意：錯(cuò)誤與失步是不同的概念！設(shè)密文錯(cuò)誤c=c1,c2,c3,…cn-1,cn（c2錯(cuò)）⊕k=k1,k2,k3,…kn-1,kn（密鑰正確）m=m1,×,m3,…mn-1,mn（僅m2錯(cuò)）②自同步序列密碼（Self-SynchronousStreamCipher）密鑰序列產(chǎn)生算法與明文（密文）相關(guān)，則所產(chǎn)生的密鑰序列與明文（密文）相關(guān)。設(shè)密鑰序列產(chǎn)生器具有n位存儲(chǔ)，則加密時(shí)一位密文錯(cuò)誤將影響后面連續(xù)n個(gè)密文錯(cuò)誤。在此之后恢復(fù)正確。解密時(shí)一位密文錯(cuò)誤也將影響后面連續(xù)n個(gè)明文錯(cuò)。在此之后恢復(fù)正確。加解密會(huì)造成錯(cuò)誤傳播。在錯(cuò)誤過去之后恢復(fù)正確。二、線性移位寄存器序列密碼1、線性移位寄存器（LinearSiftRegistor）s0，s1，...，sn-1組成左移移位寄存器，并稱每一時(shí)刻移位寄存器的取值為一個(gè)狀態(tài)。移位寄存器的輸出同時(shí)要送入sn-1，其值要通過函數(shù)F(s0,s1,...,sn-1)計(jì)算產(chǎn)生。稱函數(shù)F(s0,s1,...,sn-1)為反饋函數(shù)。如果反饋函數(shù)F(s0,s1,...,sn-1)是s0,s1,...,sn-1的線性函數(shù)，則稱為線性移位寄存器，否則稱為非線性移位寄存器。設(shè)F(s0,s1,...,sn-1)為線性函數(shù)，則可寫成F(s0,s1,...,sn-1)=g0s0+g1s1+,...,+gn-1sn-1其中，g0,g1,...,gn-1為反饋系數(shù)。在二進(jìn)制的情況下，式中的+即為⊕，反饋系數(shù)gi∈GF(2)，如果gi=0，則表示式中的gisi項(xiàng)不存在，因此表示si不連接。同理，gi=1表示si連接。故gi的作用相當(dāng)于一個(gè)開關(guān)。形式地，用xi與si相對(duì)應(yīng)，則根據(jù)反饋函數(shù)可導(dǎo)出一個(gè)文字x的多項(xiàng)式：g(x)=gnxn+gn-1xn-1+,...,+g1x+g0稱g(x)為線性移位寄存器的連接多項(xiàng)式。與圖對(duì)照可知，gn=g0=1。否則，若gn=0則輸出不反饋到sn-1，若g1=0則s0不起作用，應(yīng)將其去掉。n級(jí)線性移位寄存器最多有2n個(gè)不同的狀態(tài)。若其初始狀態(tài)為零，則其后續(xù)狀態(tài)恒為零。若其初始狀態(tài)不為零，則其后續(xù)狀態(tài)也不為零。因此，n級(jí)線性移位寄存器的狀態(tài)周期≤2n–1，其輸出序列的周期≤2n–1。只要選擇合適的連接多項(xiàng)式便可使線性移位寄存器的輸出序列周期達(dá)到最大值2n–1，并稱此時(shí)的輸出序列為最大長度線性移位寄存器輸出序列，簡稱為m序列。僅當(dāng)連接多項(xiàng)式g(x)為本原多項(xiàng)式時(shí)，其線性移位寄存器的輸出序列為m序列。設(shè)f(x)為GF（2）上的多項(xiàng)式，使f(x)|xp－1的最小正整數(shù)p稱為f(x)的周期。如果f(x)的次數(shù)為n，且其周期為2n－1，則稱f(x)為本原多項(xiàng)式。已經(jīng)證明，對(duì)于任意的正整數(shù)n，至少存在一個(gè)n次本原多項(xiàng)式。而且有有效的產(chǎn)生算法。舉例：設(shè)g(x)=x4+x+1，g(x)為本原多項(xiàng)式，以其為連接多項(xiàng)式的線性移位寄存器的輸出序列為100110101111000···，它是周期為24-1=15的m序列。m序列具有良好的隨機(jī)性：游程：稱序列中連續(xù)的i個(gè)1為長度等于i的1游程，同樣，稱序列中連續(xù)的i個(gè)0為長度等于i的0游程。①在一個(gè)周期內(nèi)，0和1出現(xiàn)的次數(shù)接近相等，即0出現(xiàn)的次數(shù)為2n-1-1，1出現(xiàn)的次數(shù)為2n-1；②將序列的一個(gè)周期首尾相接，其游程總數(shù)N=2n-1。③其中1游程和0游程的數(shù)目各占一半。當(dāng)n>2時(shí)，游程分布如下（1≤i≤n-2）：長為i的1游程有N/2i+1個(gè)；長為i的0游程有N/2i+1個(gè)；長為n-1的0游程有1個(gè)；長為n的1游程有1個(gè).④自相關(guān)函數(shù)反映一個(gè)周期內(nèi)平均每位的相同程度。2、線性移位寄存器序列密碼m序列具有良好的隨機(jī)性；50年代開始用作密鑰序列，并用于軍用。60年代發(fā)現(xiàn)其是不安全的。設(shè)m序列線性移位寄存器的狀態(tài)為S=（s0,s1,...,sn-1）T，下一狀態(tài)為S’=（s’0,s’1,...,s’n-1）T，其中s’0=s1s’1=s2...s’n-2=sn-1s’n-1=g0s0+g1s1+,...,+gn-1sn-1寫成矩陣形式：S’=HSmod2010...0s’0s0001...0s’1s1000...0000...1g0g1...gn-1s’n-1sn-1矩陣H稱為連接多項(xiàng)式的伴侶矩陣。進(jìn)一步假設(shè)攻擊者知道了一段長2n位的明密文對(duì)，即已知：M=m1,m2,...,m2nC=c1,c2,...,c2n于是可求出一段長2n位的密鑰序列，K=k1,k2,...,k2n，其中ki=mi⊕ci=mi⊕(mi⊕ki)。由此可以推出線性移位寄存器連續(xù)n+1個(gè)狀態(tài)：S1=（k1,k2,...,kn）TS2=（k2,k3,...,kn+1）T…Sn+1=（kn+1,kn+2,...,k2n）T作矩陣X=（S1,S2,...,Sn）TY=（S2,S3,...,Sn+1）T根據(jù)S’=HSmod2，有S2=HS1S3=HS2...Sn+1=HSn于是，Y=HXmod2因?yàn)閙序列的線性移位寄存器連續(xù)n個(gè)狀態(tài)向量彼此線性無關(guān)，因此X矩陣為滿秩矩陣，故存在逆矩陣X-1，于是H=YX-1mod2求出H矩陣，便確定出連接多項(xiàng)式g(x)，從而完全確定線性移位寄存器的結(jié)構(gòu)。例：m序列100110101111000連續(xù)4個(gè)狀態(tài)1001，0011，0110，1101線性無關(guān)求逆矩陣X-1的計(jì)算復(fù)雜度為O（n3）。一般，對(duì)于n=1000的線性移位寄存器序列密碼，用每秒100萬次的計(jì)算機(jī)，一天之內(nèi)便可破譯。三、非線性序列密碼線性移位寄存器序列密碼在已知明文攻擊下是可破譯的，可破譯的根本原因在于線性移位寄存器序列是線性的，這一事實(shí)促使人們向非線性領(lǐng)域探索。目前研究得比較充分的方法：①非線性移位寄存器序列②對(duì)線性移位寄存器序列進(jìn)行非線性組合③利用非線性分組碼產(chǎn)生非線性序列①非線性移位寄存器序列令反饋函數(shù)f(s0,s1,...,sn-1)為非線性函數(shù)便構(gòu)成非線性移位寄存器，其輸出序列為非線性序列。稱輸出序列的周期達(dá)到最大值2n的非線性移位寄存器序列為M序列。M序列的0，1分布和游分布是均勻的，而且周期最大。非線性移位寄存器反饋函數(shù)的數(shù)量極大。GF（2）上的n級(jí)移位寄存器共有2n個(gè)狀態(tài)，因此共有？種不同的反饋函數(shù)，其中線性反饋函數(shù)只有2n-1種，其余均為非線性。顯然，非線性移位寄存器的空間極大！例：令n=3，f(s0,s1,s2)=s0⊕s2⊕1⊕s1s2，由于與運(yùn)算為非線性運(yùn)算，故反饋函數(shù)為非線性反饋函數(shù)，其輸出序列為10110100...，為M序列。②對(duì)線性移位寄存器序列進(jìn)行非線性組合非線性移位寄存器序列的研究比較困難，但人們對(duì)線性移位寄存器序列的研究卻比較充分和深入。于是人們想到，利用線性移位寄存器序列設(shè)計(jì)容易、隨機(jī)性好等優(yōu)點(diǎn)，對(duì)一個(gè)或多個(gè)線性移位寄存器序列進(jìn)行非線性組合可以獲得良好的非線性序列。在這里用線性移位寄存器作為驅(qū)動(dòng)源來驅(qū)動(dòng)非線性電路產(chǎn)生非線性序列。其中用線性移位寄存器序列來確保所產(chǎn)生序列的長周期和均勻性，用非非線性電路來確保輸出序列的非線性和其它密碼性質(zhì)。通常稱這里的非線性電路為前饋電路，稱這種輸出序列為前饋序列。對(duì)多個(gè)LSR進(jìn)行非線性組合四、RC4序列密碼RC4序列密碼是美國RSA數(shù)據(jù)安全公司設(shè)計(jì)的一種序列密碼。RSA數(shù)據(jù)安全公司將其收集在加密工具軟件BSAFE中。最初并沒有公布RC4的算法。人們通過對(duì)軟件進(jìn)行逆向分析得到了算法。在這種情況下RSA數(shù)據(jù)安全公司于1997年公布了RC4密碼算法。密鑰40位的RC4，通過Internet32小時(shí)攻破。RC4密碼與基于移位寄存器的序列密碼不同。它是一種基于非線性數(shù)據(jù)表變換的序列密碼。它以一個(gè)足夠大的數(shù)據(jù)表為基礎(chǔ)，對(duì)表進(jìn)行非線性變換，產(chǎn)生非線性的密鑰序列。RC4使用256個(gè)字節(jié)的S表和兩個(gè)指針（I和J）。S表的值S0,S1,…，S255是0,1,…，255的一個(gè)排列。I和J的初值為0。我們把RC4算法看成一個(gè)有限狀態(tài)自動(dòng)機(jī)。把S表和I、J指針的具體取值稱為RC4的一個(gè)狀態(tài)：T=<S0,S1，…，S255,I,J>對(duì)狀態(tài)T進(jìn)行非