分組密碼體制(閱讀)課件

第3章分組密碼體制郝艷華漳州師范學(xué)院計算機(jī)科學(xué)與工程系11/25/20221第3章分組密碼體制郝艷華10/11/202213.1分組密碼概述3.2數(shù)據(jù)加密標(biāo)準(zhǔn)3.3差分密碼分析與線性密碼分析3.4分組密碼的運(yùn)行模式3.5IDEA3.6AES算法——Rijndael11/25/202223.1分組密碼概述10/11/20222§3.1分組密碼概述在許多密碼系統(tǒng)中，單鑰分組密碼是系統(tǒng)安全的一個重要組成部分，用分組密碼易于構(gòu)造偽隨機(jī)數(shù)生成器、流密碼、消息認(rèn)證碼（MAC）和雜湊函數(shù)等，還可進(jìn)而成為消息認(rèn)證技術(shù)、數(shù)據(jù)完整性機(jī)制、實體認(rèn)證協(xié)議以及單鑰數(shù)字簽字體制的核心組成部分。實際應(yīng)用中對于分組密碼的要求：安全性運(yùn)行速度、存儲量（程序的長度、數(shù)據(jù)分組長度、高速緩存大?。崿F(xiàn)平臺（硬件、軟件、芯片）、運(yùn)行模式11/25/20223§3.1分組密碼概述在許多密碼系統(tǒng)中，單鑰分組密碼是系統(tǒng)安明文x0,x1,…,xi,…明文分組x=(x0,x1,…,xn-1)，密鑰k=(k0,k1,…,kt-1)密文分組y=(y0,y1,…,ym-1)加密函數(shù)E：Vn×K→Vm圖3.1分組密碼框圖11/25/20224明文x0,x1,…,xi,…圖3.1分組密碼框圖10/11與流密碼不同之處在于輸出的每一位數(shù)字不是只與相應(yīng)時刻輸入的明文數(shù)字有關(guān)，而是與一組長為n的明文數(shù)字有關(guān)。在相同密鑰下，分組密碼對長為n的輸入明文組所實施的變換是等同的，所以只需研究對任一組明文數(shù)字的變換規(guī)則這種密碼實質(zhì)上是字長為n的數(shù)字序列的代換密碼11/25/20225與流密碼不同之處在于輸出的每一位數(shù)字不是只與相應(yīng)時刻輸入的明通常取m=n。若m>n，則為有數(shù)據(jù)擴(kuò)展的分組密碼；若m<n，則為有數(shù)據(jù)壓縮的分組密碼。本文主要討論二元情況11/25/20226通常取m=n。10/11/20226設(shè)計的算法應(yīng)滿足下述要求：①分組長度n要足夠大，使分組代換字母表中的元素個數(shù)2n足夠大，防止明文窮舉攻擊法奏效。DES、IDEA、FEAL和LOKI等分組密碼都采用n=64，在生日攻擊下用232組密文成功概率為1/2，同時要求232×64b=215MB存貯，故采用窮舉攻擊是不現(xiàn)實的。11/25/20227設(shè)計的算法應(yīng)滿足下述要求：10/11/20227②密鑰量要足夠大（即置換子集中的元素足夠多），盡可能消除弱密鑰并使所有密鑰同等地好，以防止密鑰窮舉攻擊奏效。但密鑰又不能過長，以便于密鑰的管理。DES采用56比特密鑰，太短了，IDEA采用128比特密鑰，據(jù)估計，在今后30～40年內(nèi)采用80比特密鑰是足夠安全的。11/25/20228②密鑰量要足夠大（即置換子集中的元素足夠多），盡可能消除弱③由密鑰確定置換的算法要足夠復(fù)雜，充分實現(xiàn)明文與密鑰的擴(kuò)散和混淆，沒有簡單的關(guān)系可循，能抗擊各種已知的攻擊，如差分攻擊和線性攻擊；有高的非線性階數(shù)，實現(xiàn)復(fù)雜的密碼變換；使對手破譯時除了用窮舉法外，無其它捷徑可循。11/25/20229③由密鑰確定置換的算法要足夠復(fù)雜，充分實現(xiàn)明文與密鑰的擴(kuò)散④加密和解密運(yùn)算簡單，易于軟件和硬件高速實現(xiàn)。如將分組n化分為子段，每段長為8、16或者32。在以軟件實現(xiàn)時，應(yīng)選用簡單的運(yùn)算，使作用于子段上的密碼運(yùn)算易于以標(biāo)準(zhǔn)處理器的基本運(yùn)算，如加、乘、移位等實現(xiàn)，避免用以軟件難于實現(xiàn)的逐比特置換。為了便于硬件實現(xiàn)，加密和解密過程之間的差別應(yīng)僅在于由秘密密鑰所生成的密鑰表不同而已。這樣，加密和解密就可用同一器件實現(xiàn)。設(shè)計的算法采用規(guī)則的模塊結(jié)構(gòu)，如多輪迭代等，以便于軟件和VLSI（超大規(guī)模集成電路）快速實現(xiàn)。11/25/202210④加密和解密運(yùn)算簡單，易于軟件和硬件高速實現(xiàn)。如將分組n化⑤數(shù)據(jù)擴(kuò)展盡可能地小。一般無數(shù)據(jù)擴(kuò)展，在采用同態(tài)置換和隨機(jī)化加密技術(shù)時可引入數(shù)據(jù)擴(kuò)展。⑥差錯傳播盡可能地小。要實現(xiàn)上述幾點(diǎn)要求：首先要在理論上研究有效而可靠的設(shè)計方法而后進(jìn)行嚴(yán)格的安全性檢驗要易于實現(xiàn)11/25/202211⑤數(shù)據(jù)擴(kuò)展盡可能地小。一般無數(shù)據(jù)擴(kuò)展，在采用同態(tài)置換和隨機(jī)§3.1.1代換如果明文和密文的分組長都為n比特，則明文的每一個分組都有2n個可能的取值。為使加密運(yùn)算可逆（使解密運(yùn)算可行），明文的每一個分組都應(yīng)產(chǎn)生惟一的一個密文分組，這樣的變換是可逆的，稱明文分組到密文分組的可逆變換為代換。不同可逆變換的個數(shù)有2n!個。11/25/202212§3.1.1代換如果明文和密文的分組長都為n比特，則明文的下圖表示n=4的代換密碼的一般結(jié)構(gòu)，4比特輸入產(chǎn)生16個可能輸入狀態(tài)中的一個，由代換結(jié)構(gòu)將這一狀態(tài)映射為16個可能輸出狀態(tài)中的一個，每一輸出狀態(tài)由4個密文比特表示。11/25/202213下圖表示n=4的代換密碼的一般結(jié)構(gòu)，4比特輸入產(chǎn)生16個可能加密映射和解密映射可由代換表來定義這種定義法是分組密碼最常用的形式，能用于定義明文和密文之間的任何可逆映射11/25/202214加密映射和解密映射可由代換表來定義10/11/202214如果分組長度太小，系統(tǒng)則等價于古典的代換密碼，容易通過對明文的統(tǒng)計分析而被攻破。這個弱點(diǎn)不是代換結(jié)構(gòu)固有的，只是因為分組長度太小。如果分組長度n足夠大，而且從明文到密文可有任意可逆的代換，那么明文的統(tǒng)計特性將被隱藏而使以上的攻擊不能奏效從實現(xiàn)的角度來看，分組長度很大的可逆代換結(jié)構(gòu)是不實際的。一般地，對n比特的代換結(jié)構(gòu)，密鑰的大小是n×2n比特。如對64比特的分組，密鑰大小應(yīng)是64×264=270≈1021比特，因此難以處理。11/25/202215如果分組長度太小，系統(tǒng)則等價于古典的代換密碼，容易通過對明文實際中常將n分成較小的段，例如可選n=r·n0，其中r和n0都是正整數(shù)，將設(shè)計n個變量的代換變?yōu)樵O(shè)計r個較小的子代換，而每個子代換只有n0個輸入變量。一般n0都不太大，稱每個子代換為代換盒，簡稱為S盒。 例如DES中將輸入為48比特、輸出為32比特的代換用8個S盒來實現(xiàn)，每個S盒的輸入端數(shù)僅為6比特，輸出端數(shù)僅為4比特。11/25/202216實際中常將n分成較小的段，例如可選n=r·n0，其中r和n§3.1.2擴(kuò)散和混淆擴(kuò)散和混淆是由Shannon提出的設(shè)計密碼系統(tǒng)的兩個基本方法，目的是抗擊敵手對密碼系統(tǒng)的統(tǒng)計分析。如果敵手知道明文的某些統(tǒng)計特性，如消息中不同字母出現(xiàn)的頻率、可能出現(xiàn)的特定單詞或短語，而且這些統(tǒng)計特性以某種方式在密文中反映出來，那么敵手就有可能得出加密密鑰或其一部分，或者得出包含加密密鑰的一個可能的密鑰集合。11/25/202217§3.1.2擴(kuò)散和混淆擴(kuò)散和混淆是由Shannon提出的設(shè)所謂擴(kuò)散，就是將明文的統(tǒng)計特性散布到密文中去，實現(xiàn)方式是使得密文中每一位由明文中多位產(chǎn)生。例如對英文消息M=m1m2m3…的加密操作其中ord(mi)是求字母mi對應(yīng)的序號，chr(i)是求序號i對應(yīng)的字母。這時明文的統(tǒng)計特性將被散布到密文中，因而每一字母在密文中出現(xiàn)的頻率比在明文中出現(xiàn)的頻率更接近于相等，雙字母及多字母出現(xiàn)的頻率也更接近于相等。在二元分組密碼中，可對數(shù)據(jù)重復(fù)執(zhí)行某個置換，再對這一置換作用于一函數(shù)，可獲得擴(kuò)散11/25/202218所謂擴(kuò)散，就是將明文的統(tǒng)計特性散布到密文中去，實現(xiàn)方式是使得擴(kuò)散是使明文和密文之間的統(tǒng)計關(guān)系變得盡可能復(fù)雜，以使敵手無法得到密鑰混淆是使密文和密鑰之間的統(tǒng)計關(guān)系變得盡可能復(fù)雜，以使敵手無法得到密鑰。因此即使敵手能得到密文的一些統(tǒng)計關(guān)系，由于密鑰和密文之間的統(tǒng)計關(guān)系復(fù)雜化，敵手也無法得到密鑰。使用復(fù)雜的代換算法可以得到預(yù)期的混淆效果，而簡單的線性代換函數(shù)得到的混淆效果則不夠理想。擴(kuò)散和混淆成功地實現(xiàn)了分組密碼的本質(zhì)屬性，因而成為設(shè)計現(xiàn)代分組密碼的基礎(chǔ)。11/25/202219擴(kuò)散是使明文和密文之間的統(tǒng)計關(guān)系變得盡可能復(fù)雜，以使敵手無法§3.1.3Feistel密碼結(jié)構(gòu)很多分組密碼的結(jié)構(gòu)從本質(zhì)上說都是基于該結(jié)構(gòu)的乘積密碼指順序地執(zhí)行兩個或多個基本密碼系統(tǒng)，使得最后結(jié)果的密碼強(qiáng)度高于每個基本密碼系統(tǒng)產(chǎn)生的結(jié)果.Feistel提出了實現(xiàn)代換和置換的方法。其思想實際上是Shannon提出的利用乘積密碼實現(xiàn)混淆和擴(kuò)散思想的具體應(yīng)用。11/25/202220§3.1.3Feistel密碼結(jié)構(gòu)很多分組密碼的結(jié)構(gòu)從本質(zhì)圖3.3Feistel網(wǎng)絡(luò)示意圖11/25/202221圖3.3Feistel網(wǎng)絡(luò)示意圖10/11/2022211.Feistel加密結(jié)構(gòu) 輸入是分組長為2w的明文和一個密鑰K。將每組明文分成左右兩半L0和R0，在進(jìn)行完n輪迭代后，左右兩半再合并到一起以產(chǎn)生密文分組。其第i輪迭代的輸入為前一輪輸出的函數(shù)：其中Ki是第i輪用的子密鑰，由加密密鑰K得到。一般地，各輪子密鑰彼此不同而且與K也不同。11/25/2022221.Feistel加密結(jié)構(gòu)10/11/202222Feistel網(wǎng)絡(luò)中每輪結(jié)構(gòu)都相同，每輪中右半數(shù)據(jù)被作用于輪函數(shù)F后，再與左半數(shù)據(jù)進(jìn)行異或運(yùn)算——代換每輪的輪函數(shù)的結(jié)構(gòu)都相同，但以不同的子密鑰Ki作為參數(shù)。代換過程完成后，再交換左、右兩半數(shù)據(jù)——置換這種結(jié)構(gòu)是Shannon提出的代換——置換網(wǎng)絡(luò)SPN的特有形式11/25/202223Feistel網(wǎng)絡(luò)中每輪結(jié)構(gòu)都相同，每輪中右半數(shù)據(jù)被作用于輪Feistel網(wǎng)絡(luò)的實現(xiàn)與以下參數(shù)和特性有關(guān)：①分組大小:分組越大則安全性越高，但加密速度就越慢。分組密碼設(shè)計中最為普遍使用的分組大小是64比特。②密鑰大?。好荑€越長則安全性越高，但加密速度就越慢?，F(xiàn)在普遍認(rèn)為64比特或更短的密鑰長度是不安全的，通常使用128比特的密鑰長度。③輪數(shù)：單輪結(jié)構(gòu)遠(yuǎn)不足以保證安全性，但多輪結(jié)構(gòu)可提供足夠的安全性。典型地，輪數(shù)取為16。④子密鑰產(chǎn)生算法：該算法的復(fù)雜性越大，則密碼分析的困難性就越大。⑤輪函數(shù)：輪函數(shù)的復(fù)雜性越大，密碼分析的困難性也越大。11/25/202224Feistel網(wǎng)絡(luò)的實現(xiàn)與以下參數(shù)和特性有關(guān)：10/11在設(shè)計Feistel網(wǎng)絡(luò)時，還有以下兩個方面需要考慮：①快速的軟件實現(xiàn)：在很多情況中，算法是被鑲嵌在應(yīng)用程序中，因而無法用硬件實現(xiàn)。此時算法的執(zhí)行速度是考慮的關(guān)鍵。②算法容易分析：如果算法能被無疑義地解釋清楚，就可容易地分析算法抵抗攻擊的能力，有助于設(shè)計高強(qiáng)度的算法。11/25/202225在設(shè)計Feistel網(wǎng)絡(luò)時，還有以下兩個方面需要考慮：12.Feistel解密結(jié)構(gòu)

