密碼學教程 課件 3-分組密碼

第三章分組密碼

3.1概述

3.2DES（數(shù)據(jù)加密標準）3.3AES（高級加密標準）

3.4SM4（我國商用分組算法）

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

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

使密文和密鑰關系復雜，從而統(tǒng)計分析更加困難。

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

字母組合之間的統(tǒng)計關系。

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

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

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

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

Feistel結構SP結構En

分組密碼：

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

密鑰長度固定，且對不同明文段保持不變。序列密碼：

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

加密過程簡單，但需要密文與密鑰同步。分組密碼適用性更廣，易于標準化；序列密碼主要用于保密性，速度更快，可實時通信。

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

一、DES的加解密過程

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

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

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）如果密鑰擴展過程中，

P1=(41768253)，

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

輸入主密鑰為K=11001010，

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

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

兩個S盒見下頁。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下得到的密文是什么？

并通過解密得到原明文驗證加密的正確性。（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的特點

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

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

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

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

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

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

三、多重DES

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

雙重DES：

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

三重DES：

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

k1=k2或k2=k3)。DESk1mDESk2－1DESk3cDESk1－1DESk2DESk3－13.3AES（高級加密標準）

1997年美國國家標準技術研究所（NIST）征集AES(AdvancedEncryptionStandard)。

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

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

RC6、Rijndael、Serpent、Twofish、Mars2000年獲勝者是Rijndael算法，是比利時密碼設計者所作。

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

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

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

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

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

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

AES密鑰擴展過程：

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

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

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

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

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

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

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

中一共有個元素，可以有多種方式表示，AES中用多項式表示（以便能進行乘/除運算）。

一個字節(jié)8bit：

對應多項式：

一個字節(jié)8比特，可以看作中的一個元素。例題：0x57即01010111，對應多項式：

對于域的加法就是多項式對應項相加，系數(shù)模二加：

‘57’

‘83’

01010111

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

例題：‘57’·‘83’

對應：

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

分配律！

復雜運算化簡為簡單運算的迭代都是乘x

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

06=00000110=00000100+00000010=02+04

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

xtime()運算：x

b(x)

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

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

xtime()算法：例題：57

13=01010111

00010011

“13”=

00010011

=

00000001

+00000010

+00010000因此13=“01”+

“02”+

“10”字節(jié)13是16進制，不是十進制，十進制數(shù)對應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對于域的除法，也就乘以除數(shù)的乘法逆。一般地，可以利用多項式的擴展歐幾里得算法求乘法逆。

例題：求多項式模的逆元。驗證：表示為輸入的線性組合兩邊模M(x),可得逆元。因為：或者采用以下迭代算法：每次剩余可表示為n與u的代數(shù)和。

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

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

逆元為，

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

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

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

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

列混合是字的運算

AES中兩個字相加的含義！乘法是多項式相乘后，模一個4次多項式，

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

都成為四項之和為了進行解密，a(x)應當有逆。AES中的列混合：MDS碼，最佳擴散性；重量輕，計算簡單

例題：

AES列混合的性質：

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

三、AES的特點

結構簡單，適應性強；加解密結構相同，但是解密使用加密的逆模塊；逆S盒逆S盒對于AES的攻擊：主要利用AES代數(shù)結構的特點。

積分分析：通過預測幾輪之后的積分值來猜測密鑰。

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

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

（sidechannelattack）（差分能量攻擊）

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

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

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

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

相同明文對應相同密文。CBC

模式(cipherblockchaining)DESD