現(xiàn)代密碼學(第三章)

第三章：分組密碼一、分組密碼的基本概念二、分組密碼DES三、分組密碼IDEA四、分組密碼Rijndael五、分組密碼SAFER+2024/12/291一、分組密碼的基本概念分組密碼若明文流被分割成等長串，各串用相同的加密算法和相同的密鑰進行加密，就是分組密碼。即當（1）明文和密文是固定長度為n的比特串m=m1m2m3…mn

，c=c1c2c3…cn

，（2）加密密鑰和解密密鑰相等，是固定長度為j的比特串z=z1z2z3…zj，（3）加密算法為c=E(m,z)，（4）解密算法為m=D(c,z)=D(E(m,z),z)。則稱這樣的加解密算法為分組密碼。2024/12/292一、分組密碼的基本概念分組密碼的優(yōu)缺點分組密碼的加解密算法（E，D）簡潔快速，所占用的計算資源小，易于軟件和硬件實現(xiàn)。一般來說，用硬件實現(xiàn)時，流密碼比分組密碼更簡單快速；用軟件實現(xiàn)時，分組密碼比流密碼更簡單快速。加解密算法（E，D）參數(shù)固定，比流密碼更容易實現(xiàn)標準化。由于明文流被分段加密，因此容易實現(xiàn)同步，而且傳輸錯誤不會向后擴散。分組密碼的安全性很難被證明，至多證明局部安全性。2024/12/293一、分組密碼的基本概念分組密碼所面對的主要威脅：已知明文攻擊分組密碼的密鑰z被重復使用，即多次一密。因此最主要的威脅就是已知明文攻擊。設攻擊者Eve獲得了一組明文/密文對（m，c）。他試圖在加密方程c=E(m,z)或解密方程m=D(c,z)中求出密鑰z。2024/12/294一、分組密碼的基本概念Eve的一種辦法是窮舉搜索密鑰的所有可能值。（密鑰z長度為j，共有2j個可能值）為了抵抗窮舉搜索，密鑰的長度j不能太小。當然密鑰長度也不能太大，否則加解密的計算量就會很大。當前常用的密鑰長度為64或128或256。Eve的另一種辦法是充分利用加解密算法（E，D）的弱點。如果某一組明文/密文對（m，c）使得方程m=D(c,z)特別容易解出z，m就稱為一個弱明文，z就稱為一個弱密鑰。2024/12/295一、分組密碼的基本概念Eve時刻都在對加解密算法（E，D）進行研究，以便找到弱明文和弱密鑰。(當然，即使Eve通過研究找到了弱明文m和弱密鑰z，也不見得能夠在實際中碰到這樣的m)如果給Eve更加優(yōu)越的條件，讓他能夠故意“碰到”弱明文m。這就是說，讓Eve獲得一個正在使用的加密黑盒，可以隨意地輸入明文，輸出密文。這樣的攻擊是已知明文攻擊的強化型，稱為選擇明文攻擊。要求：加解密算法（E，D）不存在弱明文和弱密鑰。2024/12/296一、分組密碼的基本概念為了抵抗已知明文攻擊（甚至選擇明文攻擊），分組密碼應該滿足的性質(zhì)混淆性：所設計的密碼應使得明文、密文、密鑰之間的依賴關系相當復雜，以至于這種依賴關系對密碼分析者來說是無法利用的。密碼分析者利用這種依賴關系的方法非常多，因此混淆性也是一個極為繁雜的概念。2024/12/297一、分組密碼的基本概念擴散性：所設計的密碼應使得（1）密鑰的每一個比特影響密文的每一個比特，以防止對密鑰進行逐段破譯；（2）明文的每一個比特影響密文的每一個比特，以便最充分地隱蔽明文。對擴散性可以有多種理解，比如“粘連性”指的是明文、密文、密鑰的每一位都相互依賴；“不連續(xù)性”或“雪崩性”指的是當改變明文的任何一個比特時，對應密文改變的比特的個數(shù)是一個隨機變量；“不可部分破譯性”指的是分組密碼不能分解成若干子密碼。這就是說，對分組密碼的攻擊要么徹底破譯，要么一無所獲。（everythingornothing）2024/12/298一、分組密碼的基本概念非線性度：這一項屬于混淆性?；緮?shù)學原理：如果明文與密文的關系是n維線性關系，系數(shù)是密鑰，則n個明文/密文對（而不是2n個）就可破解密鑰；如果明文與密文的關系是n維r次函數(shù)關系，且系數(shù)是密鑰，則nr個明文/密文對就可破解密鑰；如果雖然次數(shù)r較大，但明文與密文的關系“非常逼近”一個n維線性關系，則n個明文/密文對就可“基本上”破解密鑰。2024/12/299一、分組密碼的基本概念這就是線性密碼分析的思想。抵抗線性密碼分析的強度就是非線性度。2024/12/2910一、分組密碼的基本概念安全強度的穩(wěn)定性：指的是當部分密鑰被破譯后，分組密碼仍有一定的抗攻擊能力。以下舉一個簡單的例子來說明安全強度的穩(wěn)定性。設明文x為n比特長；兩個n比特長的密鑰k1和k2；密文y=(x‘+’k1)“+”k2，其中‘+’為逐比特異或，“+”為(mod2n)加法。這個加密算法所使用的密鑰長度為2n。2024/12/2911一、分組密碼的基本概念假設攻擊者已經(jīng)獲得了k2的低m比特。根據(jù)“+”的進位規(guī)則，只需要一對明文/密文對就可立即推算出k1的低m比特；因此對未來任意的密文，可立即得到其對應明文的低m比特。這就是說，2n長的密鑰的各比特對安全性的貢獻是極不平均的，在截獲一對明文/密文對的前提下，安全性完全依賴于k2的低位的保密性。這個加密算法就是極不穩(wěn)定的。2024/12/2912一、分組密碼的基本概念分組密碼的設計準則

安全性

簡潔性

有效性

透明性和靈活性

加解密相似性

2024/12/2913一、分組密碼的基本概念安全性概括地說安全性就是從任何角度難以攻破。其中兩個最重要的角度是①對于一個正在使用的加密算法，即使攻擊者獲得“許多”精心選擇的明文--密文對，他仍無法“接近”密鑰；②即使攻擊者獲得“許多”精心選擇的明文--密文對，他仍無法“接近”任一個新密文所對應的明文。

