第四章分組密碼一、分組密碼概述二、分組密碼運行模式三、DES四、AES五、分組密碼的分析2022/12/231第四章分組密碼一、分組密碼概述2022/12/201一、分組密碼概述2022/12/232一、分組密碼概述2022/12/202分組密碼概述分組密碼是許多系統安全的一個重要組成部分。可用于構造擬隨機數生成器流密碼消息認證碼(MAC)和雜湊函數消息認證技術、數據完整性機構、實體認證協議以及單鑰數字簽字體制的核心組成部分。

2022/12/233分組密碼概述分組密碼是許多系統安全的一個重要組成部分。可用于應用中對于分組碼的要求安全性運行速度存儲量(程序的長度、數據分組長度、高速緩存大小)實現平臺(硬、軟件、芯片)運行模式2022/12/234應用中對于分組碼的要求安全性2022/12/204分組密碼概述明文序列x1,x2,…,xi,…加密函數E:Vn×KVn

這種密碼實質上是字長為m的數字序列的代換密碼。

解密算法加密算法密鑰k=(k0,k1,…,kt-1)密鑰k=(k0,k1,…,kt-1)明文x=(x0,x1,…,xm-1)明文x=(x0,x1,…,xm-1)密文x=(y0,y1,…,ym-1)2022/12/235分組密碼概述明文序列x1,x2,…,xi,…解

分組密碼概述通常取n=m。若n>m，則為有數據擴展的分組密碼。若n<m，則為有數據壓縮的分組密碼。2022/12/236

分組密碼概述通常取n=m。2022/12/206分組密碼設計問題

分組密碼的設計問題在于找到一種算法，能在密鑰控制下從一個足夠大且足夠好的置換子集中，簡單而迅速地選出一個置換，用來對當前輸入的明文的數字組進行加密變換。2022/12/237分組密碼設計問題分組密碼的設計問題在于找到分組密碼算法應滿足的要求分組長度n要足夠大：防止明文窮舉攻擊法奏效。密鑰量要足夠大：盡可能消除弱密鑰并使所有密鑰同等地好，以防止密鑰窮舉攻擊奏效。由密鑰確定置換的算法要足夠復雜：充分實現明文與密鑰的擴散和混淆，沒有簡單的關系可循，要能抗擊各種已知的攻擊。2022/12/238分組密碼算法應滿足的要求分組長度n要足夠大：2022/12/分組密碼算法應滿足的要求加密和解密運算簡單：

易于軟件和硬件高速實現。數據擴展：

一般無數據擴展，在采用同態置換和隨機化加密技術時可引入數據擴展。差錯傳播盡可能地小。

2022/12/239分組密碼算法應滿足的要求加密和解密運算簡單：2022/12/代換網絡代換是輸入集A到輸出A’上的雙射變換：

fk：AA＇

式中，k是控制輸入變量，在密碼學中則為密鑰。實現代換fk的網絡稱作代換網絡。雙射條件保證在給定k下可從密文惟一地恢復出原明文。2022/12/2310代換網絡代換是輸入集A到輸出A’上的雙射變換：2022/12代換網絡代換fk的集合：

S={fkkK}K是密鑰空間。如果網絡可以實現所有可能的2n!個代換，則稱其為全代換網絡。全代換網絡密鑰個數必須滿足條件：＃{k}2n!2022/12/2311代換網絡代換fk的集合：2022/12/2011代換網絡密碼設計中需要先定義代換集S，而后還需定義解密變換集，即逆代換網絡S-1，它以密文y作為輸入矢量，其輸出為恢復的明文矢量x。要實現全代換網絡并不容易。因此實用中常常利用一些簡單的基本代換，通過組合實現較復雜的、元素個數較多的代換集。實用密碼體制的集合S中的元素個數都遠小于2n!。2022/12/2312代換網絡密碼設計中需要先定義代換集S，而后還需定義解密變換集代換盒(S盒)在密碼設計中，可選n=rn0，其中r和n0都為正整數，將設計n個變量的代換網絡化為設計r個較小的子代換網絡，而每個子代換網絡只有n0個輸入變量。稱每個子代換網絡為代換盒(SubstitutionBox)

