《數據加密與PKI應用（微課版）》 課件 Chapter04-分組加密算法

數據加密與PKI應用第4章分組加密算法分組加密算法也叫塊兒加密算法（BlockCipher），屬于對稱密碼體制，是“替代-換位”加密法到計算機加密的延伸。分組加密算法采用二進制位運算（或字節(jié)運算）方式，運算效率相對較高，被廣泛應用于現代加密系統(tǒng)中，是現代密碼學的重要組成部分。目錄014.1分組加密算法概述024.2數據加標準DES034.3高級加密標準AES044.4分組加密工作模式明文分組與密文分組

分組加密算法將明文編碼為二進制序列后，按固定長度分為t個分組：M1,M2,...,Mt，使用密鑰對每個分組執(zhí)行相同的變換，從而生成t個密文分組：C1,C2,...,Ct。

考慮到算法的安全性，分組加密算法的分組長度不能太短，應該保證加密算法能夠抵抗密碼分析；另外，考慮到分組加密算法的實用性，分組長度不能太長，要便于運算。目前，分組加密算法分組的大小通常為64比特或128比特。

分組加密算法處理的分組大小是固定的，如果明文數據的大小不是分組大小的整數倍，那么就需要對最后一個分組進行填充，使其達到規(guī)定的大小。填充應該具有可逆性，即在解密時應該能夠識別出加密時使用的填充數據。分組加密算法的基本結構擴散性：隱蔽明文的統(tǒng)計特性。實現擴散性的常用方法是換位。模糊性：隱蔽密鑰的統(tǒng)計特性。實現擴散性的常用方法是替代。通常采用非線性變換。乘積密碼：將擴散和模糊串聯起來并重復操作，這樣的密碼體制被稱為（ProduceCipher）

20世紀40年代，香濃（Shannon）提出，好的加密算法應該具備擴散性（Diffusion）和模糊性（Confusion）。擴散性：擴散就是讓明文中的每一比特影響密文中的許多比特，或者說讓密文中的每一比特受明文中的許多比特的影響，這樣可以隱蔽明文的統(tǒng)計特性。實現擴散性的常用方法是換位。模糊性：模糊就是將密文與密鑰之間的統(tǒng)計關系變得盡可能復雜，使得對手即使獲取了關于密文的一些統(tǒng)計特性，也無法推測密鑰。使用復雜的非線性替代變換可以達到比較好的模糊效果。實現模糊性的常用方法是替代。Feistel網絡是一種迭代結構，它將明文平分為左右兩部分，L0和R0，經過r(r≥1)輪迭代完成整個操作過程。假設第i-1輪的輸出為Li-1和Ri-1，則它們作為第i輪的輸入，重復執(zhí)行相同的變換。Feistel網絡結構的典型代表是數據加密標準（DES,DataEncryptionStandard）。Feistel網絡在SP網絡中，S表示替代，又被稱為混淆層，主要起模糊作用；P表示換位，又被稱為換位層，主要起擴散作用。SP網絡也是一種乘積密碼，它由一定數量的迭代組成，其中每一次迭代都包含了替代和換位。假設第i-1輪的輸出為xi-1，它是第i輪的輸入，在經過替代和換位后，輸出第i輪的結果xi，這里的替代部分需要使用第i輪的子密鑰ki。SP網絡結構的典型代表是高級加密標準（AdvancedEncryptionStandard,AES）。SP網絡目錄014.1分組加密算法概述024.2數據加標準DES034.3高級加密標準AES044.4分組加密工作模式DES算法的整體結構明文分組：64比特；密鑰長度：64比特；密文分組：64比特DES的加密過程包含3個階段：

(1)將64比特明文數據分組送入初始換位IP()函數（InitialPermutation），用于對明文中的數據重新排列，然后將明文分成兩部分，分別為L0（前32比特）和R0（后32比特）。

(2)進行16輪迭代運算。這16輪迭代運算具有相同的結構，每輪都會應用替代技術和換位技術，且使用不同的子密鑰k