2024/12/2914一、分組密碼的基本概念簡潔性分組密碼算法在滿足安全性的同時盡可能簡單快速。如果分組密碼算法用軟件來實現(xiàn)，則要求字長盡可能自然地適應軟件編程，比如8、16、32比特等。在軟件實現(xiàn)中，按比特置換通常是難于實現(xiàn)的，因此應盡量避免使用它。字的運算應該是易于軟件實現(xiàn)的運算，最好是用一些標準處理器所具有的一些基本指令，比如加法、乘法、移位等。如果分組密碼算法用硬件來實現(xiàn)，則盡量使用規(guī)則結(jié)構，以便用VLSI來實現(xiàn)。2024/12/2915一、分組密碼的基本概念有效性分組密碼的設計應使密鑰最大限度地起到安全性作用。在有效性差的分組密碼算法中，一個長密鑰的作用等效于另一個短密鑰，或其作用在統(tǒng)計上逼近短密鑰。以下是兩個極端的例子。2024/12/2916一、分組密碼的基本概念設明文x、密文y、密鑰k1和k2均為n比特長；‘+’為逐比特異或，“+”為(mod2n)加法。如果加密算法為y=(x‘+’k1)‘+’k2，則2n長的密鑰(k1,k2)等效于n長的密鑰k1‘+’k2。如果加密算法為y=(x‘+’k1)“+”k2，則由前面的討論知：在k2的低m比特已知并且截獲一對明文/密文對的前提下，2n-m長的剩余密鑰等效于2n-2m長的密鑰。2024/12/2917一、分組密碼的基本概念透明性和靈活性透明性即要求算法是可證明安全的（雖然這是很困難的）。這就要求算法盡可能使用通用部件，避免黑盒。靈活性即要求算法的實現(xiàn)可以適應多種計算環(huán)境；明文分組長度可以伸縮；算法可以移植和變形。2024/12/2918一、分組密碼的基本概念加解密相似性我們知道：加密算法是E(·,z)，解密算法是D(·,z)。這里E(·,z)和D(·,z)使用相同的密鑰z，使用不同的算法E和D。如果D(·,z)=E(·,z*)，其中z*是z經(jīng)過非常簡單的重新編排得到的，則稱分組密碼算法是加解密相似的。2024/12/2919一、分組密碼的基本概念加解密相似即加密算法和解密算法相同，僅僅密鑰的編排不同。一個加解密相似的分組密碼算法，其加密機和解密機是同一個機件（加密軟件與解密軟件是同一個軟件），僅僅臨時輸入的密鑰不同。加解密相似性的好處是大大節(jié)省存儲空間和其它計算資源，大幅降低成本。這也是分組密碼設計所追求的一個方向。2024/12/2920一、分組密碼的基本概念分組密碼的設計技巧

計算部件

計算部件的組合SPN（即替換/置換網(wǎng)絡）多輪迭代與輪函數(shù)

2024/12/2921一、分組密碼的基本概念分組密碼的設計者總是在安全性與簡潔性之間回旋，因此一般的設計方法都是用一些簡單的計算部件，通過組合成為復雜的、能抵抗各種攻擊的加密函數(shù)。密碼設計者希望這些計算部件的安全性功能互補，而不是相互抵消。2024/12/2922一、分組密碼的基本概念計算部件群加密：明文塊與密鑰塊進行群“乘法”運算，它的作用是一次性地掩蓋明文。如果單獨使用群加密部件，則一組已知的明文/密文對就可獲得密鑰。以下是最常用的兩種群加密。逐比特異或‘+’，結(jié)構最簡單，缺點也最明顯，密文的一個比特只依賴于明文的一個比特和密鑰的一個比特，毫無擴散功能。(mod2n)加法“+”也是非常簡單的計算部件，具有單向擴散功能，即明文或密鑰的第j位影響密文的第j位、第j+1位、…、第n位。

2024/12/2923一、分組密碼的基本概念S盒（SubstitutionBox，即替換盒）：在分組密碼的計算部件中，必須有一個部件來實現(xiàn)高度的非線性。高度非線性函數(shù)的計算有兩種途徑：（1）用“解析表達式”（代數(shù)正規(guī)型），將自變量的值代入“解析表達式”，計算出函數(shù)值。（2）用輸入/輸出真值表，輸入自變量的值作為地址，在該地址所存儲的值就是查表查出的函數(shù)值。比較這兩種途徑，發(fā)現(xiàn)：2024/12/2924一、分組密碼的基本概念用“解析表達式”計算高度非線性函數(shù)，總是比較復雜，速度比較慢。隨著輸入/輸出長度增大，計算復雜度線性地增大。用輸入/輸出真值表計算高度非線性函數(shù)，短的輸入/輸出使計算量很小。隨著輸入/輸出長度增大，計算復雜度指數(shù)地增大（例如，輸入長度為n時，自變量有2n個可能的值，即輸入/輸出真值表有2n個地址；輸出長度為m時，函數(shù)值有2m個可能的值）。2024/12/2925一、分組密碼的基本概念因此在分組密碼算法中，高度非線性函數(shù)是用輸入/輸出真值表來計算的，不過輸入/輸出長度必須比較小，通常輸入長度不超過8比特。這里有一個問題：當輸入長度比較小時，課文比特的混淆性和擴散性就比較差。（例如，輸入長度為8比特時，高度非線性函數(shù)只是在8比特范圍內(nèi)進行混淆和擴散）。這個問題的解決方案是：許多線性函數(shù)可以實現(xiàn)大范圍的混淆和擴散。2024/12/2926一、分組密碼的基本概念因此有以下的結(jié)論：輸入/輸出長度比較小的高度非線性函數(shù)僅僅實現(xiàn)高度非線性，混淆和擴散功能可以由其它的線性計算部件來完成。輸入/輸出長度比較小的，用輸入/輸出真值表來計算的，僅僅實現(xiàn)高度非線性功能的計算部件稱為S盒?，F(xiàn)有的大多數(shù)S盒是公開的，即是一個單表代換部件。一少部分S盒是由密鑰控制的，即是一個多表代換部件。2024/12/2927一、分組密碼的基本概念計算部件的組合替換/置換網(wǎng)絡（SPN）：這是一個集掩蔽、混淆、擴散為一體的綜合性部件，由若干子部件組合而成。替換/置換網(wǎng)絡的一個典型代表是Feistel網(wǎng)絡，算法為：將明文m分為等長的兩部分m=(L(0),R(0))；使用由密鑰k控制的高度非線性函數(shù)F，（1）計算：(L’,R’)=(L(0)‘+’F(R(0),k),R(0))；（2）計算密文：c=(L(1),R(1))=(R’,L’)。2024/12/2928一、分組密碼的基本概念2024/12/2929一、分組密碼的基本概念Feistel網(wǎng)絡的結(jié)構特點定義變換f稱為對合變換（或稱為自反變換），如果其反變換還是f。（對任何x滿足f(f(x))=x）我們看到，F(xiàn)eistel網(wǎng)絡的第（1）步是對合變換；Feistel網(wǎng)絡的第（2）步也是對合變換；Feistel網(wǎng)絡本身不是對合變換。Feistel網(wǎng)絡的這種結(jié)構使它能夠組合成安全強度高的分組密碼算法。2024/12/2930一、分組密碼的基本概念Feistel網(wǎng)絡能否直接用作分組密碼算法？不能。首先，明文(L(0),R(0))和密文(L(1),R(1))之間有一個明顯的關系R(0)=

