1、第4章 分 組 密 碼 4.1 分組密碼的設(shè)計原理與結(jié)構(gòu) 4.2 數(shù)據(jù)加密標(biāo)準(zhǔn) DES與多重DES 4.3 高級加密標(biāo)準(zhǔn) AES 4.4 IDEA算法 4.5 NoeKeon算法 4.6 分組密碼的應(yīng)用模式 分組密碼：Ekk上述n與n滿足nn（為什么？），分別稱為明文分組長度與密文分組長度。分組（塊）密碼概念大多數(shù)實(shí)用分組密碼的明文信號取自于F2，且滿足：n=n，即沒有明文擴(kuò)展?？疾斓囊粋€分組密碼體制，設(shè)K為密鑰空間，n為分組長度，那么加密變換空間為：E=Ek|Ek: 是一一映射,kK。若將 中點(diǎn) 與其所對應(yīng)的二進(jìn)制數(shù) 不加區(qū)別，則每個Ek(kK)可等同一個2n-置換。分組（塊）密碼概念線性部

2、分E分組（塊）密碼概念記 為由所有2n-置換構(gòu)成的所謂2n次對稱群，那么一個好的分組密碼的加密變換空間在 中的位置應(yīng)如下圖所示：4.1 分組密碼的設(shè)計原理一、香農(nóng)安全理論的主要結(jié)論為了克服統(tǒng)計分析，可以采用擴(kuò)散和混淆兩種基本方式。完善保密的密碼系統(tǒng)的充要條件是明文和密文是相互獨(dú)立的。 一次一密體制是完善保密體制，要求： （1） 密鑰的長度至少和明文相同； （2） 每次加密使用不同的密鑰； （3） 密鑰是隨機(jī)性的。 擴(kuò)散：就是使明文的每一位影響密文中的許多位， 也就是密文的每一位受明文的許多位的影響。 這樣可以隱蔽明文的統(tǒng)計特性。 換位變換可以實(shí)現(xiàn)有效的擴(kuò)散，打亂明文字母之間、字母組合之間的統(tǒng)計

3、關(guān)系。 混淆：就是將密文和密鑰之間的統(tǒng)計關(guān)系變得盡可能 復(fù)雜，從而使統(tǒng)計分析更加困難，即使敵手獲 得關(guān)于密文的一些統(tǒng)計特性，也無法推測密鑰。 使用復(fù)雜的非線性替代變換可以達(dá)到比較好的混淆效果。 分組密碼的基本設(shè)計原則針對安全性的一般設(shè)計原則分組長度n要足夠大，以防止對明文的窮搜攻擊奏效。密鑰空間K要足夠大，以防止對密鑰的窮搜攻擊奏效?；煜好芪呐c明文、密鑰的關(guān)系復(fù)雜化，非線性的、且處處勻強(qiáng)。分組密碼的基本設(shè)計原則（續(xù)）擴(kuò)散：要使密鑰每一位數(shù)字影響密文的一半以上數(shù)字以防止對密鑰進(jìn)行逐段破譯，而且明文的每一位數(shù)字也應(yīng)影響密文的一半以上數(shù)字以便隱蔽明文數(shù)字的統(tǒng)計特性。針對實(shí)現(xiàn)的設(shè)計原則要考慮到用軟件

4、還是硬件來實(shí)現(xiàn)所設(shè)計的分組密碼問題。硬件實(shí)現(xiàn)的優(yōu)點(diǎn)是可獲得高速率和形成專用器件，而軟件實(shí)現(xiàn)的優(yōu)點(diǎn)是靈活性強(qiáng)（便于移植）、代價低。軟件實(shí)現(xiàn)的設(shè)計原則：使用子塊和簡單的運(yùn)算。密碼運(yùn)算在子塊上進(jìn)行，要求子塊的長度能自然地適應(yīng)軟件編程，比如8、16或32比特等；在軟件實(shí)現(xiàn)中，按比特操作（如置換）是難于實(shí)現(xiàn)的，因此應(yīng)該盡量避免它。子塊上所進(jìn)行的密碼運(yùn)算應(yīng)該是一些易于軟件實(shí)現(xiàn)的運(yùn)算，最好是用一些標(biāo)準(zhǔn)處理器所具有的那些基本指令，比如加法、乘法和移位等。分組密碼的基本設(shè)計原則（續(xù)）硬件實(shí)現(xiàn)的設(shè)計原則：加密和解密應(yīng)具有相似性（最好只是在密鑰的使用方式上存在不同，其余皆同）以便可以用同樣的器件來實(shí)現(xiàn)。盡量使用規(guī)則

5、結(jié)構(gòu)，且應(yīng)符合國際的統(tǒng)一標(biāo)準(zhǔn)，以便適合于用超大規(guī)模集成電路來實(shí)現(xiàn)。值得注意的是：分組密碼常常以乘積密碼的方式來設(shè)計。由合理選擇的許多子密碼（相繼使用）構(gòu)成的乘積密碼既可實(shí)現(xiàn)良好的混亂、又可實(shí)現(xiàn)良好的擴(kuò)散。分組密碼的基本設(shè)計原則（續(xù)）一般系統(tǒng)中將替代和置換作為基本單元使用。而它們可用簡單的電路（或軟件實(shí)現(xiàn)）來完成，這也就是通常所說的 S 盒和 P 盒。 二、分組密碼的結(jié)構(gòu)S盒substitution box ；P盒permutation box 。例如：下圖為8-bit 輸入輸出的 P 盒和 3 bit 輸入輸出的 S 盒。01234567原 8 Bit的序號！36071245置換后的 8 Bi

