第三章對稱密碼體制

1、1 第三章第三章 對稱密碼體制對稱密碼體制3.1 3.1 分組密碼原理分組密碼原理3.2 3.2 數(shù)據(jù)加密標準（數(shù)據(jù)加密標準（DESDES）3.3 3.3 高級加密標準高級加密標準(AES)(AES)3.4 3.4 分組密碼的工作模式分組密碼的工作模式23.1 3.1 分組密碼原理分組密碼原理對稱密碼體制根據(jù)對明文加密方式的不同分為對稱密碼體制根據(jù)對明文加密方式的不同分為分組密碼分組密碼和和流密碼流密碼。分組密碼：分組密碼：按一定長度（如按一定長度（如64bit64bit，128bit128bit）對）對明文進行分組，然后以組為單位采用同樣的密明文進行分組，然后以組為單位采用同樣的密鑰進行加鑰

2、進行加/ /解密；解密；流密碼：流密碼：不進行分組，而是按位進行加不進行分組，而是按位進行加/ /解密解密無記憶元件無記憶元件內(nèi)部記憶元件kkx1xmymy1y1x1分組密碼流密碼3 分組密碼對不同的組采用同樣的密鑰k進行加/解密。設(shè)密文組為y=y1y2ym，則對明文組x=x1x2 xm用密鑰k加密可得到y(tǒng)=ek(x1)ek(x2) ek(xm)。 流密碼的基本思想是利用密鑰k產(chǎn)生一個密鑰流z=z0z1 ，并使用如下規(guī)則加密明文串x=x0 x1 x2 ，y=y0y1y2= ez0(x0)ez1(x1) ez2(x2) 。密鑰流由密鑰流發(fā)生器f產(chǎn)生。 分組密碼與流密碼的區(qū)別就在于記憶性。43.1

3、.1 3.1.1 分組密碼設(shè)計原理分組密碼設(shè)計原理 分組密碼是將明文消息分組密碼是將明文消息編碼表示后的數(shù)字編碼表示后的數(shù)字（簡（簡稱明文數(shù)字）序列稱明文數(shù)字）序列x0，x1， ，劃分成長度為，劃分成長度為n的組的組x=(x0,x1,xn-1)，每組分別在密鑰，每組分別在密鑰 k=(k0,k1,km-1)的控制下變換成等長的輸出數(shù)字（簡稱密文數(shù)字）的控制下變換成等長的輸出數(shù)字（簡稱密文數(shù)字）序列序列y=(y0,y1,yn-1) 。 5 分組密碼的算法應(yīng)滿足如下安全性和軟分組密碼的算法應(yīng)滿足如下安全性和軟/硬件實現(xiàn)的硬件實現(xiàn)的要求：要求：（1）分組長度足夠大，防止明文被窮舉攻擊。如）分組長度足夠

4、大，防止明文被窮舉攻擊。如n=64bit (DES) ，新的標準，新的標準n=128bit (AES) （2）密鑰空間足夠大，從而防止窮舉密鑰攻擊。同時，）密鑰空間足夠大，從而防止窮舉密鑰攻擊。同時，密鑰又不能太長，以利于密鑰管理，密鑰又不能太長，以利于密鑰管理，DES采用采用56bit有效密鑰，現(xiàn)在不夠長，今后采用有效密鑰，現(xiàn)在不夠長，今后采用128bit是足夠安是足夠安全的。全的。（3）由密鑰確定的算法要足夠復(fù)雜，充分實現(xiàn)明文與）由密鑰確定的算法要足夠復(fù)雜，充分實現(xiàn)明文與密文的擴散和混淆，沒有簡單的關(guān)系可循。密文的擴散和混淆，沒有簡單的關(guān)系可循。 （4）軟件實現(xiàn)的要求：盡量使用適合編程的子