L(1)，即密鑰只覆蓋了明文的一半。其次，設攻擊者Eve獲得了明文(L(0),R(0))和密文(L(1),R(1))。Eve知道R(1)=L(0)‘+’F(R(0),k)，即F(R(0),k)=R(1)‘+’L(0)。在方程中，Eve僅僅不知道密鑰k。如果函數(shù)F設計得不好，就可能在方程中解出密鑰k，或猜測出密鑰k。這就是說，算法的安全性完全依賴于函數(shù)F，安全性依靠過于單薄。2024/12/2931一、分組密碼的基本概念多輪迭代與輪函數(shù)：迭代型分組密碼就是用簡單的、安全性弱的加密算法進行多輪迭代以獲得強的安全性。單輪加密算法稱為輪函數(shù)，所用的密鑰稱為單輪子密鑰。比如，把Feistel網(wǎng)絡作為輪函數(shù)，將迭代型分組密碼的加密算法構造如下：Feistel網(wǎng)絡→Feistel網(wǎng)絡→…Feistel網(wǎng)絡→左右對換。則（1）克服了Feistel網(wǎng)絡的安全性缺陷；（2）分組密碼是“加解密相似的”。2024/12/2932一、分組密碼的基本概念分組密碼的工作模式

分組密碼算法本身具有缺點：相同的密文分組一定對應相同的明文分組。分組密碼的工作模式就是以該分組密碼算法為基礎構造的密碼系統(tǒng)，意在增加課文分組的相互依賴性，克服分組密碼算法的缺點。以下簡記分組密碼的加密算法為E(·)，解密算法為D(·)。一個分組密碼的各種工作模式有：電碼本模式（ElectricCodeBook或ECB）碼分組鏈接模式（CodeBlockChaining或CBC）碼反饋模式（CodeFeedBack或CFB）輸出反饋模式（OutputFeedBack或OFB）2024/12/2933一、分組密碼的基本概念電碼本模式：直接使用分組密碼算法來進行消息加密和解密。

碼分組鏈接模式：記各明文分組為x1，x2，…，xn；對應的各密文分組為y1，y2，…，yn。取y0為一個公開的課文分組。加密算法為yj=E(xj‘+’yj-1)，j=1~n。解密算法為xj=D(yj)‘+’yj-1，j=1~n。2024/12/2934一、分組密碼的基本概念碼反饋模式：將明文序列分為子塊x1，x2，…，xn；對應的密文子塊為y1，y2，…，yn。其中m個子塊的長度等于分組密碼的一個明文分組長度。記E*(·)為分組密碼加密結(jié)果的最左邊子塊。CFB模式的加密算法為：(y1,y2,…,ym)=E(x1,x2,…,xm)；yj=xj‘+’E*(

yj-m,yj-m+1,…,yj-1)，j=m+1~n。解密算法為：(x1,x2,…,xm)=D(y1,y2,…,ym)；xj=yj‘+’E*(

yj-m,yj-m+1,…,yj-1)，j=m+1~n。2024/12/2935一、分組密碼的基本概念輸出反饋模式：將明文序列分為子塊x1，x2，…（無窮長）；對應的密文子塊為y1，y2，…。其中m個子塊的長度等于分組密碼的一個明文分組長度。記E*(·)為分組密碼加密結(jié)果的最左邊子塊。將E*(·)作為密鑰流發(fā)生器：kj=E*(

kj-m,kj-m+1,…,kj-1)，該密鑰流的初始狀態(tài)就是分組密碼的密鑰，記為(k-m+1,k-m+2,…,k0)。加密：yj=xj‘+’kj；解密：xj=yj‘+’kj。2024/12/2936一、分組密碼的基本概念部分國際著名的商用分組密碼（1）DES（DataEncryptionStandard）（2）IDEA（InternationalDataEncryptionAlgorithm）（3）AES（AdvancedEncryptionStandard）2024/12/2937二、分組密碼DES美國國家標準局（NBS）于1977年公布了由IBM公司研制的一種加密算法，并批準把它作為非機要部門使用的數(shù)據(jù)加密標準（DataEncryptionStandard），簡稱DES。自從公布以來，它一直超越國界成為國際上商用保密通信和計算機通信的最常用的加密算法。當時規(guī)定DES的使用期為10年。后來美國政府宣布延長它的使用期，其原因大概有兩條：一是DES尚未受到嚴重的威脅，二是一直沒有新的數(shù)據(jù)加密標準問世。DES超期服役了很長時間，在國際通信保密的舞臺上活躍了20年。2024/12/2938二、分組密碼DESDES扮演的突出角色首先，DES的結(jié)構閃爍著人類設計思想的精華，其優(yōu)點和缺點被密碼學界淋漓盡致地討論，供后人借鑒。舉例如下：（1）DES使用了S盒，而S盒現(xiàn)在已經(jīng)是幾乎所有分組密碼算法不可缺少的部件。（2）迭代分組密碼是分組密碼的主流設計。（3）DES輪函數(shù)結(jié)構是Feistel網(wǎng)絡，這種結(jié)構現(xiàn)在已經(jīng)是輪函數(shù)的經(jīng)典結(jié)構之一。2024/12/2939二、分組密碼DES（4）DES算法的第一個和最后一個部件沒有密鑰的參與，在已知明文攻擊之下不起任何安全性作用。以后設計的分組密碼都糾正了這個缺點。（5）DES的S盒設計細節(jié)始終沒有公布，因此被人們懷疑設有陷門（即密碼設計者為自己預留的破譯通道）。這種不透明的設計顯然會影響其商用前景。這一缺點引出了商用分組密碼設計的一個準則“透明性”，即密碼的使用者能夠確知該密碼的安全強度。