6、t的序號！101輸入 的3 Bit！0000010000000001111順序輸入十進(jìn)制數(shù)：0123456724506713乘積密碼系統(tǒng)是代換盒與置換盒變換的組合，兩者結(jié)合得到的密碼系統(tǒng)比單獨(dú)一種更強(qiáng)。這一密碼被IBM 用于LUCIFER系統(tǒng)，后來成為數(shù)據(jù)加密標(biāo)準(zhǔn) Data Encryption Standard (DES)的基礎(chǔ)。 SP 結(jié)構(gòu)（替代置換網(wǎng)絡(luò)）： 每輪處理整個分組數(shù)據(jù)，加解密不相似。分組密碼的總體結(jié)構(gòu)有兩種類型：Feistel 結(jié)構(gòu)：每輪處理一半數(shù)據(jù)，加解密相似。SP結(jié)構(gòu)是Feistel結(jié)構(gòu)的推廣，結(jié)構(gòu)更加清晰， S 一般稱為混淆層，主要起混淆作用； P 一般稱為擴(kuò)散層，主要起

7、擴(kuò)散作用。DES是 Feistel結(jié)構(gòu)的代表，AES是SP結(jié)構(gòu)的一個代表。 4.2 數(shù)據(jù)加密標(biāo)準(zhǔn) DES4.2 數(shù)據(jù)加密標(biāo)準(zhǔn) DES 4.2 數(shù)據(jù)加密標(biāo)準(zhǔn) DESDES 是現(xiàn)代分組密碼的一個里程碑。從1977年提出（原計劃用10年）到最近被認(rèn)為不安全，經(jīng)歷了20多年（將被AES取代），是分組密碼設(shè)計的一個典范。 一、DES的結(jié)構(gòu) 明文分組： 64 bit 密文分組： 64 bit密鑰： 64 bit，其中8bit為校驗(yàn)位，實(shí)際 56 bit輪數(shù)： 16 輪（圈）加密函數(shù)： 直接異或，8個 6-4 S盒。32 Bit！32 Bit！64 Bit！48 Bit！一共16 輪！64 bit！DES的

8、描述在前面加密算法的圖示中，初始置換IP的定義為：可以求出IP的逆IP-1為DES的加密函數(shù)：8個6-4 S盒！48 bit！48 bit！32 bit！48=32 bitDES的描述在前面函數(shù)f的圖示中，擴(kuò)展置換E的定義為：置換P的定義為：DES的描述在前面函數(shù)f的圖示中，8個S-盒S1,S2,S3,S4,S5,S6,S7,S8的定義見書p.233表7.3.3。每個S-盒Si(i=1,2,8)均以6bit作為輸入、而輸出4bit，茲以下例來說明其計算過程。求S1(010011)：（找到S-盒S1如下）于是，S1(010011)=0110。密鑰生成：64 bit輸入密鑰！56 bit56 bi

9、t48 bit28 bitDES的描述密鑰擴(kuò)展. 各輪迭代一共使用16個加密子密鑰K1,K2,K16，它們依據(jù)所給56bit主密鑰K按下述擴(kuò)展算法產(chǎn)生：K(56bit)PC-1(置換)LS1LS1LS16LS16PC-2PC-2K1(48bit)K16(48bit)(選取：有舍棄)其中，DES的描述在前面密鑰擴(kuò)展的圖示中，置換PC-1與選取PC-2分別為：Feistel 結(jié)構(gòu)證明 即可。（設(shè) ，說明A=Ri-1,B=Li-1）小規(guī)模DES舉例DES的描述fKi(48bit)第 i輪迭代正確性. 只需對下面圖示的變換 ：DES的解密過程：經(jīng)過初始置換變?yōu)榻?jīng)過第一輪：經(jīng)過第二輪：經(jīng)過第三輪：如此經(jīng)

10、過15輪，最后一輪不交換，得到再經(jīng)過逆初始置換，得到明文。寫法：二、DES的特點(diǎn) 除密鑰順序之外，加密和解密步驟完全相同； 主要的批評：密鑰太短，迭代次數(shù)可能太少， S盒可能存在不安全隱患。 差分分析：通過分析明文對的差值（異或）對密文對的 差值的影響來恢復(fù)某些密鑰比特。 窮舉攻擊：現(xiàn)在人們利用網(wǎng)絡(luò)計算可以在20多小時 破譯56位的DES。DES已變得不安全了。 線性分析：一種已知明文攻擊，它試圖建立起明文、 密文和密鑰的一組近似線性方程。 DES的設(shè)計特色（續(xù)）S-盒的設(shè)計準(zhǔn)則還沒有完全公開。一些密碼學(xué)家懷疑美國NSA(the National Se-curity Agency)設(shè)計S-盒時