i。這些子密鑰是從原始密鑰運算而來的。第16輪運算的輸出為R16和L16。

(3)將R16和L16重新拼接起來，然后送入逆初始換位IP-1()函數，最后的輸出就是64比特的密文。子密鑰生成

DES算法需要進行16輪迭代運算，每輪都需要一個48比特的子密鑰。

子密鑰是根據用戶提供的64比特初始密鑰產生的。子密鑰生成

將64比特的初始密鑰送入壓縮型初始密鑰換位表PC-1，去除奇偶校驗位，對密鑰重新排列并分為兩部分，C0（前28比特）和D0（后28比特）。子密鑰生成

將64比特的初始密鑰送入壓縮型初始密鑰換位表PC-1，去除奇偶校驗位，對密鑰重新排列并分為兩部分，C0（前28比特）和D0（后28比特）。子密鑰生成

在計算第i輪子密鑰時，將Ci-1和Di-1分別循環(huán)左移，移動位數取決于輪數i。在第i=1,2,9,16輪中，C、D兩部分分別循環(huán)左移1位，其余輪中分別循環(huán)左移2位。4×1+12×2=28子密鑰生成

將經過移位后的Ci和Di送入一個壓縮型換位表PC-2，將子密鑰壓縮為48比特（去除第9、18、22、25、35、38、43、54位）。子密鑰生成

將經過移位后的Ci和Di送入一個壓縮型換位表PC-2，將子密鑰壓縮為48比特（去除第9、18、22、25、35、38、43、54位）。初始換位與逆初始換位

逆初始換位IP-1()是初始換位IP()的逆過程。逆初始換位針對16輪迭代的結果進行運算，即執(zhí)行IP-1(R16||L16)?？梢钥闯?，通過逆初始換位，原明文分組的比特位被恢復原位。IP-1()IP()初始換位與逆初始換位f(Ri-1,ki)迭代函數

16輪迭代運算具有相同的結構。初始換位后的明文被分為左右兩部分進行處理，每輪迭代的輸入是上一輪的輸出。以第i輪運算為例：Li

=

Ri-1Ri

=

Li-1⊕f(Ri-1,ki)f(Ri-1,ki)迭代運算

擴展換位表如表4-8所示，它將32比特輸入（Ri-1）擴展為48比特。f(Ri-1,ki)迭代運算

子密鑰異或是指將經過擴展換位得到的48比特輸出與子密鑰

ki

進行異或運算。f(Ri-1,ki)迭代運算

S盒替代是將上一步輸出的48比特作為輸入，經過變換得到32比特輸出。S盒替代將48比特分成8個6比特的分組，分別輸入8個不同的S盒。假設S盒的6位輸入為x5x4x3x2x1x0，將x5x0轉換成十進制數0~3中的一個數，它確定表中的行號；將x4x3x2x1轉換成十進制數0~15中的一個數，它確定表中的列號。f(Ri-1,ki)迭代運算S盒替代是將上一步輸出的48比特作為輸入，經過變換得到32比特輸出。S盒替代將48比特分成8個6比特的分組，分別輸入8個不同的S盒。假設S盒的6位輸入為x5x4x3x2x1x0，將x5x0轉換成十進制數0~3中的一個數，它確定表中的行號；將x4x3x2x1轉換成十進制數0~15中的一個數，它確定表中的列號。f(Ri-1,ki)迭代運算P盒換位是將S盒替代的輸出結果按照固定的換位盒（P盒）進行變換。該換位將每位映射到輸出位，任何一位不能被映射兩次，也不能被省略。f()f(Ri-1,ki)

S盒替代是DES算法的核心，是一種非線性運算：

如果沒有非線性運算，則破譯者就能夠使用一個線性等式組來表示DES的輸入和輸出，其中密鑰位是未知的，這樣的算法很容易被破譯。迭代運算DES的密文分組C可以表示為：C=IP-1(R16||L16)，將其代入加密算法，首先進行初始換位IP：L0d||R0d=IP(C)