2024/12/2940二、分組密碼DES其次，對DES的各種攻擊方法紛紛被提出。窮舉搜索仍然是對分組密碼實用攻擊的主角。但進入90年代后，基于數(shù)學分析的攻擊方法逐漸興起，如以色列密碼專家Shamir等人提出了差分密碼分析，日本密碼學家Matsui等人提出了線性密碼分析，這些數(shù)學攻擊方法都首先被用于破譯DES，并且可以說取得了局部的成功。(比如，有人在個人計算機上用差分密碼分析方法，幾分鐘就破譯了8輪DES（標準的DES算法為16輪迭代）。又比如，據(jù)稱使用243個明文/密文對就可以由線性密碼分析方法破譯DES。243已經(jīng)不是天文數(shù)字了，據(jù)稱數(shù)十臺工作站協(xié)同工作，經(jīng)過十多天就可完成。

)2024/12/2941二、分組密碼DES為抵抗對DES的各種攻擊，產(chǎn)生了強化版的三重DES。三重DES的安全強度高于DES，但似乎不夠簡潔。2000年5月，美國國家標準技術研究所（NIST）最終確定了DES的替代標準AES（AdvancedEncryptionStandard），才使DES基本上完成了自己的歷史使命。AES的算法名稱是Rijndael。2024/12/2942二、分組密碼DESDES的計算部件

初始置換IP與其逆置換IP

-1IP是對64比特課文進行位置重排。IP

-1是IP的反變換。設m=(m1,m2,…,m64)；c=(c1,c2,…,c64)；使得IP(m)=c，或者IP-1(c)=m。則c1=m58，c2=m50，…，c64=m7。2024/12/2943二、分組密碼DES下表詳細給出IP(m)的下標序號與m的下標序號的對應關系，其中IP(m)的下標按順序排列。2024/12/2944二、分組密碼DES下表詳細給出IP

-1(c)的下標序號與c的下標序號的對應關系，其中IP

-1(c)的下標按順序排列。2024/12/2945二、分組密碼DES擴充變換E

擴充變換E的作用是將32比特的課文膨脹為48比特。設

m=(m1,m2,…,m32)；c=(c1,c2,…,c48)；使得E(m)=c。則c1=m32，c2=m1，…，c48=m1。下表詳細給出E(m)的下標序號與m的下標序號的對應關系，其中E(m)的下標按順序排列。（注意：下表的中間4列恰好是m的第1~第32比特）2024/12/2946二、分組密碼DESE：2024/12/2947二、分組密碼DES

8個S盒S1、S2、…、S8

每個S盒Sj都是將6比特的課文縮減為4比特；8個S盒總共將48比特的課文縮減為32比特。（請不要忘記S盒的作用是獲得高度的非線性）設一個S盒的輸入為6比特串m=(m1,m2,m3,m4,m5,m6)，輸出為4比特串c=(c1,c2,c3,c4)。將比特串m1m6、m2m3m4m5、c1c2c3c4都用10進制數(shù)來表示，則在表中位于m1m6行m2m3m4m5列的數(shù)就是S盒的輸出c1c2c3c4

。2024/12/2948S1

0123456789101112131415014413121511831061259071015741421311061211953824114813621115129731050315128249175113141006132024/12/2949S20123456789101112131415015181461134972131205101313471528141201106911520147111041315812693215313810131542116712051492024/12/2950S30123456789101112131415010091463155113127114281137093461028514121115121364981530111212510147311013069874151431152122024/12/2951S40123456789101112131415071314306910128511124151138115615034721211014921069012117131513145284331506101138945111272142024/12/2952S50123456789101112131415021241710116853151301491141121247131501510398624211110137815912563014311812711421361509104532024/12/2953S60123456789101112131415012110159268013341475111101542712956113140113829141552812370410113116343212951510111417608132024/12/2954S70123456789101112131415041121415081331297510611130117491101435122158621411131237141015680592361113814107950151423122024/12/2955S80123456789101112131415013284615111109314501271115138103741256110149227114191214206101315358321147410813151290356112024/12/2956二、分組密碼DES我們發(fā)現(xiàn)，每一個S盒的每一行數(shù)字都是0~15的一個排列。換句話說，每一個S盒，當輸入值m1m6固定時，輸出值c1c2c3c4都是輸入值m2m3m4m5的可逆函數(shù)。為什么要這樣設計？為了使擴充變換E→8個S盒（32比特→32比特）整體是一個可逆函數(shù)，必須使得8個S盒總體輸出是8個S盒總體輸入的第2~5、8~11、14~17、20~23、26~29、32~35、38~41、44~47比特的可逆函數(shù)。（回顧擴充變換E：擴充變換E的作用是將32比特的課文膨脹為48比特，且擴充變換后的第1、6、7、12、13、18、19、24、25、30、31、36、37、42、43、48比特為擴充部分。）2024/12/2957二、分組密碼DES置換P：將32比特的課文改變位置順序。見下表。2024/12/2958二、分組密碼DES32比特輸入/32比特輸出的鑰控非線性函數(shù)F鑰控非線性函數(shù)記為Y=F(X,k)，其中X