11、隱藏了“陷門”，使得只有他們才知道破譯算法，但沒有證據(jù)能表明這一點(diǎn)。1976年，美國NSA披露了S-盒的下述幾條設(shè)計原則：每個S-盒的每一行是整數(shù)015的一個全排列；每個S-盒的輸出都不是其輸入的線性或仿射函數(shù)；改變?nèi)我籗-盒任意1bit的輸入，其輸出至少有2bit發(fā)生變化；DES的設(shè)計特色（續(xù)）對任一S-盒的任意6bit輸入x,S(x)與S(x001100)至少有2bit不同；對任一S-盒的任意6bit輸入x，及,0,1，都有S(x)S(x1100)；對任一S-盒，當(dāng)它的任一位輸入保持不變，其它5位輸入盡情變化時，所有諸4bit輸出中，0與1的總數(shù)接近相等。DES的設(shè)計特色（續(xù)）DES的安全

12、問題DES的安全性完全依賴于所用的密鑰。自從其算法作為標(biāo)準(zhǔn)公開以來，人們對它的安全性就有激烈的爭論。下面簡要介紹20年來人們就其安全方面的一些主要研究結(jié)果。取反特性. 對于明文組M，密文組C和主密鑰K，若C=DESK(M)則 ，其中 , 和 分別為M,C和K的逐位取反。證明. 若以K為主密鑰擴(kuò)展的16個加密子密鑰記為K1,K2,K16，則以 為主密鑰擴(kuò)展的16個加密子密鑰為注意到 ，不難看出注意到 ，不難看出 DES的安全問題（續(xù)）上述取補(bǔ)特性會使DES在選擇明文攻擊下所需工作量減少一半：攻擊者為破譯所使用的密鑰，選取兩個明密文對 與 ，并對于可能密鑰 ，計算出DESK(M)=C。若C=C1或

13、 ，則分別說明K或 為實(shí)際密鑰。DES的安全問題（續(xù)）弱密鑰與半弱密鑰. 大多數(shù)密碼體制都有某些明顯的“壞密鑰”，DES也不例外。對于 ，若由K擴(kuò)展出來的加密子密鑰為：K1,K2,K15,K16，而由K擴(kuò)展出來的加密子密鑰卻是：K16,K15,K2,K1，即有 ，則稱K與K互為對合。下面我們分析一下 中到底有些什么樣的對合對？DES的安全問題（續(xù)）在DES的主密鑰擴(kuò)展中，C0與D0各自獨(dú)立地循環(huán)移位來產(chǎn)生加(解)密子密鑰。若C0與D0分別是00,11,10,01中任意一個的14次重復(fù)，則因這樣的C0與D0都對環(huán)移(無論左或右)偶數(shù)位具有自封閉性，故若 ，則由K擴(kuò)展出來的加密子密鑰為：K1,K2

14、,K2,K2,K2,K2,K2,K2,K1,K1,K1,K1,K1,K1,K1,K2；DES的安全問題（續(xù)）把C0與D0各自左環(huán)移一位得C1與D1，設(shè) ，則由K擴(kuò)展出來的加密子密鑰為：K2,K1,K1,K1,K1,K1,K1,K1,K2,K2,K2,K2,K2,K2,K2,K1。因此，由上述C0、D0導(dǎo)致的K與K互為對合；實(shí)際上， 除了這些以外，在 中似乎不再有其它的對合對了。DES的安全問題（續(xù)）對于 ，若K是自己的對合，則稱K為DES的一個弱密鑰；若K存在異于自己的對合，則稱K為DES的一個半弱密鑰。顯然，C0與D0分別是00,11,10,01中任意一個的14次重復(fù)的情況共有42=16種，

15、其中C0與D0分別是00,11中任意一個的14次重復(fù)的情況(計22=4種)對應(yīng)弱密鑰；剩下的(16-4=12種)對應(yīng)半弱密鑰。DES的安全問題（續(xù)）弱密鑰與半弱密鑰直接引起的“危險”是在多重使用DES加密中，第二次加密有可能使第一次加密復(fù)原；另外，弱密鑰與半弱密鑰使得擴(kuò)展出來的諸加密子密鑰至多有兩種差異，如此導(dǎo)致原本多輪迭代的復(fù)雜結(jié)構(gòu)簡化和容易分析。所幸在總數(shù)256個可選密鑰中，弱密鑰與半弱密鑰所占的比例極小，如果是隨機(jī)選擇，(半)弱密鑰出現(xiàn)的概率很小，因而其存在性并不會危及DES的安全。DES的安全問題（續(xù)）密文與明文、密文與密鑰的相關(guān)性. 人們的研究結(jié)果表明：DES的編碼過程可使每個密文比

16、特都是所有明文比特和所有密鑰比特的復(fù)雜混合函數(shù)，而要達(dá)到這一要求至少需要DES的迭代：5輪。人們也用2-檢驗(yàn)證明：DES迭代8輪以后，就可認(rèn)為輸出和輸入不相關(guān)了。DES的安全問題（續(xù)）密鑰搜索機(jī). 在對DES安全性的批評意見中，較一致的看法是DES的密鑰太短！其長度56bit，致使密鑰量僅為2561017，不能抵抗窮搜攻擊，事實(shí)證明的確如此。1997年1月28日，美國RSA數(shù)據(jù)安全公司在RSA安全年會上發(fā)布了一項(xiàng)“秘密密鑰挑戰(zhàn)”競賽，分別懸賞1000美金、5000美金和10000美金用于攻破不同長度的RC5密碼算法，同時還懸賞10000美金破譯密鑰長度為56bit的DES。RSA公司發(fā)起這場挑