=IP(IP-1(R16||L16))

=R16||L16即L0d=R16，R0d=L16，也就是說解密第1輪的輸入是加密第16輪的輸出。DES算法解密過程接下來分析解密的第1輪操作：L1d=R0d

=L16

=R15

R1d=L0d

⊕f(R0d,k16)

=R16

⊕f(L16,k16)

=L15

⊕f(R15,k16)

⊕f(L16,k16)

=L15

⊕f(L15,k16)⊕f(R15,k16)

=L15

這說明，解密的第1輪輸出與加密的第16輪輸入相等。DES算法解密過程接下來的15輪迭代也執(zhí)行相同的操作：Lid=R16-i

Rid=L16-i

其中，i=1,2,...,16。DES算法解密過程解密的第16輪為：L16d=R0R16d=L0DES算法解密過程經過逆初始換位，可以恢復出明文M：IP-1(R16d||L16d)

=IP-1(L0||R0)

=IP-1(IP(M))

=MDES算法解密過程因為：C16=C0，D16=D0，所以：k16

=PC-2(C16,D16)=PC-2(C0,D0)=PC-2(PC-1(k))

=k1d解密子密鑰生成過程

計算k15時，可以通過C16和D16循環(huán)右移1位，再經過壓縮型換位PC-2得到，恰好等于k2d

。

另外，計算k1（k16d）、k8（k9d）、k15（k2d），需要循環(huán)右移1位后，再經過壓縮型換位換位PC-2得到子密鑰

其他子密鑰則需要循環(huán)右移兩位，再經過壓縮型換位換位PC-2得到子密鑰。算法特殊性(1)互補性。如果C=DESk(M)，那么當明文和密鑰取補后，密文也會取補，即

。這種形式，使得DES在選擇明文攻擊下工作量減半。(2)弱密鑰。DES在每輪操作中都會使用一個子密鑰。如果給定初始密鑰k，使得各輪子密鑰都相等，則稱k為弱密鑰。通過弱密鑰，加密明文兩次，則得到的仍然是明文，即：M=DESk(DESk(M))。DES的弱密鑰包括：0101010101010101H、1F1F1F1F0E0E0E0EH、E0E0E0E0F1F1F1F1H、FEFEFEFEFEFEFEFEH。算法特殊性(3)半弱密鑰。如果兩個不同的密鑰k和k'使得M=DESk(DESk'(M))，則k和k'為半弱密鑰，即k'能夠解密由密鑰k加密所得的密文。半弱密鑰只交替地生成兩種子密鑰，DES有6對兒半弱密鑰：窮舉攻擊與密碼分析窮舉攻擊：DES的密鑰太短，有效密鑰只有56比特，密鑰空間僅為256≈1017，1998年7月，電子前沿基金會（ElectronicFrontierFoundation,EFF）使用一臺造價25萬美元的密鑰搜索機器，在56小時內就成功破譯了DES。1999年1月，電子前沿基金會用22小時15分鐘就宣告破譯了一個DES的密鑰。密碼分析法：除了窮舉攻擊以外，還可以通過差分密碼分析（DifferentialCryptanalysis）、線性密碼分析（LinearCryptanalysis）、相關密鑰密碼分析（Related-KeyCryptanalysis）等方法來攻擊DES。差分分析通過分析明文對兒的差值（通過異或運算來定義DES算法的差分）對密文對兒的差值的影響來恢復某些密鑰位。線性密碼分析通過線性近似值來描述DES操作結構，試圖發(fā)現這些結構的一些弱點。相關密鑰密碼分析類似于差分密碼分析，但它考查不同密鑰間的差分。3DES雙重DES算法不能抵抗中途相遇攻擊（Meet-in-the-middleAttack）。在眾多的多重DES算法中，由Tuchman提出的三重DES算法是一種被廣泛接受的改進方法，已經被用于密鑰管理標準ANSX9.17和ISO8732中。通過三重DES，使用兩個密鑰，可以將有效密鑰長度增加到112比特，可以有效抵御窮舉攻擊。目錄014.1分組加密算法概述024.2數據加標準DES034.3高級加密標準AES044.4分組加密工作模式AES算法的整體結構明文分組：128比特；密鑰長度：128/192/256比特；密文分組：128比特AES加密使用了4個基本變換：字節(jié)代替（SubBytes）變換、行移位（ShiftRows）變換、列混合（MixColumns）變換、輪密鑰加（AddRoundKey）變換。