Feistel解密過程本質(zhì)上和加密過程是一樣的，算法使用密文作為輸入，但使用子密鑰Ki的次序與加密過程相反，即第1輪使用Kn，第2輪使用Kn-1，……，最后一輪使用K1。這一特性保證了解密和加密可采用同一算法。11/25/2022262.Feistel解密結(jié)構(gòu)10/11/202226圖3.4Feistel加解密過程11/25/202227圖3.4Feistel加解密過程10/11/202227證明解密過程第1輪的輸出等于加密過程第16輪輸入左右兩半的交換值在加密過程中：在解密過程中11/25/202228證明解密過程第1輪的輸出等于加密過程第16輪輸入左右兩半的交所以解密過程第1輪的輸出為LE15‖RE15，等于加密過程第16輪輸入左右兩半交換后的結(jié)果。容易證明這種對應(yīng)關(guān)系在16輪中每輪都成立。一般地，加密過程的第i輪有因此以上兩式描述了加密過程中第i輪的輸入與第i輪輸出的函數(shù)關(guān)系11/25/202229所以解密過程第1輪的輸出為LE15‖RE15，等于加密過程第§3.2數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)（dataencryptionstandard,DES）是迄今為止世界上最為廣泛使用和流行的一種分組密碼算法它的分組長度為64比特，密鑰長度為56比特，它是由美國IBM公司研制的，是早期的稱作Lucifer密碼的一種發(fā)展和修改1975年3月17日DES首次被公布在聯(lián)邦記錄中，經(jīng)過大量的公開討論后，DES于1977年1月15日被正式批準(zhǔn)并作為美國聯(lián)邦信息處理標(biāo)準(zhǔn)，即FIPS-46，同年7月15日開始生效。規(guī)定每隔5年由美國國家保密局（nationalsecurityagency,NSA）作出評估，并重新批準(zhǔn)它是否繼續(xù)作為聯(lián)邦加密標(biāo)準(zhǔn)。11/25/202230§3.2數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)（dataencrypt最近的一次評估是在1994年1月，美國已決定1998年12月以后將不再使用DES。1997年DESCHALL小組經(jīng)過近4個月的努力，通過Internet搜索了3×1016個密鑰，找出了DES的密鑰，恢復(fù)出了明文。1998年5月美國EFF(electronicsfrontierfoundation)宣布，他們以一臺價值20萬美元的計算機(jī)改裝成的專用解密機(jī)，用56小時破譯了56比特密鑰的DES。美國國家標(biāo)準(zhǔn)和技術(shù)協(xié)會已征集并進(jìn)行了幾輪評估、篩選，產(chǎn)生了稱之為AES(advancedencryptionstandard)的新加密標(biāo)準(zhǔn)。盡管如此，DES對于推動密碼理論的發(fā)展和應(yīng)用畢竟起了重大作用，對于掌握分組密碼的基本理論、設(shè)計思想和實際應(yīng)用仍然有著重要的參考價值11/25/202231最近的一次評估是在1994年1月，美國已決定1998年12月§3.2.1DES描述11/25/202232§3.2.1DES描述10/11/2022321.初始置換

