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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、對明文進行加密、對密文進行解密的密碼體制。其技術、思想以及破譯方法雖然很簡單，但是反映了密碼設計和破譯的思想，是學習密碼學的基本入口，對于理解、設計和分析現(xiàn)代密碼仍然具有借鑒的價值。兩個基本方法 置換（Permutation）:保持明文中所有字母不變，利用置換打亂明文字母的位置和次序，即在消息內變換字母的位置。 代替（Substitution）:明文中每一個字符被替換成密文中的另外一個字符。接收者對密文進行逆替換就恢復出明文來。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) 單表代替密碼：將明文的一個字符用相應的一個密文字符代替。 多表代替密碼：單個明文字符可以映射成幾個密文字符之一，由多個單表代替密碼構成，例如，可能有4個不同的簡單代替密碼。例如A可能對應于5、13、25或56，“B”可

18、能對應于7、19、31或42，等等。 多字母代替密碼：字符塊被成組的加密，例如“ABA”可能對應于“RTQ”，ABB可能對應于“SLL”等。 單表密碼（愷撒密碼,乘積密碼,仿射密碼） 多表密碼(維吉尼亞） 多字母代換密碼 (希爾密碼）(1) 同余理論1)模運算:即求余,記為mod（即5+10000除以7的余數(shù)）即：10000天后是星期二 2)同余定義:m正整數(shù),m除a,b余數(shù)同,稱 a,b為模m同余,記為a=b mod m例:假設今天是星期五，請問10000天后是星期幾？3)同余滿足自反性、對稱性、傳遞性； 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)同余的性質：若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對于模n互為逆元。 (用Euclid算法求乘法逆元) 例：152 mod 12=(3*3)mod 12=9注：若a和n互素，則a在模n下有逆元。(2)單表密碼1)愷撒密碼(加法密碼、移位密碼)明文 26個字母

20、密文 26個字母加密 Ek(m)=m+k=c mod n (n=26)當k=3,每個字母使用其后第3個(循環(huán))代替明文 meet me after class密文 PHHW PH DIWHU FODVV解密 Dk(c)=c-k=m mod n密鑰量為n-1應用同余性質（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ù)的個數(shù)，n1。 例：(3)= (4) = (6) =2，(5)=4，(7) =6 ,(12)=4 密鑰量為Euler函數(shù)(n)-1應用同余性質（2）以

21、及逆元的定義加密:選取k1，k2兩個參數(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年）明文中各個字母出現(xiàn)的統(tǒng)計概率字母組合概率雙字母組合：th、he、in、er三字母組合：the、ing、and單表代替無法抵御統(tǒng)計分析攻擊！(2) 多表密碼（維吉尼亞）多表密碼是利用多個單表代替密碼構成的密碼體制。它在對明文進行加密的過程中依照密鑰的指示輪流使用多個單表代替密碼。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 存在等價于gcd|k|，261對于二階矩陣 ，|A|例： ，|A|=27=27*1=1mod 26,則 注：a+b=0 mod 26, 即 a=-b mod 26 Hill密碼舉例密匙產(chǎn)生：首先決定所用矩陣的大小，譬如是22, 其中E的行列式值detE必須與26互質，否則不存在E的反矩陣。明文m=Hill 矩陣形態(tài)加密過程：密文c=pbwz 解密矩陣計算加密矩陣的反矩陣，再進行模運算（mod 26），得解密矩陣 解密過程 用唯密文攻擊法分析多字母代換密碼如Hill密碼是比較困難的。Hill密碼可抵抗頻率分析，不能抵抗已知明文攻

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

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

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

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

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

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

31、說明典型的分組密碼結構:Feistel結構(1973年）置換:代替過程完成后，再交換左、右兩半數(shù)據(jù)。乘積密碼:每輪結構相同,但以不同的子密鑰Ki作為參數(shù)。代替:每輪中右半數(shù)據(jù)被作用于輪函數(shù)F后，再與左半數(shù)據(jù)進行異或運算。是Shannon提出的代替置換網(wǎng)絡（substitution-permutation network, SPN）的特有形式。特點是每次只處理明文的一半。算法說明Ki：每級密鑰不同 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=兩個子塊左右交換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）分組長度n足夠大。（2）密鑰量足夠大。（3）循環(huán)次數(shù)越多越安全。（4）輪函數(shù)變換足夠復雜。（5）子密鑰產(chǎn)生算法。（6）快速軟件實現(xiàn)。（4）算法容易分析，這樣可容易發(fā)現(xiàn)弱點，并給出對其的更高安全級別的保障措施。Feistel

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

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

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

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

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

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