S盒x5

x4

x3

x2

x1

x0y3

y2

y1

y0DES的S盒2022/12/2313代換盒(S盒)在密碼設計中，可選n=rDES的S1-盒的輸入和輸出關系x5x0x5x4x3x2x1x010101100列號0123456789101112131415行號01441312151183106125907101574142131106121195382411481362111512973105031512824917511214100613

(y3

,

y2,

y1

,y0)=(0,0,1,0)2022/12/2314DES的S1-盒的輸入和輸出關系x5x0擴散和混淆擴散將明文的統計特性散布到密文中。實現的方式是使明文的每一位影響密文中多位的值。2022/12/2315擴散和混淆擴散將明文的統計特性散布到密文中。實現的方式是使明S盒的設計準則迄今為止，有關方面未曾完全公開有關DES的S盒的設計準則。Branstead等曾披露過下述準則：P1S盒的輸出都不是其輸入的線性或仿射函數。P2改變S盒的一個輸入比特，其輸出至少有兩比特產生變化，即近一半產生變化。P3當S盒的任一輸入位保持不變，其它5位輸入變化時(共有25=32種情況)，輸出數字中的0和1的總數近于相等。這三點使DES的S盒能夠實現較好的混淆。2022/12/2316S盒的設計準則迄今為止，有關方面未曾完全公S盒的組合問題:如何將幾個S盒組合起來構成一個n值較大的組。

將幾個S盒的輸入端并行，并通過坐標置換(P-盒)將各S盒輸出比特次序打亂，再送到下一級各S盒的輸入端，起到了Shannon所謂的“擴散”作用。S盒提供非線性變換，將來自上一級不同的S盒的輸出進行“混淆”。經過P-盒的擴散作用使1均勻地分散到整個輸出矢量中，從而保證了輸出密文統計上的均勻性，這就是Shannon的乘積密碼的作用。2022/12/2317S盒的組合問題:如何將幾個S盒組合起來構成一個n值較大的組Feistel網絡

將nbit明文分成為左右各半、長為n/2bit的段，以L和R表示。然后進行多輪迭代，其第i輪迭代的輸出為前輪輸出的函數

Li=Ri-1

Ri=Li-1f(Ri-1,Ki)式中，Ki是第i輪用的子密鑰，f是任意密碼輪函數。稱這種分組密碼算法為Feistel網絡（FeistelNetwork），它保證加密和解密可采用同一算法實施2022/12/2318Feistel網絡將nbit明文分成為左右各半、長迭代分組密碼若以一個簡單函數f，進行多次迭代，就稱其為迭代密碼。每次迭代稱作一輪(Round)。相應函數f稱作輪函數。每一輪輸出都是前一輪輸出的函數，即y(i)=f[y(i-1),k(i)]，其中k(i)是第i輪迭代用的子密鑰，由秘密密鑰k通過密鑰生成算法產生。

子密鑰產生器kk(1)k(2)k(r)y(0)=xy(1)y(2)y(r-1)y(r)=y2022/12/2319迭代分組密碼若以一個簡單函數f，進行多次迭代，就稱其為迭代密對合密碼(InvolutionCipher)

加密函數f(x,k)，實現F2n×F2t

F2n的映射。其中，n是分組長，t是密鑰長。若對每個密鑰取值都有f[f(x,k)，k]=x，即f(x,k)2=I(恒等置換)則稱其為對合密碼，以fI表示。2022/12/2320對合密碼(InvolutionCipher)20I型迭代分組密碼以對合密碼函數構造的多輪迭代分組密碼。E[x,k]=fI[fI[

fI[fI[x,k(1)]，k(2)]，k(r-1)]，k(r)]D[y,k]=fI[fI[

fI[fI[y,k(r)]，k(r-1)]，k(2)]，k(1)]