AES的解密使用了這4個變換的逆操作，分別為逆字節(jié)代替（InvSubBytes）變換、逆行移位（InvShiftRows）變換、逆列混合（InvMixColumns）變換和輪密鑰加變換（該變換自身就是可逆的變化）。AES就是利用上述4個基本變換經過N輪迭代而完成的。當密鑰長度為128比特時，輪數N=10；當密鑰長度為192比特時，輪數N=12；當密鑰長度為256比特時，輪數N=14。AES算法的整體結構加密過程：(1)給定一個明文分組M，將其放入狀態(tài)矩陣。輸入擴展密鑰w0、w1、w2和w3，對狀態(tài)矩陣執(zhí)行輪密鑰加變換。(2)對狀態(tài)執(zhí)行第1輪到第N-1輪迭代變換，每輪都包括了字節(jié)代替、行移位、列混合、輪密鑰加四種變換。每輪的輪密鑰都會使用一個擴展密鑰w4N、w4N+1、w4N+2和w4N+3。(3)對狀態(tài)執(zhí)行最后一輪變換，只執(zhí)行字節(jié)代替、行移位和輪密鑰加三個變換，輸出密文。輪密鑰加也會使用擴展密鑰w4N、w4N+1、w4N+2和w4N+3。AES算法的整體結構解密過程：(1)給定一個密文C，將其放入狀態(tài)矩陣。輸入擴展密鑰w4N、w4N+1、w4N+2和w4N+3，對狀態(tài)矩陣執(zhí)行輪密鑰加變換。(2)對狀態(tài)執(zhí)行第1輪到第N-1輪迭代變換。每輪都包括了逆行移位、逆字節(jié)代替、輪密鑰加、逆列混合四種變換。每輪的密鑰加也會使用一個擴展密鑰w4N、w4N+1、w4N+2和w4N+3。(3)對狀態(tài)執(zhí)行最后一輪變換，只執(zhí)行逆行移位、逆字節(jié)代替、輪密鑰加三種變換，輸出明文。輪密鑰加也會使用擴展密鑰w4N、w4N+1、w4N+2和w4N+3。狀態(tài)矩陣AES算法最基本的運算單位是字節(jié)（8比特）。1.設明文分組：

首先將其劃分為16個字節(jié)：

其中：

然后將a0~a15放入一個被稱為狀態(tài)（State）的4×4矩陣中，AES的加密和解密都是在這種狀態(tài)中進行的。2.密鑰也按照上述方法進行排列，其行數為4行，列數為4列（128比特的密鑰）、6列（192比特的密鑰）或8列（256比特的密鑰）。狀態(tài)矩陣

從數學角度，可以將每個字節(jié)看作有限域上的一個元素，分別對應一個次數不超過7的多項式：

還可以表示為一個兩位的十六進制數。例如，01101011B可以表示為：

6BH輪密鑰加

輪密鑰加變換，由狀態(tài)矩陣與擴展密鑰矩陣的對應字節(jié)逐比特做異或運算。由于輪密鑰加使用異或運算，所以其逆變換的運算方法相同。

舉例：給定狀態(tài)矩陣和擴展密鑰矩陣，計算輪密鑰加變換的結果。字節(jié)代替與逆字節(jié)代替

字節(jié)代替是一個非線性變換，對狀態(tài)矩陣中的每一個字節(jié)a進行運算

b=M·a-1+v，得到字節(jié)b（如果a=0，則映射到自身，即b=0）。