32為比特輸入，k為48比特密鑰，Y為32比特輸出。F是擴充變換E、群加密、8個S盒、置換P的組合，具體的步驟如下。（1）X為32比特輸入。（2）對X進行擴充變換E，得到48比特課文U。（3）計算U‘+’k=V，其中k是48比特密鑰。（4）將V分為8段，分別進行8個S盒變換，得到32比特課文W。（5）對W進行置換P，得到32比特輸出Y。2024/12/2959二、分組密碼DES2024/12/2960二、分組密碼DES輪函數(shù)：輪函數(shù)是Feistel網(wǎng)絡，輸入、輸出均為64比特：2024/12/2961二、分組密碼DESDES是迭代型分組密碼，明文分組長度為64比特。加密算法步驟如下。（1）對明文分組進行初始置換IP。（2）進入16輪迭代，輪函數(shù)就是如前所述的Feistel網(wǎng)絡，其中第m輪迭代所用的子密鑰為k(m)，m=1~16；第16輪迭代是特殊的一輪，只進行“覆蓋”，不進行“左右交換”。（3）進行初始置換IP的逆變換IP-1。2024/12/29622024/12/2963二、分組密碼DESDES的用戶密鑰（密鑰種子）是64比特長，而其中的第8、16、24、32、40、48、56、64比特是奇偶校驗位。因此，真正有效的用戶密鑰（密鑰種子）是56比特長。然而DES的加密密鑰總長度是48×16=766比特。因此，56比特的用戶密鑰需要擴展為48×16=768比特的加密密鑰。密鑰擴展算法描述如下。DES加密算法的密鑰擴展算法需要用到兩個縮減變換PC-1和PC-2，其中PC-1是將64比特長的串縮減為56比特；PC-2是將56比特長的串縮減為48比特。2024/12/2964二、分組密碼DES

PC-1：2024/12/2965二、分組密碼DESPC-2：2024/12/2966二、分組密碼DES密鑰擴展算法還需要用到循環(huán)左移變換LSj，j=1~16。其中LSj表示生成第j輪子密鑰k(j)時的循環(huán)左移變換。這里規(guī)定：當j=1，2，9，16時，LSj為循環(huán)左移1位；當j=3~8或10~15時，LSj為循環(huán)左移2位。每一個循環(huán)左移變換的輸入和輸出都是28比特串。

2024/12/29672024/12/2968二、分組密碼DESDES的解密算法與加密算法相同，也是IP→16輪迭代（最后一輪是特殊輪）→IP-1。僅僅各輪迭代所用的子密鑰不同。若加密算法各輪迭代所用的子密鑰為{k(1)，k(2)，~，k(16)}，則解密算法各輪迭代所用的子密鑰為{k(16)，k(15)，~，k(1)}。2024/12/2969二、分組密碼DES對DES評價的現(xiàn)有結(jié)果DES簡單快速，所使用的計算部件都是計算機的最常用操作。DES是加解密相似的。DES加密算法的第一個計算部件是IP，最后一個計算部件是IP-1，都沒有密鑰的參與。在已知明文攻擊之下，IP和IP-1都可以剝?nèi)ィ瑳]有任何安全性功能。DES的S盒的設計細節(jié)沒有公開。DES的用戶密鑰長度（有效長度）是56比特，對于越來越快速的窮舉搜索攻擊，安全強度似乎已經(jīng)不夠了。2024/12/2970二、分組密碼DES設DES的加密算法為y=DES(x,k)，其中k為密鑰種子，則當x和k都取補時，函數(shù)值取補。對于密鑰種子k，如果DES-1(·,k)=DES(·,k)，則稱k為一個弱密鑰。根據(jù)DES的密鑰擴展算法，不難看出有4個弱密鑰：k=(0,…,0)；k=(1,…,1)；k=(0,…,0,1,…,1)；k=(1,…,1,0,…,0)。如果有兩個密鑰種子k1和k2，使得DES(·,k1)=DES(·,k2)，則稱(k1,k2)為一個半弱密鑰對。已經(jīng)發(fā)現(xiàn)DES有12個半弱密鑰對。

（以上三條說明，明文、密鑰、密文之間存在一些簡單的關系，隨機性不足）2024/12/2971二、分組密碼DES研究表明，要使密文每個比特都是明文所有比特和密鑰所有比特的復合函數(shù)，需要將DES的輪函數(shù)進行5輪以上的迭代。人們用χ2檢驗證明，用隨機密鑰種子并8輪迭代，就能使明文和密文基本上不相關。從這一角度來看，DES算法的16輪迭代是足夠了。2024/12/2972三、分組密碼IDEA運算‘+’：兩個長度為16的比特串x和y。x‘+’y表示x和y做逐位模2加運算（逐比特異或）。運算“+”：將長度為16的比特串x和y看作是“≥0，且<216”的整數(shù)。x“+”y表示x和y做模216加運算。運算×：將長度為16的比特串x和y看作是“≥1，且<216+1”的整數(shù)。其中將全0串看作是216。x×y表示x和y做模216+1乘運算。（注意：216+1是素數(shù)）2024/12/2973三、分組密碼IDEA三種運算的代數(shù)結(jié)構三種運算都是交換群運算（Abel群運算）。運算‘+’的中性元是(0000000000000000)。運算“+”的中性元是(0000000000000000)。運算×的中性元是(0000000000000001)。關于群運算‘+’，任何非中性元的次數(shù)都是2。關于群運算“+”，非中性元的次數(shù)有2，22，23，…，216。關于群運算×，非中性元的次數(shù)有2，22，23，…，216。2024/12/2974三、分組密碼IDEA三種運算的密碼學性質(zhì)設z=x‘+’y。則z的一個比特僅僅依賴于x和y在相同位置上的比特值，毫無擴散能力。設z=x“+”y。則z的一個比特依賴于x和y在相同位置及以下位置上的比特值，具有單向擴散能力。設z=x×y。則z的一個比特依賴于x和y在所有位置上的比特值，具有雙向擴散能力?！?’與“+”的結(jié)構差異很大；“+”與×雖然具有同構關系，但這種同構關系卻表現(xiàn)為一種“離散對數(shù)”的關系。將它們組合在一起使用，可以破壞任何一種群結(jié)構。2024/12/2975三、分組密碼IDEAIDEA算法輪函數(shù)輪函數(shù)為M=F(m,z)。其中m是明文，它是長度為64的比特串；M是密文，它是長度為64的比特串；z是密鑰，它是長度為96的比特串。將明文m分為4個子塊：m=(m1,m2,m3,m4)，其中每個子塊長度為16。將密文M分為4個子塊：M=(M1,M2,M3,M4)，其中每個子塊長度為16。將密鑰z分為6個子塊：z=(z1,z2,z3,z4,z5,z6)，其中每個子塊長度為16。三種運算‘+’、“+”、×分別為前面所述。2024/12/2976三、分組密碼IDEA輪函數(shù)算法描述如下。（1）(m1,m2,m3,m4)(×,“+”,“+”,×)(z1,z2,z3,z4)=(a,b,c,d)。（2）(a‘+’c,b‘+’d)=(e,f)。（3）(((e×z5)“+”f)×z6)=u，u“+”(e×z5)=v。（4）(a,b,c,d)(‘+’,‘+’,‘+’,‘+’)(u,v,u,v)=(w1,w2,w3,w4)。（5）(w1,w3,w2,w4)=(M1,M2,M3,M4)。2024/12/29772024/12/2978三、分組密碼IDEA輪函數(shù)的第（1）步稱為群加密，使用密鑰(z1,z2,z3,z4)，將(m1,m2,m3,m4)變?yōu)?a,b,c,d)。輪函數(shù)的第（2）（3）（4）步稱為MA變換，使用密鑰(z5,z6)