17、戰(zhàn)賽是為了調(diào)查在Internet上分布式計算的能力，并測試不同密鑰長度的RC5算法和密鑰長度為56bit的DES算法的相對強(qiáng)度。DES的安全問題（續(xù)）結(jié)果是：密鑰長度為40bit和48bit的RC5算法被攻破；美國克羅拉多州的程序員Verser從1997年3月13日起用了96天的時間，在Internet上數(shù)萬名志愿者的協(xié)同工作下，于1997年6月17日成功地找到了DES的密鑰，獲得了RSA公司頒發(fā)的10000美金的獎勵。這一事件表明，依靠Internet的分布式計算能力，用窮搜方法破譯DES已成為可能。因此，隨著計算機(jī)能力的增強(qiáng)與計算技術(shù)的提高，必須相應(yīng)地增加密碼算法的密鑰長度。DES的安全問

18、題（續(xù)）1977年，Diffe和Hellman曾建議制造每秒能測試106個密鑰的VLSI芯片，將這樣的100104個芯片并行操作搜索完整個密鑰空間大約需1天時間。他們估計制造這樣一臺機(jī)器需耗資大約2000萬美金。1993年，Wiener給出了一個詳細(xì)的設(shè)計密鑰搜索機(jī)的方案。他建議制造每秒能測試5107個密鑰的芯片，基于這種芯片的機(jī)器將流水作業(yè)，使得16次加密同時DES的安全問題（續(xù)）發(fā)生。目前制造這種芯片每片需耗資10.5美金，耗資10萬美金能建造一個由5760個芯片組成的框架，這使得搜索一個密鑰平均大約需要1.5天。使用十個這樣框架的機(jī)器將耗資100萬美金，搜索一個密鑰平均大約3.5小時。據(jù)

19、新華社1998年7月22日消息,電子邊境基金學(xué)會(EFF)使用一臺25萬美金的電腦在56小時內(nèi)破譯了56位密鑰的DES。DES的安全問題（續(xù)）DES的攻擊方法.目前攻擊DES的主要方法有時間-空間權(quán)衡攻擊、差分攻擊、線性攻擊和相關(guān)密鑰攻擊等方法，在這些攻擊方法中，線性攻擊方法是最有效的一種方法。除了上面介紹的幾個方面外，20年來人們還發(fā)表了許多有關(guān)DES的其它方面的研究文章，這些研究不僅深入分析、檢驗(yàn)了DES的各個方面，而且也大大地推動了密碼學(xué)的研究和發(fā)展。DES的安全問題（續(xù)）三、 多重 DES 為了提高安全性，防止窮舉攻擊，DES還有一些多重形式。 雙重DES： 但存在中間相遇攻擊：（已知

20、一對明密文）窮舉k2！窮舉k1！三重DES： 中間一層用解密形式是為了可以利用三重DES對單重DES加密的密文進(jìn)行解密（k1和k3反序） DESk1mDESk21DESk3cDESk11DESk2DESk31 4.3 高級加密標(biāo)準(zhǔn) AES 1997年美國國家標(biāo)準(zhǔn)技術(shù)研究所（NIST）征集AES (advanced encryption standard)，要求：（1）比三重DES快且至少與它一樣安全；（2）分組長度為128bit，密鑰長為128bit，192bit和 256bit；（3）算法要能抵抗已知的密碼分析方法，無明顯漏洞； （4）算法實(shí)現(xiàn)要有效率，有一定的靈活性（適應(yīng)不同的 環(huán)境），軟

21、硬件兩種方法實(shí)現(xiàn)。AES候選算法的評估準(zhǔn)則AES評估準(zhǔn)則：安全性；代價；算法和實(shí)現(xiàn)特性。安全性是評估的最重要因素，包括下述要點(diǎn)：算法抗密碼分析的強(qiáng)度，穩(wěn)固的數(shù)學(xué)基礎(chǔ)，算法輸出的隨機(jī)性，以及與其它候選算法比較的相對安全性。AES候選算法的評估準(zhǔn)則（續(xù)）代價是評估的第二個重要方面，它包括：許可要求，在各種平臺上的計算效率（速度）和內(nèi)存空間的需求。由于最終的AES算法在免稅的基礎(chǔ)上要能夠在世界范圍內(nèi)使用，故在選擇過程中必須考慮知識產(chǎn)權(quán)要求和潛在的矛盾；同時也必須考慮算法在各種平臺上的速度。此外，內(nèi)存空間需求和候選算法軟件實(shí)現(xiàn)的限制也是重要的考慮因素。算法和實(shí)現(xiàn)特性包括：靈活性、硬件和軟件適應(yīng)性、算法

22、的簡單性。算法的靈活性應(yīng)包含下述能力：處理的密鑰和分組長度必須要超出最小的支持范圍；在許多不同類型的環(huán)境中能夠安全有效地實(shí)現(xiàn)；可作為序列密碼、雜湊算法實(shí)現(xiàn)，并且可以提供附加的密碼服務(wù)。算法必須容易用軟件和硬件兩種方法實(shí)現(xiàn)，并且有利于有效的固件實(shí)現(xiàn)。算法設(shè)計相對簡單也是一個評估因素。AES候選算法的評估準(zhǔn)則（續(xù)）AES算法的遴選情況收到提交的算法(1998年6月)：15個。通過第一輪評估(1999年8月)：5個。它們分別是：RC6，MARS，RIJNDAEL，SERPENT和TWOFISH。通過第二輪評估(2000年9月)而最終選定為AES者：RIJNDAEL。15種算法參加第一輪評選，5種通過

