密碼學(xué)教程 課件 3-分組密碼

第三章分組密碼

3.1概述

3.2DES（數(shù)據(jù)加密標(biāo)準(zhǔn)）3.3AES（高級(jí)加密標(biāo)準(zhǔn)）

3.4SM4（我國(guó)商用分組算法）

3.5分組密碼的工作模式3.1概述為了克服統(tǒng)計(jì)分析，可以采用擴(kuò)散和混淆兩種基本方式。擴(kuò)散：就是使明文的每一位影響密文中的許多位，這樣可以隱蔽明文的統(tǒng)計(jì)特性。

混淆：密文的每一位受密鑰盡可能多位的影響。

使密文和密鑰關(guān)系復(fù)雜，從而統(tǒng)計(jì)分析更加困難。

換位變換可以實(shí)現(xiàn)有效的擴(kuò)散，打亂明文字母之間、

字母組合之間的統(tǒng)計(jì)關(guān)系。

代替變換(非線性的)可以達(dá)到比較好的混淆效果。

不論是數(shù)、還是其它信息，經(jīng)過編碼后都變?yōu)槎M(jìn)制串，可稱之為數(shù)據(jù)。如果對(duì)其加密，數(shù)據(jù)就是明文：11001011’10110010’

01101010’11101011’……..分組密碼的加密是每次對(duì)一段明文進(jìn)行加密，類似古典密碼的多表密碼：

……..每個(gè)明文段叫作一個(gè)明文分組，對(duì)應(yīng)密文叫作密文分組。明文分組密鑰密文分組En明文分組密鑰密文分組De01…1101…P盒－permutationbox;S盒－substitutionbox。SP結(jié)構(gòu)（替代－置換網(wǎng)絡(luò)）：每輪處理整個(gè)分組明文，加解密算法不同。分組密碼的整體結(jié)構(gòu)有兩種基本類型：（迭代類型）Feistel結(jié)構(gòu)：每輪處理一半明文，加解密算法相同。DES是Feistel結(jié)構(gòu)的代表；AES是SP結(jié)構(gòu)的一個(gè)代表。乘積密碼系統(tǒng)是S盒與P盒變換的組合，兩者結(jié)合得到的密碼系統(tǒng)比單獨(dú)一種更強(qiáng)。這一方式成為數(shù)據(jù)加密標(biāo)準(zhǔn)DataEncryptionStandard(DES)的基礎(chǔ)。

Feistel結(jié)構(gòu)SP結(jié)構(gòu)En

分組密碼：

多次迭代一個(gè)輪函數(shù)，同時(shí)處理一組明文段。

密鑰長(zhǎng)度固定，且對(duì)不同明文段保持不變。序列密碼：

產(chǎn)生（偽）隨機(jī)的密鑰流，每次處理一個(gè)明文字母。

加密過程簡(jiǎn)單，但需要密文與密鑰同步。分組密碼適用性更廣，易于標(biāo)準(zhǔn)化；序列密碼主要用于保密性，速度更快，可實(shí)時(shí)通信。

3.2DES（數(shù)據(jù)加密標(biāo)準(zhǔn)）DES（DataEncryptionStandard）從1977年提出（原計(jì)劃用10年）到1997年被認(rèn)為不安全，經(jīng)歷了20多年，是分組密碼設(shè)計(jì)的一個(gè)典范。

一、DES的加解密過程

明文分組：64bit(即64位二進(jìn)制串)密文分組：64bit密鑰：64bit，其中8bit為校驗(yàn)位，實(shí)際56bit輪數(shù)：

16輪（圈）加密函數(shù)：8個(gè)6-4S盒；P置換。整體結(jié)構(gòu)：FeistelLRLRLRIP-1IP16輪64bit64bit算法：整體結(jié)構(gòu)步(輪)函數(shù)密鑰擴(kuò)展密鑰擴(kuò)展ffDES整體結(jié)構(gòu)：32Bit！32Bit！64Bit！48Bit！一共16輪！64bit！注意：最后一輪不交換！DES的加密函數(shù)f：8個(gè)不同的6-4S盒！48bit！48bit！32bit！4×8=32bit查表！擴(kuò)展并置換查表：輸入6比特的首尾2位確定行，中間4位確定列，交叉處為輸出。密鑰擴(kuò)展：64bit輸入密鑰！56bit－去掉8、16等8個(gè)監(jiān)督位56bit48bit28bit循環(huán)移位，1、2、9、16輪左移1位，其它輪左移2位!Feistel結(jié)構(gòu)：記住這個(gè)特點(diǎn)即可??！加密解密密鑰反序L在右側(cè)加兩次，消掉！明文