，將(a,b,c,d)變?yōu)?w1,w2,w3,w4)。輪函數(shù)的第（5）步稱為塊置換，不使用密鑰，僅僅把第二子塊與第三子塊對調(diào)，將(w1,w2,w3,w4)變?yōu)?M1,M2,M3,M4)。我們將有以下的結(jié)論：MA變換是對合變換（自反變換）；塊置換是對合變換；群加密雖然不是對合變換，但其逆變換也是群加密，只不過所用的密鑰不同。2024/12/2979三、分組密碼IDEA因為(a,b,c,d)(×,“+”,“+”,×)(z1-1,-z2,-z3,z4-1)=(m1,m2,m3,m4)，其中z1-1是z1的×逆元，-z2是z2的“+”逆元，-z3是z3的“+”逆元，z4-1是z4的×逆元。所以第（1）步的逆運算仍然是群加密，只不過所使用的密鑰變成了(z1-1,-z2,-z3,z4-1)，將(a,b,c,d)變?yōu)?m1,m2,m3,m4)。2024/12/2980三、分組密碼IDEA因為(w1‘+’w3,w2‘+’w4)=(e,f)，(((e×z5)“+”f)×z6)=u，u“+”(e×z5)=v，(w1,w2,w3,w4)(‘+’,‘+’,‘+’,‘+’)(u,v,u,v)=(a,b,c,d)，所以第（2）（3）（4）步的逆運算仍然是MA變換，所使用的密鑰仍然是(z5,z6)

，將(w1,w2,w3,w4)變?yōu)?a,b,c,d)。2024/12/2981三、分組密碼IDEA因為

(M1,M3,M2,M4)=(w1,w2,w3,w4)，所以第（5）步的逆運算仍然是塊置換，將(M1,M3,M2,M4)變?yōu)?w1,w2,w3,w4)。綜上所述，有：群加密的逆運算還是群加密，只是使用的密鑰不同；MA變換的逆運算還是MA變換，使用的密鑰也相同；塊置換的逆運算還是塊置換。2024/12/2982三、分組密碼IDEA完整的加密算法：8輪迭代分組密碼IDEA的完整加密算法是連續(xù)8次使用輪函數(shù)，不過第8輪與前7輪有所不同。前7輪是普通輪，輪函數(shù)的運算步驟如前所述為：群加密→MA變換→塊置換。第8輪是特殊輪，輪函數(shù)的運算步驟為：群加密→MA變換→群加密。因此，分組密碼IDEA的完整加密算法如下：2024/12/2983三、分組密碼IDEA群加密→MA變換→塊置換→群加密→MA變換→塊置換→群加密→MA變換→塊置換→群加密→MA變換→塊置換→群加密→MA變換→塊置換→群加密→MA變換→塊置換→群加密→MA變換→塊置換→群加密→MA變換→群加密。2024/12/2984三、分組密碼IDEA解密算法考察在加密算法中的“塊置換→群加密”組合結(jié)構。設該組合結(jié)構的輸入為(g1,g2,g3,g4)，群加密的密鑰為(q1,q2,q3,q4)，輸出為(r1,r2,r3,r4)，則組合結(jié)構的算法描述如下：

(g1,g3,g2,g4)=(h1,h2,h3,h4)；(h1,h2,h3,h4)(×,“+”,“+”,×)(q1,q2,q3,q4)=(r1,r2,r3,r4)。2024/12/2985三、分組密碼IDEA這個結(jié)構還可以描述如下：(g1,g2,g3,g4)