5、塊和簡）軟件實現(xiàn)的要求：盡量使用適合編程的子塊和簡單的運算單的運算（5）硬件實現(xiàn)的要求：加密和解密應(yīng)具有相似性。）硬件實現(xiàn)的要求：加密和解密應(yīng)具有相似性。6兩個基本設(shè)計方法ShannonShannon稱之為理想密碼系統(tǒng)，稱之為理想密碼系統(tǒng)，密文的所有統(tǒng)計特性密文的所有統(tǒng)計特性都與所使用的密鑰獨立。都與所使用的密鑰獨立。 擴散（擴散（Diffusion):Diffusion):明文的統(tǒng)計結(jié)構(gòu)被擴散消失到明文的統(tǒng)計結(jié)構(gòu)被擴散消失到密文的統(tǒng)計特性中密文的統(tǒng)計特性中, ,使得明文和密文之間的統(tǒng)計關(guān)系使得明文和密文之間的統(tǒng)計關(guān)系盡量復(fù)雜。使得明文的每個比特影響到密文許多比特盡量復(fù)雜。使得明文的每個比特影

6、響到密文許多比特的取值，即每個密文比特被許多明文比特影響。的取值，即每個密文比特被許多明文比特影響。 混亂混亂(confusion)(confusion)：使得密文的統(tǒng)計特性與密鑰的：使得密文的統(tǒng)計特性與密鑰的取值之間的關(guān)系盡量復(fù)雜。取值之間的關(guān)系盡量復(fù)雜。擴散和混淆的目的都是為了挫敗推出密鑰的嘗試，擴散和混淆的目的都是為了挫敗推出密鑰的嘗試，從而從而抗統(tǒng)計分析抗統(tǒng)計分析。73.1.2 3.1.2 分組密碼的一般結(jié)構(gòu)分組密碼的一般結(jié)構(gòu)分組密碼的一般結(jié)構(gòu)可以分為兩種：分組密碼的一般結(jié)構(gòu)可以分為兩種：FeistelFeistel網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)和結(jié)構(gòu)和SPSP網(wǎng)絡(luò)結(jié)構(gòu)。網(wǎng)絡(luò)結(jié)構(gòu)。FeistelFeis

7、tel網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)FeistelFeistel網(wǎng)絡(luò)結(jié)構(gòu)如圖所示：網(wǎng)絡(luò)結(jié)構(gòu)如圖所示：DESDES采用的是采用的是FeistelFeistel網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)結(jié)構(gòu)加密: Li = Ri-1; Ri = Li-1F(Ri-1,Ki)解密: Ri-1 = Li，Li-1 = RiF(Ri-1,Ki)= RiF(Li,Ki)82. SP2. SP網(wǎng)絡(luò)結(jié)構(gòu)是分組密碼的另一種重要結(jié)構(gòu)，網(wǎng)絡(luò)結(jié)構(gòu)是分組密碼的另一種重要結(jié)構(gòu)，AESAES等重要算法采用的是此結(jié)構(gòu)。等重要算法采用的是此結(jié)構(gòu)。9DESDES（Data Encryption StandardData Encryption Standard）是迄今為止使

8、用最為廣泛的加）是迄今為止使用最為廣泛的加密算法。密算法。DESDES的產(chǎn)生的產(chǎn)生-i-i 1973 1973年年5 5月月1313日日, NBS(, NBS(美國國家標準局美國國家標準局) )開始公開征集標準加密算開始公開征集標準加密算法法, ,并公布了它的設(shè)計要求并公布了它的設(shè)計要求: :(1)(1)算法必須提供高度的安全性；算法必須提供高度的安全性；(2)(2)算法必須有詳細的說明算法必須有詳細的說明, ,并易于理解；并易于理解；(3)(3)算法的安全性取決于密鑰算法的安全性取決于密鑰, ,不依賴于算法；不依賴于算法；(4)(4)算法適用于所有用戶；算法適用于所有用戶；(5)(5)算法適

9、用于不同應(yīng)用場合；算法適用于不同應(yīng)用場合；(6)(6)算法必須高效、經(jīng)濟；算法必須高效、經(jīng)濟；(7)(7)算法必須能被證實有效；算法必須能被證實有效；(8)(8)算法必須是可出口的；算法必須是可出口的；3.2 3.2 數(shù)據(jù)加密標準（數(shù)據(jù)加密標準（DESDES）10DESDES的產(chǎn)生的產(chǎn)生-ii-ii 1974 1974年年8 8月月2727日日, NBS, NBS開始第二次征集開始第二次征集,IBM,IBM提交了算提交了算法法LUCIFERLUCIFER，該算法由，該算法由IBMIBM的工程師在的工程師在1971-19721971-1972年研年研制制 1975 1975年年3 3月月1717