M(8bit)IPT0(4bit)T1(4bit)f(T1,K1)T1(4bit)T2(4bit)IP-1密文組C(8bit)密鑰K(8bit)P1C0(4bit)D0(4bit)4-置換Qf(T2,K2)T3(4bit)T2(4bit)4-置換RC1(4bit)D1(4bit)4-置換Q-14-置換R-1P2K1(6bit)C2(4bit)D2(4bit)P2K2(6bit)小DES（1）如果密鑰擴(kuò)展過程中，

P1=(41768253)，

P2=(571842)，Q=(3142)，R=(4312)，

輸入主密鑰為K=11001010，

求經(jīng)密鑰擴(kuò)展后的K1和K2。（2）如果IP=(86421357)，

f函數(shù)如左圖所示，

兩個(gè)S盒見下頁(yè)。S1P=(3,1,2,4)f(T,K)(4bit)K(6bit)E=(4,1,2,2,3,4)T(4bit)T’(6bit)Z2(3bit)Z1(3bit)S2U2(2bit)U1(2bit)(第1bit決定行,第2、3bit決定列)解：（1）經(jīng)置換，C1D1=10010101，經(jīng)P2得K1=001110C2D2=01100110，經(jīng)P2得K2=010001。S101230301211320S201230213013021若已知明文01011100，在密鑰K下得到的密文是什么？

并通過解密得到原明文驗(yàn)證加密的正確性。（2）T1=0010，T1’=000010，Z1=001，Z2=100U1=00，U2=11，f(T1,K1)=1001，T2=1110；T2’=011110，Z1=001，Z2=111，U1=00，U2=01，f(T2,K2)=0001，T3=0011，T4=1110，1111100001011100(86421357)01110010F

0010

1110

(54637281)

11111000

11001010(41768253)01100110(3142)F

0011

1110

(4312)10010101(2413)(3421)P200111001100110P2

010001

二、DES的特點(diǎn)

除密鑰順序之外，加密和解密步驟完全相同；

主要的批評(píng)：密鑰太短，迭代次數(shù)可能太少，

S盒可能存在不安全隱患。

差分分析：通過分析明文對(duì)的差值（異或）對(duì)密文對(duì)的差值的影響來恢復(fù)某些密鑰比特。

窮舉攻擊：現(xiàn)在人們利用網(wǎng)絡(luò)計(jì)算可以在20多小時(shí)破譯56位的DES。DES已變得不安全了。

線性分析：一種已知明文攻擊，它試圖建立起明文、密文和密鑰之間的一組近似線性方程。

三、多重DES

為了提高安全性，防止窮舉攻擊，DES還有多重形式。

雙重DES：

但存在中間相遇攻擊：（已知一對(duì)明密文）窮舉k2！窮舉k1！

三重DES：

中間一層用解密形式是為了可以利用三重DES對(duì)單重DES加密的密文進(jìn)行解密(

k1=k2或k2=k3)。DESk1mDESk2－1DESk3cDESk1－1DESk2DESk3－13.3AES（高級(jí)加密標(biāo)準(zhǔn)）

1997年美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所（NIST）征集AES(AdvancedEncryptionStandard)。

要求：（1）比三重DES快且至少與它一樣安全；（2）分組長(zhǎng)度為128bit；

密鑰長(zhǎng)為128bit，192bit和256bit；（3）算法要能抵抗已知的密碼分析方法，無明顯漏洞；（4）算法實(shí)現(xiàn)要有效率，有一定的靈活性（適應(yīng)不同的環(huán)境），軟硬件兩種方法實(shí)現(xiàn)。15種算法參加第一輪評(píng)選，5種進(jìn)入第二輪：

RC6、Rijndael、Serpent、Twofish、Mars2000年獲勝者是Rijndael算法，是比利時(shí)密碼設(shè)計(jì)者所作。

一、AES的加解密過程明文分組：128bit密文分組：128bit密鑰：128、192、256bit輪數(shù)：10、12、14輪（圈）加密函數(shù)：8-8的S盒、P（行移位、列混合）密鑰生成：擴(kuò)展、遞歸總體結(jié)構(gòu)：SP結(jié)構(gòu)

10-14輪128bit128bit16個(gè)字節(jié)SP結(jié)構(gòu)