(×,“+”,“+”,×)(q1,q3,q2,q4)=(r1,r3,r2,r4)；(r1,r2,r3,r4)=(r1,r2,r3,r4)。這就是說，“塊置換→群加密”組合結(jié)構中的塊置換和群加密的順序可以顛倒，描述為“群加密→塊置換”。只不過在顛倒順序時，密鑰四個子塊中的第二、第三子塊交換位置，從(q1,q2,q3,q4)變?yōu)?q1,q3,q2,q4)。2024/12/2986三、分組密碼IDEA再注意到塊置換和群加密各自的逆運算也是它們自己。因此，結(jié)論如下：“塊置換→群加密”組合結(jié)構的逆運算還是“塊置換→群加密”組合結(jié)構。如果“塊置換→群加密”的群加密的密鑰是(q1,q2,q3,q4)，且逆運算也采用“塊置換→群加密”順序，則逆運算群加密的密鑰就是(q1-1,-q3,-q2,q4-1)。2024/12/2987三、分組密碼IDEAIDEA的解密算法是加密算法的逆運算。從前面的敘述，我們已經(jīng)得到如下事實：群加密的逆運算還是群加密；MA變換的逆運算還是MA變換；塊置換的逆運算還是塊置換；“塊置換→群加密”組合結(jié)構的逆運算還是“塊置換→群加密”組合結(jié)構。因此，IDEA的解密算法與加密算法完全相同，僅僅是密鑰有所不同。以下是加解密算法密鑰對照。2024/12/2988三、分組密碼IDEA加密算法密鑰第一輪(z11,z12,z13,z14)；(z15,z16)第二輪(z21,z22,z23,z24)；(z25,z26)第三輪(z31,z32,z33,z34)；(z35,z36)第四輪(z41,z42,z43,z44)；(z45,z46)第五輪(z51,z52,z53,z54)；(z55,z56)第六輪(z61,z62,z63,z64)；(z65,z66)第七輪(z71,z72,z73,z74)；(z75,z76)第八輪(z81,z82,z83,z84)；(z85,z86)；(z91,z92,z93,z94)2024/12/2989三、分組密碼IDEA解密算法密鑰第一輪(z91-1,-z92,-z93,z94-1)；(z85,z86)第二輪(z81-1,-z83,-z82,z84-1)；(z75,z76)第三輪(z71-1,-z73,-z72,z74-1)；(z65,z66)第四輪(z61-1,-z63,-z62,z64-1)；(z55,z56)第五輪(z51-1,-z53,-z52,z54-1)；(z45,z46)第六輪(z41-1,-z43,-z42,z44-1)；(z35,z36)第七輪(z31-1,-z33,-z32,z34-1)；(z25,z26)第八輪(z21-1,-z23,-z22,z24-1)；(z15,z16)；(z11-1,-z12,-z13,z14-1)2024/12/2990三、分組密碼IDEA密鑰擴展算法IDEA加密算法中所使用的密鑰共有52個子塊，即加密密鑰長度為16×52=832（比特）。用戶密鑰實際上只有128（比特），因此需要一個密鑰擴展算法。密鑰擴展算法如下。將128比特的用戶密鑰分為8個子塊，作為加密密鑰的第一個“8個子塊”；將128比特密鑰循環(huán)左移25位，再分為8個子塊，作為加密密鑰的第二個“8個子塊”；將128比特密鑰再次循環(huán)左移25位，再分為8個子塊，作為加密密鑰的第三個“8個子塊”；…；直到有52個子塊作為加密密鑰。2024/12/2991四、分組密碼RijndaelAES競爭過程及RIJNDAEL概述

鑒于DES的沒落，美國政界和商界一直在尋求高強度、高效率的替代算法。1997年，美國國家標準技術研究所（NIST）為了履行其法定職責，發(fā)起了一場推選用于保護敏感的（無密級的）聯(lián)邦信息的對稱密鑰加密算法的活動。于是密碼學界的精英們紛紛加入競爭的行列，提交自己設計的分組密碼算法。與此同時，NIST制定了用于比較候選算法的評估準則。該評估準則分為三大項：（1）安全性；（2）成本；（3）算法和實現(xiàn)特性。2024/12/2992四、分組密碼Rijndael1998年，NIST宣布接受15個候選算法并提請全世界密碼學界協(xié)助分析這些候選算法。分析的內(nèi)容包括對每個算法的安全性和效率進行初步檢驗。NIST通過對這些初步研究結(jié)果的考察，于1999年8月20日選定了MARS、RC6、RIJNDAEL、Serpent、Twofish等5個算法作為參加決賽的算法。經(jīng)公眾對決賽算法進行更進一步的分析評論，NIST決定推薦RIJNDAEL作為高級加密標準（AES）。2000年10月2日，美國商業(yè)部長NormanY.Mineta宣布，“RIJNDAEL數(shù)據(jù)加密算法”最終獲勝，同時為此而在全球范圍內(nèi)角逐了3年的激烈競爭隨即結(jié)束。2024/12/2993四、分組密碼RijndaelRIJNDAEL的數(shù)學基礎有限域GF(28)；系數(shù)在GF(28)上的多項式。2024/12/2994四、分組密碼Rijndael有限域GF(28)

GF(28)上的元素通常采用字節(jié)值來表示。但為了更方便地運算，此處對GF(28)上的元素采用傳統(tǒng)的多項式表示法。由b7b6b5b4b3b2b1b0構成的一個字節(jié)b看成系數(shù)在{0,1}中的多項式：b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0。在多項式表示中，GF(28)上兩個元素的和仍然是一個次數(shù)不超過7的多項式，其系數(shù)是原來兩個元素對應系數(shù)的模2加（比特異或）。要計算GF(28)上的乘法，必須先確定一個GF(2)上的8次不可約多項式；GF(28)上兩個元素的乘積就是這兩個多項式的重模積。（次數(shù)模此8次不可約多項式，系數(shù)模2）。2024/12/2995四、分組密碼Rijndael此8次不可約多項式稱為模多項式。對于RIJNDAEL密碼，模多項式確定為m(x)=x8+x4+x3+x+1

。模多項式的二進制表示為9比特100011011，十六進制表示為“11B”。以下是一個乘法的例子：

(x6+x4+x2+x+1)×(x7+x+1)=x7+x6+1(mod2,mod

m(x))；或者“01010111”ד10000011”=“11000001”；或者“57”ד83”=“C1”。2024/12/2996四、分組密碼Rijndael另外，對于u∈GF(28)，u≠0，計算u的乘法逆元v可直接采用GF(2)上多項式的歐幾里德擴充算法得u(x)u(x)+m(x)h(x)=1(mod2)，或u(x)u(x)=1(mod2,modm(x))，其中u=u(x)，v=v(x)。所計算出的v就是u的乘法逆元，即u(x)×v(x)=1或者u×v=1。

2024/12/2997四、分組密碼Rijndael系數(shù)在GF(28)上的多項式

4個字節(jié)的向量可以表示為系數(shù)在GF(28)上的次數(shù)小于4的多項式。多項式的加法就是對應系數(shù)相加；換句話說，多項式的加法就是4字節(jié)向量的逐比特異或。多項式的乘法運算必須要取模M(x)=x4+1，這樣使得次數(shù)小于4的多項式的乘積仍然是一個次數(shù)小于4的多項式。即(a3x3+a2x2+a1x+a0)×(b3x3+b2x2+b1x+b0)=c3x3+c2x2+c1x+c0