11/25/2022331.初始置換10/11/20223311/25/20223410/11/2022341.初始置換

M1M2M3M4M5M6M7M8

M9M10M11M12M13M14M15M16 M17M18M19M20M21M22M23M24

M25M26M27M28M29M30M31M32

M33M34M35M36M37M38M39M40

M41M42M43M44M45M46M47M48

M49M50M51M52M53M54M55M56

M57M58M59M60M61M62M63M6411/25/2022351.初始置換10/11/202235其中Mi是二元數(shù)字。由表3.2(a)得X=IP(M)為：

M58M50M42M34M26M18M10M2 M60M52M44M36M28M20M12M4 M62M54M46M38M30M22M14M6 M64M56M48M40M32M24M16M8 M57M49M41M33M25M17M9M1 M59M51M43M35M27M19M11M3 M61M53M45M37M29M21M13M5 M63M55M47M39M31M23M15M711/25/202236其中Mi是二元數(shù)字。由表3.2(a)得X=IP(M)為：10如果再取逆初始置換Y=IP-1(X)=IP-1(IP(M))，可以看出，M各位的初始順序?qū)⒈换謴?fù)。11/25/202237如果再取逆初始置換Y=IP-1(X)=IP-1(IP(M))圖3.6DES加密算法的輪結(jié)構(gòu)11/25/202238圖3.6DES加密算法的輪結(jié)構(gòu)10/11/202238每輪變換可由以下公式表示：11/25/202239每輪變換可由以下公式表示：10/11/202239圖3.7函數(shù)F(R,K)的計算過程11/25/202240圖3.7函數(shù)F(R,K)的計算過程10/11/20224011/25/20224110/11/20224111/25/20224210/11/20224211/25/20224310/11/202243對每個盒Si，其6比特輸入中，第1個和第6個比特形成一個2位二進(jìn)制數(shù)，用來選擇Si的4個代換中的一個。6比特輸入中，中間4位用來選擇列。行和列選定后，得到其交叉位置的十進(jìn)制數(shù)，將這個數(shù)表示為4位二進(jìn)制數(shù)即得這一S盒的輸出。例如，S1的輸入為011001，行選為01（即第1行），列選為1100（即第12列），行列交叉位置的數(shù)為9，其4位二進(jìn)制表示為1001，所以S1的輸出為1001。S盒的每一行定義了一個可逆代換。11/25/202244對每個盒Si，其6比特輸入中，第1個和第6個比特形成一個2位3.密鑰的產(chǎn)生11/25/2022453.密鑰的產(chǎn)生10/11/20224511/25/20224610/11/2022464.解密 和Feistel密碼一樣，DES的解密和加密使用同一算法，但子密鑰使用的順序相反。11/25/2022474.解密10/11/202247§3.2.2二重DES為了提高DES的安全性，并利用實現(xiàn)DES的現(xiàn)有軟硬件，可將DES算法在多密鑰下多重使用。二重DES是多重使用DES時最簡單的形式，其中明文為P，兩個加密密鑰為K1和K211/25/202248§3.2.2二重DES為了提高DES的安全性，并利用實現(xiàn)D密文為：解密時，以相反順序使用兩個密鑰：因此，二重DES所用密鑰長度為112比特，強(qiáng)度極大地增加。然而，假設(shè)對任意兩個密鑰K1和K2，能夠找出另一密鑰K3，使得那么，二重DES以及多重DES都沒有意義，因為它們與56比特密鑰的單重DES等價，好在這種假設(shè)對DES并不成立。11/25/202249密文為：10/11/202249將DES加密過程64比特分組到64比特分組的映射看作一個置換，如果考慮264個所有可能的輸入分組，則密鑰給定后，DES的加密將把每個輸入分組映射到一個惟一的輸出分組。否則，如果有兩個輸入分組被映射到同一分組，則解密過程就無法實施。對264個輸入分組，總映射個數(shù)為11/25/202250將DES加密過程64比特分組到64比特分組的映射看作一個置換另一方面，對每個不同的密鑰，DES都定義了一個映射，總映射數(shù)為256<1017。因此，可假定用兩個不同的密鑰兩次使用DES，可得一個新映射，而且這一新映射不出現(xiàn)在單重DES定義的映射中。這一假定已于1992年被證明。所以使用二重DES產(chǎn)生的映射不會等價于單重DES加密。但對二重DES有以下一種稱為中途相遇攻擊的攻擊方案，這種攻擊不依賴于DES的任何特性，因而可用于攻擊任何分組密碼。其基本思想如下：11/25/202251另一方面，對每個不同的密鑰，DES都定義了一個映射，總映射數(shù)如果有那么11/25/202252如果有10/11/202252如果已知一個明文密文對(P,C)，攻擊的實施可如下進(jìn)行：首先，用256個所有可能的K1對P加密，將加密結(jié)果存入一表并對表按X排序，然后用256個所有可能的K2對C解密，在上述表中查找與C解密結(jié)果相匹配的項，如果找到，則記下相應(yīng)的K1和K2。最后再用一新的明文密文對(P′,C′)檢驗上面找到的K1和K2，用K1和K2對P′兩次加密，若結(jié)果等于C′，就可確定K1和K2是所要找的密鑰。11/25/202253如果已知一個明文密文對(P,C)，攻擊的實施可如下進(jìn)行：首先對已知的明文P，二重DES能產(chǎn)生264個可能的密文,而可能的密鑰個數(shù)為2112，所以平均來說，對一個已知的明文，有2112/264=248個密鑰可產(chǎn)生已知的密文。而再經(jīng)過另外一對明文密文的檢驗，誤報率將下降到248-64=2-16。所以在實施中途相遇攻擊時，如果已知兩個明文密文對，則找到正確密鑰的概率為1-2-16。11/25/202254對已知的明文P，二重DES能產(chǎn)生264個可能的密文,而可能的§3.2.3兩個密鑰的三重DES抵抗中途相遇攻擊的一種方法是使用3個不同的密鑰做3次加密，從而可使已知明文攻擊的代價增加到2112。然而，這樣又會使密鑰長度增加到56×3=168比特，因而過于笨重。一種實用的方法是僅使用兩個密鑰做3次加密，實現(xiàn)方式為加密\解密\加密，簡記為EDE(encryptdecryptencrypt)，即：11/25/202255§3.2.3兩個密鑰的三重DES抵抗中途相遇攻擊的一種方法圖3.9兩個密鑰的三重DES11/25/20225610/11/202256§3.2.43個密鑰的三重DES三個密鑰的三重DES密鑰長度為168比特，加密方式為令K3=K2或K1=K2，則變?yōu)橐恢谼ES。三個密鑰的三重DES已在因特網(wǎng)的許多應(yīng)用（如PGP和S/MIME）中被采用。11/25/202257§3.2.43個密鑰的三重DES三個密鑰的三重DES密鑰長§3.3差分密碼分析與線性密碼分析3.3.1差分密碼分析差分密碼分析是迄今已知的攻擊迭代密碼最有效的方法之一，其基本思想是：通過分析明文對的差值對密文對的差值的影響來恢復(fù)某些密鑰比特。11/25/202258§3.3差分密碼分析與線性密碼分析3.3.1差分密碼分析對分組長度為n的r輪迭代密碼，兩個n比特串Yi和Y*i的差分定義為其中表示n比特串集上的一個特定群運(yùn)算，表示在此群中的逆元。由加密對可得差分序列ΔY0,ΔY1,…,ΔYr其中Y0和Y*0是明文對，Yi和Y*i(1≤i≤r)是第i輪的輸出，它們同時也是第i+1輪的輸入。第i輪的子密鑰記為Ki，F(xiàn)是輪函數(shù)，且Yi=F(Yi-1,Ki)。11/25/202259對分組長度為n的r輪迭代密碼，兩個n比特串Yi和Y*i的差分11/25/20226010/11/202260對r-輪迭代密碼的差分密碼分析過程可綜述為如下的步驟：①找出一個(r-1)-輪特征Ω(r-1)=α0,α1,…,αr-1，使得它的概率達(dá)到最大或幾乎最大。②均勻隨機(jī)地選擇明文Y0并計算Y*0，使得Y0和Y*0的差分為α0，找出Y0和Y*0在實際密鑰加密下所得的密文Yr和Y*r。若最后一輪的子密鑰Kr（或Kr的部分比特）有2m個可能值Kjr(1≤j≤2m)，設(shè)置相應(yīng)的2m個計數(shù)器Λj(1≤j≤2m)；用每個Kjr解密密文Yr和Y*r，得到Y(jié)r-1和Y*r-1，如果Yr-1和Y*r-1的差分是αr-1，則給相應(yīng)的計數(shù)器Λj加1。③重復(fù)步驟②，直到一個或幾個計數(shù)器的值明顯高于其他計數(shù)器的值，輸出它們所對應(yīng)的子密鑰（或部分比特）11/25/202261對r-輪迭代密碼的差分密碼分析過程可綜述為如下的步驟：10一種攻擊的復(fù)雜度可以分為兩部分：數(shù)據(jù)復(fù)雜度和處理復(fù)雜度。數(shù)據(jù)復(fù)雜度是實施該攻擊所需輸入的數(shù)據(jù)量；而處理復(fù)雜度是處理這些數(shù)據(jù)所需的計算量。這兩部分的主要部分通常被用來刻畫該攻擊的復(fù)雜度。