AES是面向字節(jié)的算法：字節(jié)為最小單位進(jìn)行處理。輸入明文分組：128bit=16×8bit＝16個(gè)字節(jié)，排成4×4的字節(jié)數(shù)組，稱為狀態(tài)矩陣（StateMatrix）

按列排！輪函數(shù)就是對(duì)這個(gè)數(shù)組進(jìn)行變換。乘以常數(shù)字（4字節(jié)）AES解密過程：加密過程的逆過程，需要相應(yīng)的逆變換。

AddRoundKey：將每一輪的密鑰與狀態(tài)矩陣直接異或；

InvSubBytes：逆字節(jié)替代變換，需要8-8的逆s盒。InvShiftRows：逆行移位變換；InvMixColumns：逆列混合變換；

AES密鑰擴(kuò)展過程：

產(chǎn)生各輪子密鑰，主密鑰直接作為開始的輪密鑰，

后面的由前面輪密鑰字，經(jīng)S盒等運(yùn)算遞歸產(chǎn)生。

4個(gè)字節(jié)為1個(gè)字

AES中的列混合：AES是面向字節(jié)的算法——字節(jié)的運(yùn)算！以下介紹字節(jié)替代和列混合這兩個(gè)部件的實(shí)現(xiàn)原理二、AES中的運(yùn)算

0000——0x00110——0x61100——0xC0001——0x10111——0x71101——0xD0010——0x21000——0x81110——0xE0011——0x31001——0x91111——0xF0100——0x41010——0xA0101——0x51011——0xB11000001——C1AES是面向字節(jié)的算法，最小單位是字節(jié)(Byte)。一個(gè)字節(jié)可用二位十六進(jìn)制數(shù)表示。二進(jìn)制串常表示為十六進(jìn)制任意分組表示為128bit的二進(jìn)制串，分為12個(gè)字節(jié)，每個(gè)字節(jié)表示為2位十六進(jìn)制（省略0x），例如：

AES對(duì)此字節(jié)矩陣的處理即是對(duì)字節(jié)的運(yùn)算，需要將所有字節(jié)組成的集合變?yōu)榇鷶?shù)結(jié)構(gòu)（可以加減乘除）。

仿照對(duì)“數(shù)”的處理，將這些數(shù)據(jù)視為“數(shù)”00000000=0x0000000001=0x01-----00001111=0x0F-----11111111=0xFF加、減、乘、除——域！運(yùn)算結(jié)果還在此域中S盒——字節(jié)除法列混合——字節(jié)乘法1、中的運(yùn)算（字節(jié)運(yùn)算）

中一共有個(gè)元素，可以有多種方式表示，AES中用多項(xiàng)式表示（以便能進(jìn)行乘/除運(yùn)算）。

一個(gè)字節(jié)8bit：

對(duì)應(yīng)多項(xiàng)式：

一個(gè)字節(jié)8比特，可以看作中的一個(gè)元素。例題：0x57即01010111，對(duì)應(yīng)多項(xiàng)式：

對(duì)于域的加法就是多項(xiàng)式對(duì)應(yīng)項(xiàng)相加，系數(shù)模二加：

‘57’

‘83’

01010111

10000011＝11010100‘D4’AES中兩個(gè)字節(jié)相加的含義！對(duì)于域的減法，就是加上減法逆（就是本身）。對(duì)于域的乘法，要模一個(gè)8次既約多項(xiàng)式m(x)，AES中選取的

例題：‘57’·‘83’

對(duì)應(yīng)：

二進(jìn)制表示：01010111?10000011＝11000001十六進(jìn)制表示：57?83＝c1AES中兩個(gè)字節(jié)相乘的含義！

分配律！

復(fù)雜運(yùn)算化簡(jiǎn)為簡(jiǎn)單運(yùn)算的迭代都是乘x

乘一個(gè)x，相當(dāng)于字節(jié)中的1左移1位

06=00000110=00000100+00000010=02+04

將一個(gè)字節(jié)表示為只有一個(gè)1的字節(jié)之和，而只有一個(gè)1的字節(jié)都是不斷乘x得到的。

xtime()運(yùn)算：x

b(x)

更高次的乘法可以通過重復(fù)使用xtime（）實(shí)現(xiàn)。

(1)如果，則xtime()運(yùn)算就是左移一位，后補(bǔ)零；如果，則xtime()左移一位，后補(bǔ)零，再異或1b。

xtime()算法：例題：57

13=01010111

00010011

“13”=

00010011

=

00000001

+00000010

+00010000因此13=“01”+

“02”+

“10”字節(jié)13是16進(jìn)制，不是十進(jìn)制，十進(jìn)制數(shù)對(duì)應(yīng)19。