缺點：對任意偶數輪變換，若對所有i選擇k(2i-1)=k(2i)，則加密的變換等價于恒等變換，在實用中需要避免這類密鑰選擇。2022/12/2321I型迭代分組密碼以對合密碼函數構造的多輪迭代分組密碼。202

對合置換和II型迭代分組密碼對合置換令P是對x的置換，即P：F2n

F2n

，若對所有xGF(2n)，有P[P[x]]=x，即PP=I(恒等置換)，以PI表示。II型迭代分組密碼每輪采用對合密碼函數和對合置換級連，即F[x,k]＝PI[fI[x,k]]并選解密子密鑰與加密子密鑰逆序，則加密解密可用同一器件完成。DES、FEAL和LOKI等都屬此類。2022/12/2322

對合置換和II型迭代分組密碼對合置換2022/12/202

III型迭代分組密碼群密碼：若密鑰與明文、密文取自同一空間GF(2n)，且y=xk式中，是群運算，則稱其為群密碼。顯然x可通過k的逆元求得x=yk-1令xk為一群密碼，令fI(x,kB)為一對合密碼，以F[x,k]＝fI(xkA,kB)為迭代函數，可以III型多輪迭代分組密碼。在最后一輪中，另外加了一次群密碼運算，用以保證整個加、解密的對合性。2022/12/2323

III型迭代分組密碼群密碼：若密鑰與明文、密文取自同一空III型迭代分組密碼輪函數F

F

y(1)y(r-1)(a)加密

x

fI···

fI

y

kA(1)kB(1)kA(r)kB(r)kA(r+1)F

F

y

fI···fI

x

(b)解密

kA(r+1))-1

kB(r)(kA(r))-1

kB(1)(kA)-1

2022/12/2324III型迭代分組密碼輪函數FIV型迭代分組密碼

在III型密碼的輪函數基礎上，再增加一個對合置換PI，構成IV型迭代分組密碼的輪函數

F[x,k]＝PI[fI[xkA,kB]]2022/12/2325IV型迭代分組密碼在III型密碼的輪函

IV型迭代分組密碼輪函數Fy(1)y(r-1)

F

x

fIPI···

fI

PIPI

y

kA(1)kB(1)

kA(r)

kB(r)

kA(r+1)(a)加密

FF

y

fIPI···

fI

x

(b)解密(kA(r+1))-1kB(r)

PI[kA(r)]-1

PI[kA(2)]-1

kB(1)(kA(1))-1

2022/12/2326

IV型迭代分組密碼輪函數F第四章分組密碼一、分組密碼概述二、分組密碼運行模式三、DES四、AES五、分組密碼的分析2022/12/2327第四章分組密碼一、分組密碼概述2022/12/201一、分組密碼概述2022/12/2328一、分組密碼概述2022/12/202分組密碼概述分組密碼是許多系統安全的一個重要組成部分。可用于構造擬隨機數生成器流密碼消息認證碼(MAC)和雜湊函數消息認證技術、數據完整性機構、實體認證協議以及單鑰數字簽字體制的核心組成部分。

2022/12/2329分組密碼概述分組密碼是許多系統安全的一個重要組成部分。可用于應用中對于分組碼的要求安全性運行速度存儲量(程序的長度、數據分組長度、高速緩存大小)實現平臺(硬、軟件、芯片)運行模式2022/12/2330應用中對于分組碼的要求安全性2022/12/204分組密碼概述明文序列x1,x2,…,xi,…加密函數E:Vn×KVn

這種密碼實質上是字長為m的數字序列的代換密碼。

解密算法加密算法密鑰k=(k0,k1,…,kt-1)密鑰k=(k0,k1,…,kt-1)明文x=(x0,x1,…,xm-1)明文x=(x0,x1,…,xm-1)密文x=(y0,y1,…,ym-1)2022/12/2331分組密碼概述明文序列x1,x2,…,xi,…解

分組密碼概述通常取n=m。若n>m，則為有數據擴展的分組密碼。若n<m，則為有數據壓縮的分組密碼。2022/12/2332