10、日日, NBS, NBS公開了全部細節(jié)公開了全部細節(jié) 1976 1976年年,NBS,NBS指派了兩個小組進行評價指派了兩個小組進行評價 1976 1976年年1111月月2323日，采納為聯(lián)邦標準，批準用于非軍日，采納為聯(lián)邦標準，批準用于非軍事場合的各種政府機構(gòu)事場合的各種政府機構(gòu) 1977 1977年年1 1月月1515日日, ,被正式批準為美國聯(lián)邦信息處理標被正式批準為美國聯(lián)邦信息處理標準，即準，即FIPS PUB 46FIPS PUB 46，同年，同年7 7月月1515日開始生效。日開始生效。11DES的應(yīng)用 1979 1979年，美國銀行協(xié)會批準使用年，美國銀行協(xié)會批準使用 1980

11、 1980年，美國國家標準局贊同年，美國國家標準局贊同DESDES作為私人使用的標作為私人使用的標準準, ,稱之為稱之為DEADEA（ANSI X.392ANSI X.392） 19831983年，國際化標準組織年，國際化標準組織ISOISO贊同贊同DESDES作為國際標準，作為國際標準，稱之為稱之為DEA-1DEA-1 該標準規(guī)定每五年審查一次，計劃十年后采用新標準該標準規(guī)定每五年審查一次，計劃十年后采用新標準 最近的一次評估是在最近的一次評估是在19941994年年1 1月，已決定月，已決定19981998年年1212月月以后，以后，DESDES將不再作為聯(lián)邦加密標準。將不再作為聯(lián)邦加密標

12、準。新的美國聯(lián)邦加密標準稱為高級加密標準新的美國聯(lián)邦加密標準稱為高級加密標準AES(Advanced Encryption Standard)AES(Advanced Encryption Standard)123.2.1 DES描述描述DES是采用將明文按是采用將明文按64bit分組，密鑰長度為分組，密鑰長度為64bit,其中每其中每8位有一位奇偶校驗位，實際密鑰的有效長位有一位奇偶校驗位，實際密鑰的有效長度為度為56bit,DES算法是公開的，其安全性依賴于密算法是公開的，其安全性依賴于密鑰的保密程度。鑰的保密程度。DES結(jié)構(gòu)框圖如圖：結(jié)構(gòu)框圖如圖：13141.1.初始置換初始置換IPIP

13、和初始逆置換和初始逆置換IPIP11152. 迭代變換迭代變換16 迭代變換是迭代變換是DESDES算法的核心部分，每算法的核心部分，每輪開始時將輸入的輪開始時將輸入的64bit64bit數(shù)據(jù)分成左、右數(shù)據(jù)分成左、右長度相等的兩部分，右半部分原封不動地長度相等的兩部分，右半部分原封不動地作為本輪輸出的作為本輪輸出的64bit64bit數(shù)據(jù)的左半部分，數(shù)據(jù)的左半部分，同時對右半部分進行一系列的變換，即用同時對右半部分進行一系列的變換，即用輪函數(shù)輪函數(shù)F F作用右半部分，然后將所得結(jié)果作用右半部分，然后將所得結(jié)果與輸入數(shù)據(jù)的左半部分進行逐位異或，最與輸入數(shù)據(jù)的左半部分進行逐位異或，最后將所得數(shù)據(jù)作

14、為本輪輸出的后將所得數(shù)據(jù)作為本輪輸出的64bit64bit數(shù)據(jù)數(shù)據(jù)的右半部分。的右半部分。 輪函數(shù)輪函數(shù)F F由選擇擴展運算由選擇擴展運算E E、與子密鑰、與子密鑰的異或運算、選擇壓縮運算的異或運算、選擇壓縮運算S S和置換和置換P P組成。組成。1718(1) (1) 選擇擴展運算選擇擴展運算將輸入的將輸入的32bit數(shù)據(jù)擴展為數(shù)據(jù)擴展為48bit的輸出數(shù)據(jù)，變換表如的輸出數(shù)據(jù)，變換表如下：下：可以看出可以看出1、4、5、8、9、12、13、16、17、20、21、24、25、28、29、32這這16個位置上的數(shù)據(jù)被讀了兩次。個位置上的數(shù)據(jù)被讀了兩次。19（2 2）與子密鑰的異或運算）與子密

