第四章分組密碼課件

第四章分組密碼一、分組密碼概述二、分組密碼運行模式三、DES四、AES五、分組密碼的分析2023/1/31第四章分組密碼一、分組密碼概述2022/12/291一、分組密碼概述2023/1/32一、分組密碼概述2022/12/292分組密碼概述分組密碼是許多系統(tǒng)安全的一個重要組成部分?？捎糜跇?gòu)造擬隨機數(shù)生成器流密碼消息認證碼(MAC)和雜湊函數(shù)消息認證技術(shù)、數(shù)據(jù)完整性機構(gòu)、實體認證協(xié)議以及單鑰數(shù)字簽字體制的核心組成部分。

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

這種密碼實質(zhì)上是字長為m的數(shù)字序列的代換密碼。

解密算法加密算法密鑰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)2023/1/35分組密碼概述明文序列x1,x2,…,xi,…解

分組密碼概述通常取n=m。若n>m，則為有數(shù)據(jù)擴展的分組密碼。若n<m，則為有數(shù)據(jù)壓縮的分組密碼。2023/1/36

分組密碼概述通常取n=m。2022/12/296分組密碼設(shè)計問題

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

易于軟件和硬件高速實現(xiàn)。數(shù)據(jù)擴展：

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

2023/1/39分組密碼算法應滿足的要求加密和解密運算簡單：2022/12/代換網(wǎng)絡(luò)代換是輸入集A到輸出A’上的雙射變換：

fk：AA＇

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

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

S盒x5

x4

x3

x2

x1

x0y3

y2

y1

y0DES的S盒2023/1/313代換盒(S盒)在密碼設(shè)計中，可選n=rDES的S1-盒的輸入和輸出關(guān)系x5x0x5x4x3x2x1x010101100列號0123456789101112131415行號01441312151183106125907101574142131106121195382411481362111512973105031512824917511214100613

(y3

,

y2,

y1

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

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

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

Li=Ri-1

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

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

加密函數(shù)f(x,k)，實現(xiàn)F2n×F2t

F2n的映射。其中，n是分組長，t是密鑰長。若對每個密鑰取值都有f[f(x,k)，k]=x，即f(x,k)2=I(恒等置換)則稱其為對合密碼，以fI表示。2023/1/320對合密碼(InvolutionCipher)20I型迭代分組密碼以對合密碼函數(shù)構(gòu)造的多輪迭代分組密碼。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)]

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

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

F2n

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

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

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

III型迭代分組密碼群密碼：若密鑰與明文、密文取自同一空III型迭代分組密碼輪函數(shù)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

2023/1/324III型迭代分組密碼輪函數(shù)FIV型迭代分組密碼

在III型密碼的輪函數(shù)基礎(chǔ)上，再增加一個對合置換PI，構(gòu)成IV型迭代分組密碼的輪函數(shù)

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

IV型迭代分組密碼輪函數(shù)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

2023/1/326

IV型迭代分組密碼輪函數(shù)F二、分組碼的運行模式2023/1/327二、分組碼的運行模式2022/12/2927

主要工作模式