，2024/12/2998四、分組密碼Rijndael其中c0=a0b0+a1b3+a2b2+a3b1；c1=a0b1+a1b0+a2b3+a3b2；c2=a0b2+a1b1+a2b0+a3b3；c3=a0b3+a1b2+a2b1+a3b0。注意所有的加法和乘法運算都是在域GF(28)中的。可以將上述計算表示為

2024/12/2999四、分組密碼Rijndael定理

系數(shù)在GF(28)上的多項式b3x3+b2x2+b1x+b0是模(x4+1)可逆的，當且僅當以下矩陣在GF(28)上可逆。2024/12/29100四、分組密碼RijndaelRIJNDAEL的設計標準RIJNDAEL密碼的設計力求滿足以下3條標準：（1）抗所有已知的攻擊。（2）在多個平臺上速度快，編碼緊湊。（3）設計簡單。2024/12/29101四、分組密碼RijndaelRIJNDAEL的算法說明

RIJNDAEL的明文分組稱為狀態(tài)，所有的操作都在狀態(tài)之間進行。狀態(tài)可以用以字節(jié)為元素的矩陣陣列圖表示，該陣列有4行，列數(shù)記為Nb，Nb等于分組長度除以32。密鑰種子（在原文中稱為密碼密鑰CipherKey）類似地用一個以字節(jié)為元素的矩陣陣列圖表示，該陣列有4行，列數(shù)記為Nk，Nk等于分組長度除以32。2024/12/29102四、分組密碼Rijndael下表就是Nb=6的狀態(tài)和Nk=4的密鑰種子。一個明文分組按a00a10a20a30a01a11a21a31…的順序影射到狀態(tài)陣列中。同理，密鑰種子按k00k10k20k30k01k11k21k31…的順序影射到密鑰種子陣列中。

a00

a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00

k01k02k03k10k11k12k13k20k21k22k23k30k31k32k332024/12/29103四、分組密碼Rijndael

輪函數(shù)

RIJNDAEL的輪函數(shù)由四個不同的計算部件所組成，分別是：字節(jié)代替（ByteSub）；行移位（ShiftRow）；列混合（MixColumn）；加密鑰（AddRoundKey）。1.字節(jié)代替（ByteSub）是將狀態(tài)陣列的每個字節(jié)做相同的變換，該變換由以下兩個子變換所合成：2024/12/29104（1）首先，將字節(jié)看作GF(28)上的元素，映射到自己的乘法逆；0字節(jié)影射到它自身。（2）其次，將字節(jié)看作GF(2)上的8維向量，做如下的（GF(2)上的；可逆的）仿射變換：

2024/12/29105以上兩個子變換所合成的字節(jié)代替采用一個8比特輸入/8比特輸出的S盒來實現(xiàn)。2.行移位（SHiftRow）是將狀態(tài)陣列的各行進行循環(huán)移位，不同狀態(tài)行的位移量不同。第0行不移動，第一行循環(huán)左移C1個字節(jié)，第二行循環(huán)左移C2個字節(jié)，第三行循環(huán)左移C3個字節(jié)。位移量(C1,C2,C3)的選取與Nb有關，當Nb=4或6時一般取(C1,C2,C3)=(1,2,3)。

3.列混合（MixColumn）是將狀態(tài)陣列的每個列視為系數(shù)在GF(28)上、次數(shù)小于4的多項式，被同一個固定的多項式c(x)進行模x4+1乘法。當然要求c(x)是模x4+1可逆的多項式，否則列混合變換就是不可逆的，因而會使不同的明文分組具有相同的對應密文分組。RIJNDAEL的設計者所給出的c(x)為（系數(shù)用16進制數(shù)表示）：

2024/12/29106c(x)='03'x3+'01'x2+'01'x+'02'c(x)是與x4+1互素的，因此是模x4+1可逆的。由前面的討論知，將狀態(tài)陣列的每個列視為GF(28)上的4維向量，列混合運算可表示為GF(28)上的可逆線性變換：2024/12/29107這個運算需要做GF(28)上的乘法。但由于所乘的因子是三個固定的元素02、03、01，所以這些乘法運算仍然是比較簡單的（注意到乘法運算所使用的模多項式為m(x)=x8+x4+x3+x+1）。設一個字節(jié)為b=(b7b6b5b4b3b2b1b0)，則bב01’=b；bב02’=(b6b5b4b3b2b1b00)+(000b7b70b7b7)；bב03’=bב01’+b×’02’。（請注意，加法為取模2的加法，即逐比特異或）2024/12/291084.加密鑰（AddRoundKey）是將單輪子密鑰陣列簡單地與課文陣列進行比特異或。這里當然要求子密鑰陣列與課文陣列是同階的。

綜上所述，組成RIJNDAEL輪函數(shù)的計算部件簡潔快速，功能互補。輪函數(shù)的偽C代碼如下：Round(State,RoundKey){

ByteSub(State)

ShiftRow(State)

MixColumn(State)

AddRoundKey(State,RoundKey)}

2024/12/291091.字節(jié)代替（ByteSub）2024/12/291102.行移位（SHiftRow）2024/12/291113.列混合（MixColumn）2024/12/291124.加密鑰（AddRoundKey）2024/12/29113結(jié)尾輪是特殊輪，輪函數(shù)與前面各輪不同，將MixColumn這一步去掉。即為FinalRound(State,RoundKey){

ByteSub(State)

ShiftRow(State)

AddRoundKey(State,RoundKey)}在以上的偽C代碼記法中，Round、FinalRound、ByteSub、ShiftRow、MixColumn、AddRoundKey

等函數(shù)都在指針State、RounKey所指向的陣列上進行運算。2024/12/29114四、分組密碼Rijndael迭代的輪數(shù)記為Nr，Nr與Nb和Nk有關，其中Nb是明文陣列的列數(shù)，Nk是密鑰種子陣列的列數(shù)。下表給出了Nr與Nb和Nk的關系。NrNb=4Nb=6Nb=8Nk=4101214Nk=6121214Nk=81414142024/12/29115四、分組密碼Rijnd