15、鑰的異或運算與子密鑰的異或運算：將選擇擴展運算的與子密鑰的異或運算：將選擇擴展運算的48 48 bitbit數(shù)據(jù)與子密鑰數(shù)據(jù)與子密鑰Ki(48 bit)Ki(48 bit)進行異或運算。進行異或運算。（后面詳述）（后面詳述）20（3）選擇壓縮運算）選擇壓縮運算將輸入的將輸入的48bit數(shù)據(jù)從左至右分成數(shù)據(jù)從左至右分成8組，每組組，每組6bit。然后輸入。然后輸入8個個S盒，每個盒，每個S盒為一非線性代換，有盒為一非線性代換，有4bit輸出，如圖所示：輸出，如圖所示：212223S-Box 對每個盒，對每個盒，6 6比特輸入中的第比特輸入中的第1 1和第和第6 6比特組成比特組成的二進制數(shù)確定的

16、行，中間的二進制數(shù)確定的行，中間4 4位二進制數(shù)用來位二進制數(shù)用來確定的列。相應(yīng)行、列位置的十進制數(shù)的確定的列。相應(yīng)行、列位置的十進制數(shù)的4 4位位二進制數(shù)表示作為輸出。例如的輸入為二進制數(shù)表示作為輸出。例如的輸入為101001101001，則行數(shù)和列數(shù)的二進制表示分別是則行數(shù)和列數(shù)的二進制表示分別是1111和和01000100，即表中即表中3 3行和表中行和表中4 4列，表中列，表中3 3行和表中行和表中4 4列的十列的十進制數(shù)為進制數(shù)為3 3，用，用4 4位二進制數(shù)表示為位二進制數(shù)表示為00110011，所以，所以的輸出為的輸出為00110011。24（4）置換）置換P2526273.2.

17、2 DES問題討論1.S盒的安全問題有人認為有人認為s s盒可能存在陷門，但至今沒有跡象表明盒可能存在陷門，但至今沒有跡象表明s s盒盒中存在陷門。中存在陷門。2.密鑰長度 關(guān)于關(guān)于DES算法的另一個最有爭議的問題就是擔心實際算法的另一個最有爭議的問題就是擔心實際56比特的密鑰長度不足以抵御窮舉式攻擊，因為密鑰量比特的密鑰長度不足以抵御窮舉式攻擊，因為密鑰量只有只有2 2565610101717個。個。 早在早在1977年，年，Diffie和和Hellman已建議制造一個每秒能已建議制造一個每秒能測試測試100萬個密鑰的萬個密鑰的VLSI芯片。每秒測試芯片。每秒測試100萬個密鑰萬個密鑰的機器

18、大約需要一天就可以搜索整個密鑰空間。他們估的機器大約需要一天就可以搜索整個密鑰空間。他們估計制造這樣的機器大約需要計制造這樣的機器大約需要2000萬美元。萬美元。28 在CRYPTO93上，Session和Wiener給出了一個非常詳細的密鑰搜索機器的設(shè)計方案，這個機器基于并行運算的密鑰搜索芯片，16次加密能同時完成。此芯片每秒能測試5000萬個密鑰，用5760個芯片組成的系統(tǒng)需要花費10萬美元，它平均用1.5天左右就可找到DES密鑰。 1997年1月28日，美國的RSA數(shù)據(jù)安全公司在RSA安全年會上公布了一項“秘密密鑰挑戰(zhàn)”競賽，其中包括懸賞1萬美元破譯密鑰長度為56比特的DES。美國克羅拉