即使有了安全的分組密碼算法，也需要采用適當?shù)墓ぷ髂Ｊ絹黼[蔽明文的統(tǒng)計特性、數(shù)據(jù)的格式等，以提高整體的安全性，降低刪除、重放、插入和偽造成功的機會。電子碼本(ECB)密碼反饋鏈接(CBC)

密碼反饋(CFB)輸出反饋(OFB)。

2023/1/328主要工作模式

電碼本ECB模式直接利用加密算法分別對分組數(shù)據(jù)組加密。在給定的密鑰下同一明文組總產(chǎn)生同樣的密文組。這會暴露明文數(shù)據(jù)的格式和統(tǒng)計特征。

明文數(shù)據(jù)都有固定的格式，需要以協(xié)議的形式定義，重要的數(shù)據(jù)常常在同一位置上出現(xiàn)，使密碼分析者可以對其進行統(tǒng)計分析、重傳和代換攻擊。2023/1/329電碼本ECB模式直接利用加密算法分別對分組數(shù)據(jù)組加密

電碼本ECB模式

xykDESyxkDES-12023/1/330電碼本ECB模式密碼分組鏈接CBC模式每個明文組xi加密之前，先與反饋至輸入端的前一組密文yi-1按位模2求和后，再送至加密算法加密各密文組yi不僅與當前明文組xi有關(guān)，而且通過反饋作用還與以前的明文組x1,x2,…,xi-1，有關(guān)2023/1/331密碼分組鏈接CBC模式每個明文組xi加密之前，先與反饋至輸入密碼分組鏈接CBC模式初始矢量IV(InitialVector)：第一組明文xi加密時尚無反饋密文，為此需要在寄存器中預先置入一個。收發(fā)雙方必須選用同一IV。實際上，IV的完整性要比其保密性更為重要。在CBC模式下，最好是每發(fā)一個消息，都改變IV，比如將其值加一。2023/1/332密碼分組鏈接CBC模式初始矢量IV(InitialVec密碼分組鏈接CBC模式

CBC模式xiyikDESyix’kDES-1++64bit存儲64bit存儲yi-12023/1/333密碼分組鏈接CBC模式填充(Padding)

給定加密消息的長度是隨機的，按64bit分組時，最后一組消息長度可能不足64bit?？梢蕴畛湟恍?shù)字，通常用最后1字節(jié)作為填充指示符（PI）。它所表示的十進制數(shù)字就是填充占有的字節(jié)數(shù)。數(shù)據(jù)尾部、填充字符和填充指示符一起作為一組進行加密。

數(shù)據(jù)填充PI2023/1/334填充(Padding)給定加密消息的長度是隨機的，按CBC的錯誤傳播1.明文有一組中有錯，會使以后的密文組都受影響，但經(jīng)解密后的恢復結(jié)果，除原有誤的一組外，其后各組明文都正確地恢復。2.若在傳送過程中，某組密文組yi出錯時，則該組恢復的明文x’i和下一組恢復數(shù)據(jù)x’i+1出錯。再后面的組將不會受yi中錯誤比特的影響。2023/1/335CBC的錯誤傳播2022/12/2935k-比特密碼反饋CFB模式若待加密消息必須按字符(如電傳電報)或按比特處理時，可采用CFB模式。CFB實際上是將加密算法DES作為一個密鑰流產(chǎn)生器，當k＝1時就退化為前面討論的流密碼了。CFB與CBC的區(qū)別是反饋的密文長度為k，且不是直接與明文相加，而是反饋至密鑰產(chǎn)生器。2023/1/336k-比特密碼反饋CFB模式若待加密消息必須按字符(如電傳電報k-比特密碼反饋CFB模式

CFB模式

+

+xixiyiyikkXi64bitXi64bitYi64bitYi64bitDES

DES-1選最左邊

k位選最左邊

k位kbitkbityi-Lyi-2yi-12023/1/337k-比特密碼反饋CFB模式++xixiyiyikkXk-比特密碼反饋CFB模式CFB的優(yōu)點它特別適于用戶數(shù)據(jù)格式的需要。能隱蔽明文數(shù)據(jù)圖樣，也能檢測出對手對于密文的篡改。CFB的缺點對信道錯誤較敏感，且會造成錯誤傳播。CFB也需要一個初始矢量，并要和密鑰同時進行更換。2023/1/338k-比特密碼反饋CFB模式CFB的優(yōu)點2022/12/293輸出反饋OFB模式將分組密碼算法作為一個密鑰流產(chǎn)生器，其輸出的k-bit密鑰直接反饋至分組密碼的輸入端，同時這k-bit密鑰和輸入的k-bit明文段進行對應位模2相加?？朔薈BC和CFB的錯誤傳播所帶來的問題。對于密文被篡改難以進行檢測不具有自同步能力，要求系統(tǒng)要保持嚴格的同步2023/1/339輸出反饋OFB模式將分組密碼算法作為一個密鑰流產(chǎn)生器，其輸出輸出反饋OFB模式

OFB模式

+xiyik64bit64bitDES選最左邊

k位ki64bit

寄存器kbitkbit

+xiyik64bit64bit

DES-1選最左邊

k位kbit64bit

寄存器kbitki2023/1/340輸出反饋OFB模式+xiyik64bit64bitDEOCB模式2023/1/341OCB模式2022/12/2941OCB模式functionocb-aes-encrypt(K,M,Nonce)begin

Offset=AES(K,Noncexor

L)Checksum=0

for

i=1to

m-1dobegin

Offset=Offsetxor

L(ntz(i))Checksum=Checksumxor

M[i]C[i]=OffsetxorAES(K,M[i]xorOffset)

end

Offset=Offsetxor

L(ntz(m))Pad=AES(K,len(M[m])xor

L(-1)xorOffset)C[m]=M[m]xor(thefirst|M[m]|bitsofPad)Checksum=ChecksumxorPadxor

C[m]0*FullTag=AES(K,ChecksumxorOffset)Tag=aprefixofFullTag(ofthedesiredlength)

return

C[1]...C[m-1]C[m]Tag

end

L=AES(K,0).

L(0)=Lfori>0,L(i)=L(i-1)<<1ifthefirstbitofL(i-1)is0L(i)=(L(i-1)<<1)xor0x00000000000000000000000000000087otherwise.L(-1)=L>>1ifthelastbitofLis0,L(-1)=L>>1xor0x80000000000000000000000000000043otherwise.2023/1/342OCB模式functionocb-aes-encrypt(比較和選用ECB模式，簡單、高速，但最弱、易受重發(fā)攻擊，一般不推薦。CBC適用于文件加密，但較ECB慢。安全性加強。當有少量錯誤時，也不會造成同步錯誤。OFB和CFB較CBC慢許多。每次迭代只有少數(shù)bit完成加密。若可以容忍少量錯誤擴展，則可換來恢復同步能力，此時用CFB。在字符為單元的流密碼中多選CFB模式。OFB用于高速同步系統(tǒng)，不容忍差錯傳播。2023/1/343比較和選用ECB模式，簡單、高速，但最弱、易受重發(fā)攻擊，一般三、美國數(shù)據(jù)加密標準—DES（DataEncryptionStandard）2023/1/344三、美國數(shù)據(jù)加密標準—DES（DataEncryption美國制定數(shù)據(jù)加密標準簡況目的

通信與計算機相結(jié)合是人類步入信息社會的一個階梯，它始于六十年代末，完成于90年代初。計算機通信網(wǎng)的形成與發(fā)展，要求信息作業(yè)標準化，安全保密亦不例外。只有標準化，才能真正實現(xiàn)網(wǎng)的安全，才能推廣使用加密手段，以便于訓練、生產(chǎn)和降低成本。

2023/1/345美國制定數(shù)據(jù)加密標準簡況目的2022/12/2945美國制定數(shù)據(jù)加密標準簡況美國NBS在1973年5月15公布了征求建議。1974年8月27日NBS再次出公告征求建議，對建議方案提出如下要求：算法必須完全確定而無含糊之處；算法必須有足夠高的保護水準，即可以檢測到威脅，恢復密鑰所必須的運算時間或運算次數(shù)足夠大；保護方法必須只依賴于密鑰的保密；對任何用戶或產(chǎn)品供應者必須是不加區(qū)分的。2023/1/346美國制定數(shù)據(jù)加密標準簡況美國NBS在1973年5月15公布了美國制定數(shù)據(jù)加密標準簡況IBM公司在1971年完成的LUCIFER密碼(64bit分組，代換-置換，128bit密鑰)的基礎(chǔ)上，改進成為建議的DES體制1975年3月17日NBS公布了這個算法，并說明要以它作為聯(lián)邦信息處理標準，征求各方意見。1977年1月15日建議被批準為聯(lián)邦標準[FIPSPUB46]，并設(shè)計推出DES芯片。1981年美國ANSI將其作為標準，稱之為DEA[ANSIX3.92]1983年國際標準化組織(ISO)采用它作為標準，稱作DEA-1

2023/1/347美國制定數(shù)據(jù)加密標準簡況IBM公司在1971年完成的LUCI美國制定數(shù)據(jù)加密標準簡況NSA宣布每隔5年重新審議DES是否繼續(xù)作為聯(lián)邦標準，1988年（FIPS46-1）、1993年（FIPS46-2），1998年不再重新批準DES為聯(lián)邦標準。雖然DES已有替代的數(shù)據(jù)加密標準算法，但它仍是迄今為止得到最廣泛應用的一種算法，也是一種最有代表性的分組加密體制。1993年4月，Clinton政府公布了一項建議的加密技術(shù)標準，稱作密鑰托管加密技術(shù)標準EES(EscrowedEncryptionStandard)。算法屬美國政府SECRET密級。2023/1/348美國制定數(shù)據(jù)加密標準簡況NSA宣布每隔5年重新審議DES是否美國制定數(shù)據(jù)加密標準簡況DES發(fā)展史確定了發(fā)展公用標準算法模式，而EES的制定路線與DES的背道而馳。人們懷疑有陷門和政府部門肆意侵犯公民權(quán)利。此舉遭到廣為反對。1995年5月AT&TBellLab的M.Blaze博士在PC機上用45分鐘時間使SKIPJACK的LEAF協(xié)議失敗，偽造ID碼獲得成功。1995年7月美國政府宣布放棄用EES來加密數(shù)據(jù)，只將它用于語音通信。1997年1月美國NIST著手進行AES（AdvancedEncryptionStandard）的研究，成立了標準工作室。2001年Rijndael被批準為AES標準。2023/1/349美國制定數(shù)據(jù)加密標準簡況DES發(fā)展史確定了發(fā)展公用標準算法模

DES算法分組長度為64bits(8bytes)密文分組長度也是64bits。密鑰長度為64bits，有8bits奇偶校驗，有效密鑰長度為56bits。算法主要包括：初始置換IP、16輪迭代的乘積變換、逆初始置換IP-1以及16個子密鑰產(chǎn)生器。

2023/1/350

DES算法分組長度為64bits(8bytes)2DES算法框圖

輸入64bit明文數(shù)據(jù)初始置換IP乘積變換（16輪迭代）逆初始置換IP-164bit密文數(shù)據(jù)輸出

標準數(shù)據(jù)加密算法2023/1/351DES算法框圖初始置換IP將64bit明文的位置進行置換，得到一個亂序的64bit明文組，而后分成左右兩段，每段為32bit，以L0和R0表示，IP中各列元素位置號數(shù)相差為8，相當于將原明文各字節(jié)按列寫出，各列比特經(jīng)過偶采樣和奇采樣置換后，再對各行進行逆序。將陣中元素按行讀出構(gòu)成置換輸出。逆初始置換IP-1。將16輪迭代后給出的64bit組進行置換，得到輸出的密文組。輸出為陣中元素按行讀得的結(jié)果。IP和IP-1在密碼意義上作用不大，它們的作用在于打亂原來輸入x的ASCII碼字劃分的關(guān)系，并將原來明文的校驗位x8,x16,,x64變成為IP輸出的一個字節(jié)。2023/1/352初始置換IP將64bit明文的位置進行置換，得到一個亂序的

Li-1(32bit)Ri-1(32bit)

選擇擴展運算E48bit寄存器按bit模2加密48bit寄存器選擇壓縮運算S32bit寄存器置換運算P按bit模2和

Li(32bit)Ri(32bit)乘積變換框圖密鑰產(chǎn)生器2023/1/353密鑰產(chǎn)生器2022/12/2953乘積變換它是DES算法的核心部分。將經(jīng)過IP置換后的數(shù)據(jù)分成32bit的左右兩組，在迭代過程中彼此左右交換位置。每次迭代時只對右邊的32bit進行一系列的加密變換，在此輪迭代即將結(jié)束時，把左邊的32bit與右邊得到的32bit逐位模2相加，作為下一輪迭代時右邊的段，并將原來右邊未經(jīng)變換的段直接送到左邊的寄存器中作為下一輪迭代時左邊的段。在每一輪迭代時，右邊的段要經(jīng)過選擇擴展運算E、密鑰加密運算、選擇壓縮運算S、置換運算P和左右混合運算。2023/1/354乘積變換它是DES算法的核心部分。將經(jīng)過IP置換后的數(shù)據(jù)分成乘積變換

選擇擴展運算E。將輸入的32bitRi-1擴展成48bit的輸出，令s表示E原輸入數(shù)據(jù)比特的原下標，則E的輸出是將原下標s0或1(mod4)的各比特重復一次得到的，即對原第32,1,4,5,8,9,12,13,16,17,20,21,24,25,28,29各位都重復一次,實現(xiàn)數(shù)據(jù)擴展。將表中數(shù)據(jù)按行讀出得到48bit輸出。

密鑰加密運算。將子密鑰產(chǎn)生器輸出的48bit子密鑰ki與選擇擴展運算E輸出的48bits數(shù)據(jù)按位模2相加。

選擇壓縮運算S。將前面送來的48bit數(shù)據(jù)自左至右分成8組，每組為6bit。而后并行送入8個S一盒，每個S盒為一非線性代換網(wǎng)絡(luò)，有4個輸出，運算S的框圖在圖4-4-6中給出。

p.186

圖4-4-6選擇壓縮運算S

置換運算P。對S1至S8盒輸出的32bit數(shù)據(jù)進行坐標置換，如圖4-4-7所示。置換P輸出的32bit數(shù)據(jù)與左邊32bit即Ri-1逐位模2相加，所得到的32bit作為下一輪迭代用的右邊的數(shù)字段。并將Ri-1并行送到左邊的寄存器，作為下一輪迭代用的左邊的數(shù)字段。子密鑰產(chǎn)生器。將64bit初始密鑰經(jīng)過置換選擇PC1、循環(huán)移位置換、置換選擇PC2給出每次迭代加密用的子密鑰ki，參看圖4-4-8。在64bit初始密鑰中有8位為校驗位，其位置號為8、16、32、48、56和64。其余56位為有效位，用于子密鑰計算。將這56位送入置換選擇PC1，參看圖4-4-9。經(jīng)過坐標置換后分成兩組，每級為28bit，分別送入C寄存器和D寄存器中。在各次迭代中，C和D寄存器分別將存數(shù)進行左循環(huán)移位置換，移位次數(shù)在表4-4-2中給出。每次移位后，將C和D寄存器原存數(shù)送給置換選擇PC2，見圖4-4-10。置換選擇PC2將C中第9、18、22、25位和D中第7、9、15、26位刪去，并將其余數(shù)字置換位置后送出48bit數(shù)字作為第i次迭代時所用的子密鑰ki。p.186p.186

圖4-4-7置換運算P

圖4-4-8子密鑰產(chǎn)生器框圖表4-4-2移位次數(shù)表第i次迭代12345678910111213141516循環(huán)左移次數(shù)1122222212222221

p.187

圖4-4-9置換選擇PC1

至此，我們已將DES算法的基本構(gòu)成作了介紹，加密過程可歸結(jié)如下：令I(lǐng)P表示初始置換，KS表示密鑰運算，i為迭代次數(shù)變量，KEY為64bit密鑰，f為加密函數(shù)，表示逐位模2求和。2023/1/355乘積變換選擇擴展運算E。將輸入的32bitRi-1擴選擇壓縮運算S

6bit選擇函數(shù)組4bit

48bit寄存器32bit寄存器S1S2S3S4S5S6S7S82023/1/356選擇壓縮運算S48bit寄存器32bit寄存器S乘積變換

置換運算P。對S1至S8盒輸出的32bit數(shù)據(jù)進行坐標置換，置換P輸出的32bit數(shù)據(jù)與左邊32bit即Ri-1逐位模2相加，所得到的32bit作為下一輪迭代用的右邊的數(shù)字段。并將Ri-1并行送到左邊的寄存器，作為下一輪迭代用的左邊的數(shù)字段。

子密鑰產(chǎn)生器。將64bit初始密鑰經(jīng)過置換選擇PC1、循環(huán)移位置換、置換選擇PC2給出每次迭代加密用的子密鑰ki，2023/1/357乘積變換置換運算P。對S1至S8盒輸出的32bit數(shù)據(jù)

子密鑰產(chǎn)生器框圖

密鑰（64bit）置換選擇1，PC1置換選擇2，PC2

Ci(28bit)

Di(28bit)循環(huán)左移ti+1bit循環(huán)左移ti+1bit除去第8,16,,64位(8個校驗位)ki2023/1/358

子密鑰產(chǎn)生器框圖密鑰（64bit）DES的安全性互補性。DES算法具有下述性質(zhì)。若明文組x逐位取補，密鑰k逐位取補，即y=DESk(x),則有這種互補性會使DES在選擇明文破譯下所需的工作量減半。弱密鑰和半弱密鑰。DES算法在每次迭代時都有一個子密鑰供加密用。如果給定初始密鑰k，各輪的子密鑰都相同，即有k1=k2=…=k16就稱給定密鑰k為弱密鑰(Weakkey)。2023/1/359DES的安全性互補性。DES算法具有下述性質(zhì)。若明文組x逐位DES的安全性若k為弱密鑰，則有

DESk(DESk(x))=xDESk-1(DESk-1(x))=x即以k對x加密兩次或解密兩次都可恢復出明文。其加密運算和解密運算沒有區(qū)別。弱密鑰下使DES在選擇明文攻擊下的搜索量減半。如果隨機地選擇密鑰，弱密鑰所占比例極小，而且稍加注意就不難避開。因此，弱密鑰的存在不會危及DES的安全性。2023/1/360DES的安全性若k為弱密鑰，則有2022/12/2960DES的安全性密文與明文、密文與密鑰的相關(guān)性。

Meyer[1978]詳細研究了DES的輸入明文與密文及密鑰與密文之間的相關(guān)性。表明每個密文比特都是所有明文比特和所有密鑰比特的復合函數(shù)，并且指出達到這一要求所需的迭代次數(shù)至少為5。Konheim[1981]用2檢驗證明，迭代8次后輸出和輸入就可認為是不相關(guān)的了。2023/1/361DES的安全性密文與明文、密文與密鑰的相關(guān)性。2022/12DES的安全性S盒設(shè)計。

DES靠S盒實現(xiàn)非線性變換。密鑰搜索機。

對DES安全性批評意見中，較為一致的看法是DES的密鑰短了些。IBM最初向NBS提交的建議方案采用112bits密鑰，但公布的DES標準采用64bits密鑰。有人認為NSA故意限制DES的密鑰長度。采用窮搜索對已經(jīng)對DES構(gòu)成了威脅．2023/1/362DES的安全性S盒設(shè)計。2022/12/2962二重DES用DES進行兩次加密，但這是否就意味著兩重DES加密的強度等價于112bit密鑰的密碼的強度？答案是否定的。

中途相遇攻擊法(Meet-in-the-MiddleAttack)由Diffie和Hellman[1977]最早提出，可以降低搜索量其基本想法如下。若有明文密文對(xi,yi)滿足

yi=Ek2[Ek1[xi]]則可得z=Ek1[xi]=Dk2[yi]

2023/1/363二重DES用DES進行兩次加密，但這是否就意味著兩二重DES

圖4-14-1中途相遇攻擊示意圖

zEEDDxiyixizyi

k1

k1k2k22023/1/364二重DESzEEDDxiyixizyik1k1k2k22中途相遇攻擊給定一已知明密文對(x1,y1)，可按下述方法攻擊。以密鑰k1的所有256個可能的取值對此明文x1加密，并將密文z存儲在一個表中；從所有可能的256個密鑰k2中依任意次序選出一個對給定的密文y1解密，并將每次解密結(jié)果z在上述表中查找相匹配的值。一旦找到，則可確定出兩個密鑰k1和k2；以此對密鑰k1和k2對另一已知明文密文對(x2,y2)中的明文x2進行加密，如果能得出相應的密文y2就可確定k1和k2是所要找的密鑰。2023/1/365中途相遇攻擊給定一已知明密文對(x1,y1)，可按下述方法攻中途相遇攻擊對于給定明文x，以兩重DES加密將有264個可能的密文?？赡艿拿荑€數(shù)為2112個。所以，在給定明文下，將有2112/264=248個密鑰能產(chǎn)生給定的密文。用另一對64bits明文密文對進行檢驗，就使虛報率降為248-64=2-16。這一攻擊法所需的存儲量為256×8Byte，最大試驗的加密次數(shù)2×256=257。這說明破譯雙重DES的難度為257量級。2023/1/366中途相遇攻擊對于給定明文x，以兩重DES加密將有264個可能三重DES加密加密：y=Ek1[Dk2[Ek1[x]]]解密：x=Dk1[Ek2[Dk1[y]]]稱其為加密-解密-加密方案，簡記為EDE(encrypt-decrypt-encrypt)。此方案已在ANSIX9.17和ISO8732標準中采用，并在保密增強郵遞(PEM)系統(tǒng)中得到利用。破譯它的窮舉密鑰搜索量為21125×1035量級，而用差分分析破譯也要超過1052量級。此方案仍有足夠的安全性。2023/1/367三重DES加密加密：y=Ek1[Dk2[Ek1[x]]]2四、AES2023/1/368四、AES2022/12/2968AES提出1997年1月，美國NIST向全世界密碼學界發(fā)出征集21世紀高級加密標準（AES——AdvancedEncryptionStandard）算法的公告，并成立了AES標準工作研究室，1997年4月15日的例會制定了對AES的評估標準。

2023/1/369AES提出1997年1月，美國NIST向全世AES的要求（1）AES是公開的；（2）AES為單鑰體制分組密碼；（3）AES的密鑰長度可變，可按需要增大；（4）AES適于用軟件和硬件實現(xiàn)；（5）AES可以自由地使用，或按符合美國國家標準（ANST）策略的條件使用；2023/1/370AES的要求（1）AES是公開的；2022/12/2970算法衡量條件滿足以上要求的AES算法，需按下述條件判斷優(yōu)劣a.安全性b.計算效率c.內(nèi)存要求d.使用簡便性e.靈活性。2023/1/371算法衡量條件滿足以上要求的AES算法，需按下述條件判斷優(yōu)劣2AES的評審1998年4月15日全面征集AES算法的工作結(jié)束。1998年8月20日舉行了首屆AES討論會，對涉及14個國家的密碼學家所提出的候選AES算法進行了評估和測試，初選并公布了15個被選方案，供大家公開討論。CAST-256，RC-6，CRYPTON-128，DEAL-128，F(xiàn)ROG，DFC，LOKI-97，MAGENTA，MARS，HPC,RIJNDAEL，SAFER+，SERPENT，E-2，TWOFISH。這些算法設(shè)計思想新穎，技術(shù)水平先進，算法的強度都超過3-DES，實現(xiàn)速度快于3-DES。

2023/1/372AES的評審1998年4月15日全面征集AES算法的工作結(jié)AES的評審1999年8月9日NIST宣布第二輪篩選出的5個候選算法為：

MARS(C.Burwick等,IBM），RC6TM（R.Rivest等,RSALab.)，RIJNDEAL(J.Daemen,比)，SERPENT(R.Anderson等，英、以、挪威)，TWOFISH(B.Schiener)。2000年10月2日，NIST宣布Rijndael作為新的AES2023/1/373AES的評審1999年8月9日NIST宣布第二輪篩選出的5個AES算法設(shè)計思想抵抗所有已知的攻擊；在多個平臺上速度快，編碼緊湊；設(shè)計簡單。Rijndael沒有采用Feistel結(jié)構(gòu)，輪函數(shù)由3個不同的可逆均勻變換構(gòu)成的，稱為3個層均勻變換是指狀態(tài)的每個bit都用類似的方法處理2023/1/374AES算法設(shè)計思想抵抗所有已知的攻擊；2022/12/297輪函數(shù)的3層線性混合層確保多輪之上的高度擴散；非線性層將具有最優(yōu)的“最壞情況非線性特性”的S盒并行使用；密鑰加層單輪子密鑰簡單的異或到中間狀態(tài)上，實現(xiàn)一次性掩蓋。2023/1/375輪函數(shù)的3層線性混合層2022/12/2975算法說明分組和密鑰長度可變，各自可獨立指定為128、192、256比特。狀態(tài)算法中間的結(jié)果也需要分組，稱之為狀態(tài)，狀態(tài)可以用以字節(jié)為元素的矩陣陣列表示，該陣列有4行，列數(shù)Nb為分組長度除32種子密鑰以字節(jié)為元素的矩陣陣列描述，陣列為4行，列數(shù)Nk為密鑰長度除322023/1/376算法說明分組和密鑰長度可變，各自可獨立指定為128、192、算法說明算法的輸入、輸出和種子密鑰可看成字節(jié)組成的一維數(shù)組。下標范圍輸入輸出：0－4Nb-1，種子密鑰：0－4Nk-12023/1/377算法說明算法的輸入、輸出和種子密鑰可看成字節(jié)組成的一維數(shù)組。Nb=6和Nk=4的狀態(tài)密鑰陣列按此順序放入和讀出按此順序放入2023/1/378Nb=6和Nk=4的狀態(tài)密鑰陣列按此順序放入和讀出按此順序放分組和陣列中元素對應關(guān)系分組下標n陣列位置(i,j)i=nmod4,j=[n/4];n=i+4j輪數(shù)Nr與Nb和Nk對應關(guān)系Nb=4Nb=6Nb=8Nk=4101214Nk=6121214Nk=81414142023/1/379分組和陣列中元素對應關(guān)系分組下標nNb=4Nb=6Nb=8N輪函數(shù)字節(jié)代換行移位列混合密鑰加2023/1/380輪函數(shù)字節(jié)代換2022/12/2980字節(jié)代換非線性代換，獨立地對狀態(tài)的每個字節(jié)進行，并且代換表(S盒)可逆，記為ByteSub(State),分兩步將字節(jié)作為GF(28)上的元素映射到自己的逆元將字節(jié)做如下的GF(2)上變換2023/1/381字節(jié)代換非線性代換，獨立地對狀態(tài)的每個字節(jié)進行，并且代換表(字節(jié)代換2023/1/382字節(jié)代換2022/12/2982行移位將狀態(tài)陣列的各行進行循環(huán)移位，不同行的移位量不同0行：不動1行：循環(huán)左移C1字節(jié)2行：循環(huán)左移C2字節(jié)3行：循環(huán)左移C3字節(jié)記為：ShiftRow(State)2023/1/383行移位將狀態(tài)陣列的各行進行循環(huán)移位，不同行的移位量不同202行移位移位量與分組長度的關(guān)系NbC1C2C34123612381342023/1/384行移位移位量與分組長度的關(guān)系NbC1C2C341236123列混合將每列視為GF(28)上多項式，與固定的多項式c(x)進行模x4+1乘法,要求c(x)模x4+1可逆。表示為MixColumn(State)2023/1/385列混合將每列視為GF(28)上多項式，與固定的多項式c(x)密鑰加輪密鑰與狀態(tài)進行逐比特異或。輪密鑰由種子密鑰通過密鑰編排算法得到輪密鑰長度與分組密鑰長度相同表示為AddRoundKey(State,RoundKey)2023/1/386密鑰加輪密鑰與狀態(tài)進行逐比特異或。2022/12/2986輪函數(shù)的偽C代碼Round(State,RoundKey){ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,Roundkey);}2023/1/387輪函數(shù)的偽C代碼Round(State,RoundKey)2結(jié)尾輪的輪函數(shù)Round(State,RoundKey){ByteSub(State);ShiftRow(State);AddRoundKey(State,Roundkey);}2023/1/388結(jié)尾輪的輪函數(shù)Round(State,RoundKey)20第四章分組密碼一、分組密碼概述二、分組密碼運行模式三、DES四、AES五、分組密碼的分析2023/1/389第四章分組密碼一、分組密碼概述2022/12/291一、分組密碼概述2023/1/390一、分組密碼概述2022/12/292分組密碼概述分組密碼是許多系統(tǒng)安全的一個重要組成部分?？捎糜跇?gòu)造擬隨機數(shù)生成器流密碼消息認證碼(MAC)和雜湊函數(shù)消息認證技術(shù)、數(shù)據(jù)完整性機構(gòu)、實體認證協(xié)議以及單鑰數(shù)字簽字體制的核心組成部分。

2023/1/391分組密碼概述分組密碼是許多系統(tǒng)安全的一個重要組成部分?？捎糜趹弥袑τ诜纸M碼的要求安全性運行速度存儲量(程序的長度、數(shù)據(jù)分組長度、高速緩存大小)實現(xiàn)平臺(硬、軟件、芯片)運行模式2023/1/392應用中對于分組碼的要求安全性2022/12/294分組密碼概述明文序列x1,x2,…,xi,…加密函數(shù)E:Vn×KVn

這種密碼實質(zhì)上是字長為m的數(shù)字序列的代換密碼。

解密算法加密算法密鑰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)2023/1/393分組密碼概述明文序列x1,x2,…,xi,…解

分組密碼概述通常取n=m。若n>m，則為有數(shù)據(jù)擴展的分組密碼。若n<m，則為有數(shù)據(jù)壓縮的分組密碼。2023/1/394

分組密碼概述通常取n=m。2022/12/296分組密碼設(shè)計問題

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

易于軟件和硬件高速實現(xiàn)。數(shù)據(jù)擴展：

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

2023/1/397分組密碼算法應滿足的要求加密和解密運算簡單：2022/12/代換網(wǎng)絡(luò)代換是輸入集A到輸出A’上的雙射變換：

fk：AA＇

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

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

S盒x5

x4

x3

x2

x1

x0y3

y2

y1

y0DES的S盒2023/1/3101代換盒(S盒)在密碼設(shè)計中，可選n=rDES的S1-盒的輸入和輸出關(guān)系x5x0x5x4x3x2x1x010101100列號0123456789101112131415行號01441312151183106125907101574142131106121195382411481362111512973105031512824917511214100613

(y3

,

y2,

y1

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