v是固定向量，值為63H；M是可逆的固定矩陣；a-1是a模一個8次不可約多項式的乘法逆元，在AES算法中，這個8次不可約多項式為m(x)=x8+x4+x3+x+1。v=字節(jié)代替與逆字節(jié)代替

逆字節(jié)代替變換是字節(jié)代替變換的逆變換。首先對字節(jié)進行仿射變換的逆變換，然后對所得結果求在GF（28）上的乘法逆元。也可以將該變換制作成表格進行查詢。列混合與逆列混合

列混合變換是一個線性變換，它混淆了狀態(tài)矩陣的每一列。由于每個輸入字節(jié)都影響了四個輸出字節(jié)，因此列混合起到了擴散的作用。逆列混合變換是列混合變換的逆，也可以寫成矩陣乘法形式。列混合與逆列混合

【例4-4】狀態(tài)中的1列為E6H、1BH、50H、18H，計算列混和運算后的結果。d0=02H·E6H+03H·1BH+01H·50H+01H·18H=B2H

02H·E6H

=

x·(x7+x6+x5+x2+x)=x7+x6+x4+x2+x+1

03H·1HB

=

x5+x3+x2+1

01H·50H

=

x6+x4

01H·18H

=

x4+x3，所以d0=x7+x5+x4+x=B2H

同理d1=38Hd2=75Hd3=4AH密鑰擴展

密鑰擴展算法將原初始密鑰作為輸入，輸出AES的擴展密鑰。

對于長度為128比特的密鑰，它對應的輪數N=10，需要11個擴展密鑰；對于長度為192比特的密鑰，它對應的輪數N=12，需要13個擴展密鑰；對于長度為256比特的密鑰，它對應的輪數N=14，需要15個擴展密鑰。獲取第1個密鑰擴展

給定一個初始密鑰k（以128比特密鑰為例），將其放入狀態(tài)矩陣，可以直接得到第1個擴展密鑰中的4個子密鑰w0、w1、w2、w3。2~10之子密鑰1(1)RotBytes(w4N-1)為字節(jié)旋轉，將w4N-1的四個字節(jié)循環(huán)左移一個字節(jié)。(2)SubBytes()為字節(jié)代替，與AES加密算法中的字節(jié)代替相同。(3)RCN/1為輪常數。其中，2~10之子密鑰2~4

第1個到第11個擴展密鑰，每一個擴展密鑰的第2~4個子密鑰可以通過公式4-10計算得到。AES的安全性分析

在AES算法中，每一輪加密常數的不同可以消除可能產生的輪密鑰的對稱性。輪密鑰生成算法的非線性特性消除了產生相同輪密鑰的可能性。加密/解密過程中使用不同的變換可以避免出現類似DES算法中弱密鑰和半若密鑰的可能。不可能差分（ImpossibleDifferential）攻擊法已經成功破解了6輪的AES-128；平方（Square）攻擊法已經成功破解了7輪的AES-128和AES-192；沖突（Collision）攻擊法也已經成功破解了7輪的AES-128和AES-192。

所有這些攻擊方法對于全部10輪的AES-128進行破解都失敗了，但是這表明AES算法可能存在有待發(fā)現的弱點。

如果將AES用于智能卡等硬件裝置，通過觀察硬件的性能特征可以發(fā)現一些加密操作的信息，這種攻擊方法叫做旁路攻擊（Side-ChannelAttack）。

例如，當處理密鑰為“1”的比特位時，需要消耗更多的能量，通過監(jiān)控能量的消耗，可以知道密鑰的每個位；還有一種攻擊是監(jiān)控完成一個算法所消耗的時間的微秒數，所消耗時間數也可以反映部分密鑰位。目錄014.1分組加密算法概述024.2數據加標準DES034.3高級加密標準AES044.4分組加密工作模式電碼本模式加密與解密過程：c

i=Ek(m

i),1≤i≤tm

i=Dk(c

i),1≤i≤t