分組密碼概述通常取n=m。2022/12/206分組密碼設計問題

分組密碼的設計問題在于找到一種算法，能在密鑰控制下從一個足夠大且足夠好的置換子集中，簡單而迅速地選出一個置換，用來對當前輸入的明文的數字組進行加密變換。2022/12/2333分組密碼設計問題分組密碼的設計問題在于找到分組密碼算法應滿足的要求分組長度n要足夠大：防止明文窮舉攻擊法奏效。密鑰量要足夠大：盡可能消除弱密鑰并使所有密鑰同等地好，以防止密鑰窮舉攻擊奏效。由密鑰確定置換的算法要足夠復雜：充分實現明文與密鑰的擴散和混淆，沒有簡單的關系可循，要能抗擊各種已知的攻擊。2022/12/2334分組密碼算法應滿足的要求分組長度n要足夠大：2022/12/分組密碼算法應滿足的要求加密和解密運算簡單：

易于軟件和硬件高速實現。數據擴展：

一般無數據擴展，在采用同態置換和隨機化加密技術時可引入數據擴展。差錯傳播盡可能地小。

2022/12/2335分組密碼算法應滿足的要求加密和解密運算簡單：2022/12/代換網絡代換是輸入集A到輸出A’上的雙射變換：

fk：AA＇

式中，k是控制輸入變量，在密碼學中則為密鑰。實現代換fk的網絡稱作代換網絡。雙射條件保證在給定k下可從密文惟一地恢復出原明文。2022/12/2336代換網絡代換是輸入集A到輸出A’上的雙射變換：2022/12代換網絡代換fk的集合：

S={fkkK}K是密鑰空間。如果網絡可以實現所有可能的2n!個代換，則稱其為全代換網絡。全代換網絡密鑰個數必須滿足條件：＃{k}2n!2022/12/2337代換網絡代換fk的集合：2022/12/2011代換網絡密碼設計中需要先定義代換集S，而后還需定義解密變換集，即逆代換網絡S-1，它以密文y作為輸入矢量，其輸出為恢復的明文矢量x。要實現全代換網絡并不容易。因此實用中常常利用一些簡單的基本代換，通過組合實現較復雜的、元素個數較多的代換集。實用密碼體制的集合S中的元素個數都遠小于2n!。2022/12/2338代換網絡密碼設計中需要先定義代換集S，而后還需定義解密變換集代換盒(S盒)在密碼設計中，可選n=rn0，其中r和n0都為正整數，將設計n個變量的代換網絡化為設計r個較小的子代換網絡，而每個子代換網絡只有n0個輸入變量。稱每個子代換網絡為代換盒(SubstitutionBox)

S盒x5

x4

x3

x2

x1

x0y3

y2

y1

y0DES的S盒2022/12/2339代換盒(S盒)在密碼設計中，可選n=rDES的S1-盒的輸入和輸出關系x5x0x5x4x3x2x1x010101100列號0123456789101112131415行號01441312151183106125907101574142131106121195382411481362111512973105031512824917511214100613

(y3

,

y2,

y1

,y0)=(0,0,1,0)2022/12/2340DES的S1-盒的輸入和輸出關系x5x0擴散和混淆擴散將明文的統計特性散布到密文中。實現的方式是使明文的每一位影響密文中多位的值。2022/12/2341擴散和混淆擴散將明文的統計特性散布到密文中。實現的方式是使明S盒的設計準則迄今為止，有關方面未曾完全公開有關DES的S盒的設計準則。Branstead等曾披露過下述準則：P1S盒的輸出都不是其輸入的線性或仿射函數。P2改變S盒的一個輸入比特，其輸出至少有兩比特產生變化，即近一半產生變化。P3當S盒的任一輸入位保持不變，其它5位輸入變化時(共有25=32種情況)，輸出數字中的0和1的總數近于相等。這三點使DES的S盒能夠實現較好的混淆。2022/12/2342S盒的設計準則迄今為止，有關方面未曾完全公S盒的組合問題:如何將幾個S盒組合起來構成一個n值較大的組。