23、評選： RC6、Rijndael、Serpent、Twofish、Mars2000年獲勝者是 Rijndael 算法，是比利時密碼設(shè)計者所作。 一、AES的總體結(jié)構(gòu)明文分組： 128 bit 密文分組： 128 bit密鑰： 128、192、256 bit輪數(shù)： 10、12、14 輪（圈）加密函數(shù)： 128 bit整體處理，8-8的S盒密鑰生成： 擴(kuò)展、遞歸總體結(jié)構(gòu)： SP結(jié)構(gòu) 在AES中，各種運(yùn)算是以字節(jié)為單位進(jìn)行處理的。輸入為128bit=168bit16個字節(jié)，輸出也是16個字節(jié)，加解密過程中間各步的結(jié)果稱為一個狀態(tài)，每個狀態(tài)都是128bit，排成 44 的字節(jié)數(shù)組：狀態(tài)數(shù)組： 密鑰長度

24、分組長度輪數(shù)AES1284410AES1926412AES2568414AES中密鑰長度可取128、192、256位。通常用4個字節(jié)（32位）的 字 為單位來表示。密鑰長度記為： 分組長度128bit記為 加密和解密的輪數(shù)記為 AES加密過程： Nr1輪 子密鑰！ Nr1輪 迭代！ AddRoundKey ：將每一輪的密鑰與狀態(tài)矩陣直接異或； SubBytes： 將狀態(tài)矩陣的每個字節(jié)進(jìn)行替代； 88的s盒。 ShiftRows： 將狀態(tài)矩陣的行循環(huán)移位； MixColumns： 將狀態(tài)矩陣的列進(jìn)行變換； 書中偽C語言描述！加密算法.RoundKeyByteSubstitute (4*Nb個S-

25、盒)ShiftRowMixColumnM(32*Nb bits)InitKeyFinalKeyByteSubstitute (4*Nb個S-盒)ShiftRowC(32*Nb bits)第i輪迭代(i=1,2,Nr-1)AES的描述AES解密過程：加密過程的逆過程，需要相應(yīng)的逆變換。 AddRoundKey ：將每一輪的密鑰與狀態(tài)矩陣直接異或； InvSubBytes： 逆字節(jié)替代變換，需要8-8的逆s盒。 InvShiftRows： 逆行移位變換； InvMixColumns：逆列混合變換； 書中偽C語言 描述！二、AES中的運(yùn)算 1、 中的運(yùn)算 （字節(jié)運(yùn)算） 中一共有 個元素，可以有多種方

26、式表示，AES 中用多項(xiàng)式表示。 一個字節(jié)8bit： 對應(yīng)多項(xiàng)式： 一個字節(jié)8比特，可以看作 中的一個元素。AES中需要用到 域的運(yùn)算。例如：十六進(jìn)制57，即 0101 0111 對應(yīng)多項(xiàng)式： 注意：有限域的元素個數(shù)不一定是素數(shù)。 因?yàn)槎x的運(yùn)算不同。 83 即 1000 0011 對應(yīng)著 系數(shù)在GF(2)域的多項(xiàng)式全體，模一個既約多項(xiàng)式（沒有非常數(shù)的因式） 關(guān)于加法和乘法構(gòu)成域 。 不是域，因?yàn)榉橇阍夭荒軜?gòu)成乘法群。雖然也有256個元素，但定義的運(yùn)算不同!1、有限域GF(28)中的運(yùn)算 （字節(jié)運(yùn)算） 有限域GF(28)：GF(2)上的8次不可約多項(xiàng)式可擴(kuò)展為有限域GF(28)。加法定義兩個

27、多項(xiàng)式的模2加兩個多項(xiàng)式的對應(yīng)系數(shù)的異或乘法定義為兩個多項(xiàng)式的模乘特別不可約多項(xiàng)式m(x)= x8+x4+x3+x+1對于 域的加法就是多項(xiàng)式對應(yīng)項(xiàng)相加，系數(shù)模二加： 5783 01010111 10000011 11010100D4因?yàn)橐粋€字節(jié)異或本身為0，所以一個字節(jié)的加法逆（負(fù)元）就是它本身。（減法也就是加法，即異或） AES中兩個字節(jié)相加的含義！對于域的乘法，多項(xiàng)式乘以后要模一個8次既約多項(xiàng)式m(x)，AES中選取的 例如：57 83 對應(yīng) 二進(jìn)制表示： 010101111000001111000001十六進(jìn)制表示：57 83c1b(x)= b7x7+b6x6+b5x5+b4x4+b3