電碼本模式簡稱為ECB（ElectronicCodeBook）。

在這種模式下，將需要加密的消息按照加密算法的分組大小分為數個分組，并對每個分組進行獨立加密形成密文分組，然后將所有密文分組連接起來得到密文。每個明文分組或密文分組的錯誤只影響其對應的密文分組或明文分組，而不會傳遞給其它密文分組或明文分組。采用EBC模式時，不同的明文分組或密文分組的加密或解密可以并行處理，在硬件或軟件運算時速度很快。

ECB模式的缺點是不能隱藏明文的模式，因此ECB模式無法抵抗攻擊者的主動攻擊，安全性較差。ECB模式可以用于處理短消息，例如加密密鑰時可以使用ECB模式。密碼分組鏈模式加密：c

i=Ek(m

i

⊕c

i-1),1≤i≤t，其中c0=IV；解密：m

i=Dk(c

i)⊕c

i-1,1≤i≤t，其中c0=IV

密碼分組鏈接模式簡稱CBC（Cipher-BlockChaining）。

每個明文分組先與前一個密文分組進行異或后，再進行加密。由于第一個明文分組之前沒有前一個密文分組，所以需要選擇一個初始向量IV（InitializationVector），這個初始向量相當于c0。密文隱藏了明文的模式；通過選擇不同的初始向量，可以使重復的明文產生不同的密文，而無需重新產生密鑰；CBC模式適合傳輸長報文，是SSL、IPSec等協(xié)議的標準分組加密工作模式。IV應該像密鑰一樣安全傳輸和存儲；如果明文分組中出現錯誤，那么錯誤會傳遞給當前密文分組以及后面所有密文分組；如果某個密文分組發(fā)生錯誤，那么錯誤會影響當前解密的明文分組以及下一個解密的明文分組；CBC模式的加密過程是不能并行運算的，但是解密過程可以并行運算。密碼反饋模式

密碼反饋模式簡稱CFB（CipherFeedback），前一個密文分組會被送回到密碼算法的輸入端。如果明文分組的大小為s比特，那么首先選擇一個n比特（n>s）的初始向量V1=IV，然后利用密鑰k加密該向量得到n比特序列。取該序列中高位的s比特與明文分組進行異或運算，得到s比特的密文分組。在加密第2個明文分組時，首先將初始向量左移s比特，然后將上一輪加密生成的s比特的密文分組附加到其后形成新一輪的向量，后續(xù)加密過程與第1個明文分組的加密過程相同。用同樣的方法完成全部t個明文分組的加密。

CFB模式加密和解密過程都使用了分組加密算法，本質上是將分組加密算法作為一個密鑰流生成器來使用。密碼反饋模式與CBC模式類似，通過CFB模式生成的密文隱藏了明文的模式，并且選擇的初始向量IV不同，那么得到的密文也不相同。明文分組的長度s可以由用戶來確定，該模式適用于不同的消息格式要求。加密

c1=m1

⊕MSBs(Ek(V1))

ci=mi

⊕MSBs(Ek(LSBn-s(Vi-1)||ci-1)),2≤i≤t解密

m1=c1

⊕MSBs(Ek(V1))

mi=ci

⊕MSBs(Ek(LSBn-s(Vi-1)||ci-1)),2≤i≤t密碼反饋模式CFB模式的加密過程是不能并行運算的，但是解密過程可以并行運算。在CFB模式中，加密運算不需要明文，所以在明文未知的情況下可以提前加密向量，等明文已知時可以直接通過異或運算處理明文分組，從而大大提高了系統(tǒng)的運算效率。在CFB模式中，可以利用預處理的方式來提高整個系統(tǒng)的加密效率。如果某個明文分組發(fā)生錯誤，那么由它生成的密文分組會發(fā)生錯誤，是否影響后續(xù)密文分組，取決于向量的長度和密文分組長度的關系。如果某個密文分組發(fā)生錯誤，那么解密的當前明文分組會發(fā)生錯誤，是否影響后續(xù)密