19、多洲的程序員Verser從1997年2月18日起，用了96天時間，在Internet上數(shù)萬名志愿者的協(xié)同工作下，成功地找到了DES的密鑰，贏得了懸賞的1萬美元。29 1998年7月電子前沿基金會（EFF）使用一臺25萬美元的電腦在56小時內(nèi)破譯了56比特密鑰的DES。 1999年1月RSA數(shù)據(jù)安全會議期間，電子前沿基金會用22小時15分鐘就宣告破解了一個DES的密鑰。301.兩重兩重DES3.2.3 DES的變形的變形雙重DES密鑰長度為112bit,密碼強度似乎增強了一倍，但問題并非如此。雙重DES易受中途攻擊C=EK2(EK1(P)P=DK1(DK2(C)312.三重三重DES（以被廣泛采

20、用）（以被廣泛采用）優(yōu)點：優(yōu)點：能對付中途攻擊能對付中途攻擊。密鑰長度為。密鑰長度為168bit 32AES背景-i 1997年4月15日，（美國）國家標準技術(shù)研究所（ NIST ） 發(fā)起征集高級加密標準（ Advanced Encryption Standard）AES的活動，活動目的是確定一個非保密的、可以公開技術(shù)細節(jié)的、全球免費使用的分組密碼算法，作為新的數(shù)據(jù)加密標準。 1997年9月12日，美國聯(lián)邦登記處公布了正式征集AES候選算法的通告。作為進入AES候選過程的一個條件，開發(fā)者承諾放棄被選中算法的知識產(chǎn)權(quán)。對AES的基本要求是：比三重DES快、至少與三重DES一樣安全、數(shù)據(jù)分組長度為

21、128比特、密鑰長度為128/192/256比特。3.3 高級加密標準高級加密標準AES33AES背景-ii 1998年8月12日，在首屆AES會議上指定了15個候選算法。 1999年3月22日第二次AES會議上，將候選名單減少為5 個， 這5 個算法是RC6 ， Rijndael ，SERPENT，Twofish和MARS。 2000年4月13日，第三次AES會議上，對這5個候選算法的各種分析結(jié)果進行了討論。 2000年10月2日，NIST宣布了獲勝者Rijndael算法， 2001 年11 月出版了最終標準FIPSPUB197。34Rijndael簡介 不屬于Feistel結(jié)構(gòu) 加密、解密

22、相似但不對稱 支持128/32=Nb數(shù)據(jù)塊大小 支持128/192/256(/32=Nk)密鑰長度 有較好的數(shù)學(xué)理論作為基礎(chǔ) 結(jié)構(gòu)簡單、速度快35 輪數(shù)輪數(shù)r與與Nb和和Nk r Nb=4 Nb=6Nb=8 Nk=4 10 12 14 Nk=6 12 12 14 Nk=8 14 14 14AES參數(shù)參數(shù)36SP網(wǎng)絡(luò)結(jié)構(gòu)在這種密碼的每一輪中，輪輸入首先被一個由子密鑰控制的可逆函數(shù)S作用，然后再對所得結(jié)果用置換（或可逆線性變換）P作用。S和P分別被稱為混亂層和擴散層，主要起混亂和擴散作用。37AES算法結(jié)構(gòu)-i AES算法的輪變換中沒有Feistel結(jié)構(gòu)，輪變換是由三個不同的可逆一致變換組成，稱之

23、為層， 線性混合層：確保多輪之上的高度擴散。 非線性層：具有最優(yōu)最差-情形非線性性的S-盒的并行應(yīng)用。 密鑰加層：輪密鑰簡單地異或到中間狀態(tài)上。38AES算法結(jié)構(gòu)-ii3940電子密碼本電子密碼本 ECB (electronic codebook mode)ECB (electronic codebook mode)密碼分組鏈接密碼分組鏈接 CBC (cipher block chaining)CBC (cipher block chaining)密碼反饋密碼反饋 CFB (cipher feedback)CFB (cipher feedback)輸出反饋輸出反饋 OFB (output fe

24、edback)OFB (output feedback)3.4 3.4 分組密碼的工作模式分組密碼的工作模式分組密碼在加密時明文的長度是固定的。而實用中待加密消息分組密碼在加密時明文的長度是固定的。而實用中待加密消息的數(shù)據(jù)量是不定的，數(shù)據(jù)格式也可能是多種多樣的，為了能在的數(shù)據(jù)量是不定的，數(shù)據(jù)格式也可能是多種多樣的，為了能在各種應(yīng)用場合安全地使用分組密碼，通常對不同的使用目的運各種應(yīng)用場合安全地使用分組密碼，通常對不同的使用目的運用不同的工作模式。用不同的工作模式。分組密碼的工作模式：就是以該分組密碼為基礎(chǔ)構(gòu)造分組密碼的工作模式：就是以該分組密碼為基礎(chǔ)構(gòu)造的一個密碼系統(tǒng)。的一個密碼系統(tǒng)。41iK

25、iiKiC = E (P) P = D(C) 電子密碼本電子密碼本ECB3.4.1 電碼本模式（電碼本模式（ECB)42ECB的特點的特點ECBECB用于短數(shù)據(jù)（如加密密鑰）是非常理想，長消息不夠安全用于短數(shù)據(jù)（如加密密鑰）是非常理想，長消息不夠安全簡單、有效簡單、有效可以并行實現(xiàn)可以并行實現(xiàn)不能隱藏明文的模式信息不能隱藏明文的模式信息 相同明文相同明文生成生成相同密文，相同密文，同樣信息多次出現(xiàn)造成泄漏同樣信息多次出現(xiàn)造成泄漏對明文的主動攻擊是可能的對明文的主動攻擊是可能的 信息塊可被替換、重排、刪除、重放信息塊可被替換、重排、刪除、重放誤差傳遞：密文塊損壞誤差傳遞：密文塊損壞僅僅對應(yīng)明文塊

26、損壞對應(yīng)明文塊損壞適合于傳輸短信息適合于傳輸短信息43密碼分組鏈接密碼分組鏈接CBCiKii-1iKii-1C = E (PC ) P = D (C ) C3.4.2 密碼分組鏈接模式（密碼分組鏈接模式（CBC)44CBC的特點的特點沒有已知的并行實現(xiàn)算法沒有已知的并行實現(xiàn)算法能隱藏明文的模式信息能隱藏明文的模式信息 需要共同的初始化向量需要共同的初始化向量IVIV， IVIV應(yīng)像密鑰一樣被保護，對于應(yīng)像密鑰一樣被保護，對于收發(fā)雙方都應(yīng)是已知的。收發(fā)雙方都應(yīng)是已知的。 相同明文相同明文生成生成不同密文不同密文 初始化向量初始化向量IVIV可以用來改變第一組的明文分布模式可以用來改變第一組的明文