57

02=xtime(57)=xtime(01010111)=ae57

04=xtime(ae)=xtime(10101110)=4757

08=xtime(47)=xtime(01000111)=8e57

10=xtime(8e)=xtime(10001110)=0757

13=57

(01⊕02⊕10)

=57⊕ae⊕07=fe對(duì)于域的除法，也就乘以除數(shù)的乘法逆。一般地，可以利用多項(xiàng)式的擴(kuò)展歐幾里得算法求乘法逆。

例題：求多項(xiàng)式模的逆元。驗(yàn)證：表示為輸入的線性組合兩邊模M(x),可得逆元。因?yàn)椋夯蛘卟捎靡韵碌惴ǎ好看问Ｓ嗫杀硎緸閚與u的代數(shù)和。

注意順序AES中規(guī)定：

53的字節(jié)代替。二進(jìn)制為01010011，表示的域元素為例題：表示為二進(jìn)制為11001010。

逆元為，

所以53代替為11101101，即“ed”。

注意順序！2、系數(shù)在的多項(xiàng)式運(yùn)算（字運(yùn)算）

這時(shí)元素用多項(xiàng)式表示，就是系數(shù)在中的小于4次的多項(xiàng)式。

加法就是多項(xiàng)式對(duì)應(yīng)項(xiàng)的系數(shù)相加，因此也就是中元素相加，即逐位模二加。

列混合是字的運(yùn)算

AES中兩個(gè)字相加的含義！乘法是多項(xiàng)式相乘后，模一個(gè)4次多項(xiàng)式，

AES中兩個(gè)字相乘的含義！不是既約的：(01+01=00)

都成為四項(xiàng)之和為了進(jìn)行解密，a(x)應(yīng)當(dāng)有逆。AES中的列混合：MDS碼，最佳擴(kuò)散性；重量輕，計(jì)算簡(jiǎn)單

例題：

AES列混合的性質(zhì)：

混合前后兩列的四個(gè)字節(jié)之和保持不變。

三、AES的特點(diǎn)

結(jié)構(gòu)簡(jiǎn)單，適應(yīng)性強(qiáng)；加解密結(jié)構(gòu)相同，但是解密使用加密的逆模塊；逆S盒逆S盒對(duì)于AES的攻擊：主要利用AES代數(shù)結(jié)構(gòu)的特點(diǎn)。

積分分析：通過預(yù)測(cè)幾輪之后的積分值來猜測(cè)密鑰。

代數(shù)攻擊：用某種代數(shù)方程系統(tǒng)描述S盒。

側(cè)信道攻擊：加密中間過程電磁泄漏可能暴露密鑰信息。

（sidechannelattack）（差分能量攻擊）

AES的設(shè)計(jì)能夠抵御已有的線性分析和差分分析；采用較大的S盒，并且能進(jìn)行代數(shù)上的定義，而不像DES的S盒是“隨機(jī)”代替（不易判斷安全性）。寬軌跡策略Feistel結(jié)構(gòu)SP結(jié)構(gòu)En

3.4SM4（我國(guó)商用密碼算法）SM4是2006年我國(guó)公布的商用分組密碼算法。特點(diǎn)：分組長(zhǎng)度和密鑰長(zhǎng)度都是128比特；加密算法和密鑰擴(kuò)展都是32輪非線性迭代；采用一個(gè)8*8的S盒；采用32bit的異或和移位運(yùn)算L；結(jié)構(gòu)為非對(duì)稱的Feistel；加解密算法相同，只是輪密鑰順序顛倒。Electronic-CodeBook(ECB)：電碼本模式Cipher-BlockChaining(CBC)：密碼分組鏈接模式CipherFeedBack(CFB)：密碼反饋模式OutputFeedBack(OFB)：輸出反饋模式

為了防止攻擊，分組密碼需要有一定的工作模式。CFB和OFB兩種模式：可利用分組密碼實(shí)現(xiàn)流密碼！3.5分組密碼工作模式

（另外新的還有：計(jì)數(shù)器模式、加密認(rèn)證模式等）這些模式適用于各種分組密碼，以下僅以DES為例。DESDESm1c1km2c26464kDESkcnmnDES-1DES-1c1m1kc2m26464kDES-1kmncnECB模式（electroniccodebook）相同明文產(chǎn)生相同密文！以DES為例但這種模式存在以下問題：

相同明文對(duì)應(yīng)相同密文。CBC

模式(cipherblockchaining)DESD