將幾個S盒的輸入端并行，并通過坐標置換(P-盒)將各S盒輸出比特次序打亂，再送到下一級各S盒的輸入端，起到了Shannon所謂的“擴散”作用。S盒提供非線性變換，將來自上一級不同的S盒的輸出進行“混淆”。經過P-盒的擴散作用使1均勻地分散到整個輸出矢量中，從而保證了輸出密文統計上的均勻性，這就是Shannon的乘積密碼的作用。2022/12/2343S盒的組合問題:如何將幾個S盒組合起來構成一個n值較大的組Feistel網絡

將nbit明文分成為左右各半、長為n/2bit的段，以L和R表示。然后進行多輪迭代，其第i輪迭代的輸出為前輪輸出的函數

Li=Ri-1

Ri=Li-1f(Ri-1,Ki)式中，Ki是第i輪用的子密鑰，f是任意密碼輪函數。稱這種分組密碼算法為Feistel網絡（FeistelNetwork），它保證加密和解密可采用同一算法實施2022/12/2344Feistel網絡將nbit明文分成為左右各半、長迭代分組密碼若以一個簡單函數f，進行多次迭代，就稱其為迭代密碼。每次迭代稱作一輪(Round)。相應函數f稱作輪函數。每一輪輸出都是前一輪輸出的函數，即y(i)=f[y(i-1),k(i)]，其中k(i)是第i輪迭代用的子密鑰，由秘密密鑰k通過密鑰生成算法產生。

子密鑰產生器kk(1)k(2)k(r)y(0)=xy(1)y(2)y(r-1)y(r)=y2022/12/2345迭代分組密碼若以一個簡單函數f，進行多次迭代，就稱其為迭代密對合密碼(InvolutionCipher)

加密函數f(x,k)，實現F2n×F2t

F2n的映射。其中，n是分組長，t是密鑰長。若對每個密鑰取值都有f[f(x,k)，k]=x，即f(x,k)2=I(恒等置換)則稱其為對合密碼，以fI表示。2022/12/2346對合密碼(InvolutionCipher)20I型迭代分組密碼以對合密碼函數構造的多輪迭代分組密碼。E[x,k]=fI[fI[

fI[fI[x,k(1)]，k(2)]，k(r-1)]，k(r)]D[y,k]=fI[fI[

fI[fI[y,k(r)]，k(r-1)]，k(2)]，k(1)]

缺點：對任意偶數輪變換，若對所有i選擇k(2i-1)=k(2i)，則加密的變換等價于恒等變換，在實用中需要避免這類密鑰選擇。2022/12/2347I型迭代分組密碼以對合密碼函數構造的多輪迭代分組密碼。202

對合置換和II型迭代分組密碼對合置換令P是對x的置換，即P：F2n

F2n

，若對所有xGF(2n)，有P[P[x]]=x，即PP=I(恒等置換)，以PI表示。II型迭代分組密碼每輪采用對合密碼函數和對合置換級連，即F[x,k]＝PI[fI[x,k]]并選解密子密鑰與加密子密鑰逆序，則加密解密可用同一器件完成。DES、FEAL和LOKI等都屬此類。2022/12/2348

對合置換和II型迭代分組密碼對合置換2022/12/202

III型迭代分組密碼群密碼：若密鑰與明文、密文取自同一空間GF(2n)，且y=xk式中，是群運算，則稱其為群密碼。顯然x可通過k的逆元求得x=yk-1令xk為一群密碼，令fI(x,kB)為一對合密碼，以F[x,k]＝fI(xkA,kB)為迭代函數，可以III型多輪迭代分組密碼。在最后一輪中，另外加了一次群密碼運算，用以保證整個加、解密的對合性。2022/12/2349

III型迭代分組密碼群密碼：若密鑰與明文、密文取自同一空III型迭代分組密碼輪函數F

F

y(1)y(r-1)(a)加密

x

fI···

fI

y

kA(1)kB(1)kA(r)kB(r)kA(r+1)F