27、分布模式對明文的主動攻擊是不容易的對明文的主動攻擊是不容易的 信息塊不容易被替換、重排、刪除、重放信息塊不容易被替換、重排、刪除、重放 誤差傳遞：密文塊損壞誤差傳遞：密文塊損壞兩兩明文明文塊塊損壞損壞安全性好于安全性好于ECBECB適合于傳輸長度大于適合于傳輸長度大于6464位的報文，還可以進行用戶鑒別位的報文，還可以進行用戶鑒別, ,是是大多系統(tǒng)的標準如大多系統(tǒng)的標準如 SSLSSL、IPSecIPSecCBCCBC模式除了能夠獲得保密性外，還能用于認證。模式除了能夠獲得保密性外，還能用于認證。45密碼反饋密碼反饋CFB CFB:CFB:若待加密的消息按字符處理時，可采用若待加密的消息按字符

28、處理時，可采用CFBCFB或或OFBOFB模式。實際上將模式。實際上將DESDES轉(zhuǎn)換為流密碼。轉(zhuǎn)換為流密碼。流密碼不需要對消息進行填充，而且運行是流密碼不需要對消息進行填充，而且運行是實時的。實時的。假定：假定：Si Si 為移位寄存器為移位寄存器, ,傳輸單位為傳輸單位為jbitbit 加密加密: C: Ci i =P =Pi i ( (E EK K(S(Si i) )的高的高j j位位) ) 解密解密: P: Pi i=C=Ci i ( (E EK K(S(Si i) )的高的高j j位位) ) S Si+1i+1=(S=(Si ij)|Cj)|Ci i3.4.3 密碼反饋模式（密碼反饋模式（CFB)46密碼反饋密碼反饋