28、x3+b2x2+b1x+b0b7b6b5b4b3b2b1b0 xb(x)= b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x ( mod m(x) m(x)= x8+x4+x3+x+1b7=0 b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 xb6b5b4b3b2b1b00 b(x)在字節(jié)內(nèi)左移一位（最后一位補(bǔ)0）b7=1，b(x)在字節(jié)內(nèi)左移一位（最后一位補(bǔ)0）與1B（00011011）逐比特異或x的冪乘運(yùn)算可以重復(fù)應(yīng)用xtime來實(shí)現(xiàn)多項(xiàng)式乘法將上式模m（x）就得到xb(x)。這種運(yùn)算稱為xtime( )運(yùn)算。 (1) 如果 ，則xtime(

29、 )運(yùn)算就是左移一位；(2) 如果 ，則xtime( )左移一位后，還需要減去 m(x) , 也就是異或1b。二進(jìn)制表示為00000001 00011011，十六進(jìn)制表示為 01 1b 更高次的乘法可以通過重復(fù)使用xtime（）實(shí)現(xiàn)。 xtime（） 運(yùn)算：x b(x)。 例如：5713=f e 5702=xtime(57)=ae 5704=xtime(ae)=47 5708=xtime(47)=8e 5710=xtime(8e)=07 5713=57(010210) =57ae07=fe可以利用多項(xiàng)式的擴(kuò)展歐幾里得算法求乘法逆。 AES中兩個字節(jié)相乘的含義！例：求多項(xiàng)式 模 的逆元。驗(yàn)證：如

30、何判斷一個多項(xiàng)式是既約多項(xiàng)式？ 如同判斷一個整數(shù)是不是素數(shù)一樣。 對于高次多項(xiàng)式比較困難，（多項(xiàng)式的根問題）， 抽象代數(shù)中有一些相關(guān)結(jié)論，例如，對于 多項(xiàng)式中有因子x+1當(dāng)且僅當(dāng)它有偶數(shù)個非零系數(shù)。 如同素數(shù)檢測存在一些算法或者查表， 既約多項(xiàng)式的判定也是如此。 一些小次數(shù)的既約多項(xiàng)式表如下：字節(jié)替代(ByteSubstitute)變換ByteSubstitute獨(dú)立地對每個字節(jié)進(jìn)行,是非線性的。它由以下兩個變換合成而得：0000；對于x00，xx-1（在GF(28)中）。 （F2上仿射變換） AES的描述字節(jié)代換示意圖為了提高速度，將上述ByteSubstitute變換做成替換表(S-盒)如

31、下：63 7c 77 7b f2 6b 6f c5 30 1 67 2b fe d7 ab 76ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15 4 c7 23 c3 18 96 5 9a 7 12 80 e2 eb 27 b2 75 9 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 8453 d1 0 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cfd0 ef aa fb 43 4d 33

32、 85 45 f9 2 7f 50 3c 9f a851 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2cd c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 7360 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e b dbe0 32 3a a 49 6 24 5c c2 d3 ac 62 91 95 e4 79e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 8ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b

33、 8a70 3e b5 66 48 3 f6 e 61 35 57 b9 86 c1 1d 9ee1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df8c a1 89 d bf e6 42 68 41 99 2d f b0 54 bb 16AES的描述2、系數(shù)在 的多項(xiàng)式運(yùn)算 （字運(yùn)算） 一個4字節(jié)的字可以看作 中的元素。 這時元素用多項(xiàng)式表示，就是系數(shù)在 中的小于4 次的多項(xiàng)式。 加法就是多項(xiàng)式對應(yīng)項(xiàng)的系數(shù)相加，因此也就是中元素相加，即逐位模二加。 AES中兩個 字相加的含義！4. 系數(shù)在GF(28)上的多項(xiàng)式模取M(x)=x4+1，系數(shù)在GF(28)

34、上的任意多項(xiàng)式可表示為a3x3+a2x2+a1x+a0，ai GF(28)系數(shù)對應(yīng)4個字節(jié)構(gòu)成的向量。加法定義如下對應(yīng)系數(shù)相加；4字節(jié)向量的逐比特異或。乘法是多項(xiàng)式相乘后，模一個4次多項(xiàng)式，不是既約的：（系數(shù)為單位元“01”） AES中兩個 字相乘的含義！多項(xiàng)式除法！ AES乘以一個固定 多項(xiàng)式a(x)= 為了解密， a(x)應(yīng)當(dāng)有逆設(shè)a(x)= a3x3+a2x2+a1x+a0，b(x)= b3x3+b2x2+b1x+b0，c(x)= a(x) b(x)=c3x3+c2x2+c1x+c0。由于xj mod (x4+1)= x j mod 4，所以c0=a0b0a3b1a2b2a1b3；c1=

35、 a1b0a0b1a3b2a2b3；c2= a2b0a1b1a0b2a3b3；c3= a3b0a2b1a1b2a0b3。注意：M(x)不是GF(28)上的不可約多項(xiàng)式，非0多項(xiàng)式乘法逆元不一定存在。在Rijndael密碼中，只限于乘一個固定的有逆元的多項(xiàng)式乘法定義列混合(MixColumn)變換如下：在此作為GF(28)上矩陣進(jìn)行乘法。行移位(ShiftRow)或列混合(MixCo-lumn)變換更新陣列，其輸出是對更新后的，按列依次取出來的4*Nb字節(jié)a0,0 a1,0a2,0a3,0 a0,Nb-1a1,Nb-1a2,Nb-1a3,Nb-1。陣列的第j列AES的描述用多項(xiàng)式x乘b(x)有：

36、（所以相當(dāng)于循環(huán)左移一位。） 小結(jié)：字節(jié)運(yùn)算：加法 ， 乘法 一個字節(jié)表示為多項(xiàng)式，每一位對應(yīng)多項(xiàng)式的系數(shù)字運(yùn)算：加法，乘法 一個字表示為多項(xiàng)式，每一位對應(yīng)多項(xiàng)式的系數(shù)行移位(ShiftRow)與列混合(MixColu-mn)變換 將4*Nb字節(jié)輸入a0,0a1,0a2,0a3,0 a0,Nb-1a1,Nb-1a2,Nb-1a3,Nb-1的每4個字節(jié)排成一列，得到以下4Nb陣列： AES的描述ShiftRow將狀態(tài)陣列的各行進(jìn)行循環(huán)移位，移位量與分組長度的關(guān)系NbC1C2C34123612381340行：不動狀態(tài)陣列的每個列a(x)與一個固定的多項(xiàng)式c(x)進(jìn)行模x4+1乘法后混淆為b(x).

37、記為c(x)是模x4+1可逆的多項(xiàng)式03x3+01x2+01x+02MixColumnb(x)= c(x)a(x)逆d(x)=0Bx3+0Dx2+09x+0E三、AES中的變換1、字節(jié)替代 ByteSub(State)3、列混合 MixColumn(State)2、行移位 ShiftRow(State)4、加密鑰 AddRoundKey(State, RoundKey)5、密鑰擴(kuò)展8、逆列混合 InvMixColumn(State)6、逆字節(jié)替代 InvByteSub(State)7、逆行移位 InvShiftRow(State)Rijndael (State, ExpandedKey)Add

38、RoundKey (State, ExpandedKey);for (i=1; i Nr; i +) Round (State, ExpandedKey+Nb* i);FinalRound (State, ExpandedKey+Nb*Nr)Round (State, RoundKey) ByteSub (State); ShiftRow (State); MixColumn (State); AddRoundKey (State, RoundKey)FinalRound (State, RoundKey) ByteSub (State); ShiftRow (State); AddRound

39、Key (State, RoundKey)行移位(ShiftRow) 變換的方法是：將陣列的第0行不動，以下第i(i=1,2,3)行左環(huán)移Ci(見下表)字節(jié)： 431832163214C3C2C1CiNbAES的描述迭代輪數(shù)+1：Nr Nr值依賴于Nb和Nk的選擇，具體情況見下表：NrNb=4Nb=6Nb=8Nk=4101214Nk=6121214Nk=8141416AES的描述密鑰擴(kuò)展. InitKey、RoundKey(i=1,2,Nr-1)、以及FinalKey一共是Nr+1個子密鑰(每個應(yīng)為4*Nb 字節(jié))。它們將由所給的4*Nk字節(jié)主密鑰經(jīng)過變換而得到，方法就是：用4*Nk字節(jié)主密鑰

40、作為下列Nk級移存器的初態(tài)，然后進(jìn)動足夠多拍，在產(chǎn)生的32比特字的序列W中順序取出。AES的描述當(dāng)Nk6時，Nk級移存器如下圖：當(dāng)進(jìn)動拍數(shù)j%Nk0 時 此處Rconstt=Xtimet-1(01)|00|00|00(t0)Rconst(j+Nk-1)/ Nk當(dāng)進(jìn)動拍數(shù)j %Nk=0 時 Nk級存儲器4個S-盒右環(huán)移1字節(jié)4 bytes 4 bytes4 bytesWAES的描述WRotWordSubWord 當(dāng)Nk6時，擴(kuò)展算法如下 KeyExpansion (byteKey4*Nk , WNb*(Nr+1) for (i =0; i Nk; i +)Wi=(Key4* i,Key4* i

41、+1,Key4* i +2,Key4* i +3 ); for (i =Nk; i 6時，擴(kuò)展算法如下： KeyExpansion (byte Key4*Nk , WNb*(Nr+1) for (i=0; i Nk; i +)Wi=(Key4* i, Key4* i +1, Key4* i +2, Key4* i +3 );for (i =Nk; i 6時，Nk級移存器如下圖：Nk級存儲器AES的描述4 bytes 4 bytes4 bytesW4個S-盒Rconst(j+Nk-1)/ Nk此處Rconstt=Xtimet-1(01)|00|00|00(t0)右環(huán)移1字節(jié)當(dāng)進(jìn)動拍數(shù)j %Nk=

42、0 時 當(dāng)進(jìn)動拍數(shù)j%Nk=4 時 W4個S-盒當(dāng)進(jìn)動拍數(shù)j%Nk1,4 時 W脫密過程.子密鑰肯定是反序來使用，但不能采用與加密過程一樣的算法。從加密過程易看出解密步驟，在此明確：行移位(ShiftRow)的逆：陣列的第0行不動，以下第i(i=1,2,3)行左環(huán)移Nb-Ci字節(jié)（即右環(huán)移Ci字節(jié)）；列混合(MixColumn)的逆：對陣列的第j列，AES的描述四、AES的特點(diǎn) 結(jié)構(gòu)簡單，適應(yīng)性強(qiáng)；加解密結(jié)構(gòu)相同，但是解密使用加密的逆模塊；AES的設(shè)計能夠抵御已有的線性分析和差分分析；采用較大的s盒，并且能進(jìn)行代數(shù)上的定義，而不像DES的S盒是“隨機(jī)”代換。 對于AES的攻擊：主要利用AES代

43、數(shù)結(jié)構(gòu)的特點(diǎn)。 積分分析：通過預(yù)測幾輪之后的積分值來猜測密鑰。 代數(shù)攻擊：用某種代數(shù)方程系統(tǒng)描述S盒。 能量攻擊：加密中間過程的電磁泄漏可能暴露密鑰信息。 4.6 分組密碼的工作模式分組密碼每次加密的明文數(shù)據(jù)量是固定的(64bit/128bit)，而實(shí)際待加密的信息是較長和不確定的，這就需要做一些處理。根據(jù)不同的應(yīng)用環(huán)境，需要對分組密碼的加密方式做一些變動，以增強(qiáng)密碼的安全性和適應(yīng)性?？墒褂梅纸M密碼以一些典型的方式構(gòu)造無碰撞的Hash函數(shù)。(Hash函數(shù)又稱為雜湊函數(shù)，一般用于對消息進(jìn)行摘要，這摘要可用于保證消息的完整性和數(shù)字簽名。)下面以AES為例來介紹分組密碼的實(shí)用情形和一些應(yīng)用模式。分組

44、密碼的應(yīng)用模式下面以AES為例來介紹分組密碼的實(shí)用情形和一些應(yīng)用模式。分組處理.給定加密消息(明文)的長度是隨機(jī)的，當(dāng)按128bit分組時，最后一組消息的長度可能不足16byte。這時，用一串0或隨機(jī)選取的bit來填充，不過通常要留出最后一字節(jié)說明所填充的字節(jié)數(shù)。若消息分組最后所余部分只有k bit (ki+1)組明文Mj將不在受此錯誤影響，系統(tǒng)會自動恢復(fù)正常。CBC模式的錯誤擴(kuò)散不大(至多不過是關(guān)系到兩個明文組的129比特)，但對于傳輸中的同步差錯(增加或丟失若干比特)很敏感。因而要求系統(tǒng)具有良好的幀同步；為防止這類錯誤釀成惡果，系統(tǒng)還應(yīng)采取糾錯技術(shù)。CBC評價優(yōu)點(diǎn)：1.不容易主動攻擊,安全

45、性好于ECB,適合傳輸長度長的報文,是SSL、IPSec的標(biāo)準(zhǔn)。缺點(diǎn)：1.不利于并行計算；4.誤差傳遞；3.需要初始化向量IV分組密碼的應(yīng)用模式序列模式在前述分組碼的一些工作模式中，數(shù)據(jù)加密皆按128bit一組進(jìn)行，這對于一些網(wǎng)絡(luò)上需按字節(jié)來處理數(shù)據(jù)的應(yīng)用就很不方便。以下介紹兩種按序列模式使用的分組密碼，其每次加密處理的數(shù)據(jù)量可以是任意的n(1 n128)bit。3、密文反饋（CFB）模式4、輸出反饋(OFBOutput feedback)分組密碼的應(yīng)用模式3、密文反饋(CFBCipher Feedback)模式：同OFB模式類似，仍用分組密碼算法(AES)構(gòu)作密鑰序列生成器KG，但改其輸出反

46、饋為密文反饋，所得即CFB模式。如下圖所示：128級移位寄存器DES取最左邊n bitK128bit128bitKi(n bit)Mi(n bit)Ci(n bit)密文反饋3 CFB模式： 分組密碼的應(yīng)用模式在前述CFB模式中，同樣必須預(yù)置級移位寄存器的初始128bit數(shù)據(jù)(稱為初始向量IV)，它可在信道上明傳給接收方。CFB模式也特別適合于用戶數(shù)據(jù)格式的需要。另外，由于密文反饋的作用，象CBC模式一樣，該模式能隱蔽明文的數(shù)據(jù)特征以及檢測出對密文的篡改；卻也存在有限的(其實(shí)是128/n+1組)錯誤擴(kuò)散：當(dāng)傳輸?shù)拿芪慕MCi出現(xiàn)1bit錯誤時，解密的明文組Mi也分組密碼的應(yīng)用模式有1bit錯誤，

47、而且隨后解密出來的128/n組明文Mi+1,Mi+2,Mi+128/n全錯，直至此后原Ci的1bit錯誤剛好移出64級移位寄存器，系統(tǒng)可自動恢復(fù)正常。CFB模式給出的是典型的自同步序列密碼：只要接收方連續(xù)收到128/n組正確的密文，收發(fā)雙方的128級移位寄存器存儲的數(shù)據(jù)就完全一樣，從而雙方可重新建立起同步。對CFB評價優(yōu)點(diǎn)：1.隱藏了明文模式;4.分組密碼轉(zhuǎn)化為流模式;3.可以及時加密傳送小于分組的數(shù)據(jù);缺點(diǎn):1.不利于并行計算;4.誤差傳送：一個明文單元損壞影響多個單元;3.唯一的IV;4 OFB模式： 優(yōu)點(diǎn):4、輸出反饋(OFBOutput feedback)模式：該模式的工作原理如下頁圖

48、示：在上述OFB模式中，必須預(yù)置128級移位寄存器的初始128比特數(shù)據(jù)（稱為初始向量IV），它可在信道上明傳給接收方。128級移位寄存器AES取最左邊n bitK128bit128bitKi(n bit)Mi(n bit)Ci(n bit)輸出反饋分組密碼的應(yīng)用模式OFB模式特別適合于用戶數(shù)據(jù)格式的需要（在密碼體制的設(shè)計中，應(yīng)盡量避免更改現(xiàn)有系統(tǒng)的數(shù)據(jù)格式和一些規(guī)定，這是一個重要的設(shè)計原則)。此外，OFB模式不具有自同步能力，要求系統(tǒng)要保持嚴(yán)格的同步，否則難以解密。OFB模式實(shí)際上是用分組密碼算法(AES)構(gòu)造一個密鑰序列生成器KG，本質(zhì)上已轉(zhuǎn)化為序列密碼的方式。因此，分組密碼的應(yīng)用模式OFB模式具有序列