第7 8講-分組密碼

第四章分組密碼

1明文處理方式分組密碼（blockcipher)

將明文分成固定長度的組，用同一密鑰和算法對每一塊加密，輸出也是固定長度的密文。

流密碼（streamcipher)

又稱序列密碼。序列密碼每次加密一位或一字節(jié)的明文。2§4.1分組密碼的基本原理

定義1

分組密碼就是將明文數(shù)據(jù)按固定長度進(jìn)行分組，然后在同一密鑰控制下逐組進(jìn)行加密，從而將各個明文分組變換成一個等長的密文分組的密碼。其中二進(jìn)制明文分組的長度稱為該分組密碼的分組規(guī)模.m1m2m3mnc1c2c3cn3實現(xiàn)原則:(1)必須實現(xiàn)起來比較簡單,知道密鑰時加密和脫密都十分容易,適合硬件和(或)軟件實現(xiàn).

(2)加脫密速度和所消耗的資源和成本較低,能滿足具體應(yīng)用范圍的需要.

例:對高速通信數(shù)據(jù)的加密----硬件實現(xiàn);嵌入到系統(tǒng)軟件的加密程序----軟件實現(xiàn);智能卡內(nèi)數(shù)據(jù)的加密----低成本實現(xiàn)4安全性設(shè)計原則1.混亂原則(又稱混淆原則)(Confusion)

混亂原則就是將密文、明文、密鑰三者之間的統(tǒng)計關(guān)系和代數(shù)關(guān)系變得盡可能復(fù)雜，使得敵手即使獲得了密文和明文，也無法求出密鑰的任何信息；即使獲得了密文和明文的統(tǒng)計規(guī)律，也無法求出明文的新的信息。

可進(jìn)一步理解為：（1）明文不能由已知的明文，密文及少許密鑰比特代數(shù)地或統(tǒng)計地表示出來。（2）密鑰不能由已知的明文，密文及少許密鑰比特代數(shù)地或統(tǒng)計地表示出來。52.擴散原則(Diffusion)

擴散原則就是應(yīng)將明文的統(tǒng)計規(guī)律和結(jié)構(gòu)規(guī)律散射到相當(dāng)長的一段統(tǒng)計中去(Shannon的原話)。

也就是說讓明文中的每一位影響密文中的盡可能多的位，或者說讓密文中的每一位都受到明文中的盡可能多位的影響。如果當(dāng)明文變化一個比特時,密文有某些比特不可能發(fā)生變化,則這個明文就與那些密文無關(guān),因而在攻擊這個明文比比特時就可不利用那些密文比特.6分組密碼的設(shè)計方法采用乘積密碼：即通過將一個弱的密碼函數(shù)迭代若干次，產(chǎn)生一個強的密碼函數(shù)，使明文和密鑰得到必要的混亂和擴散。在設(shè)計迭代函數(shù)時，充分利用代替密碼和移位密碼各自的優(yōu)點，抵消各自的缺點，從而通過多次迭代，形成一個強的分組密碼算法。7§4.2

DES分組密碼算法(DateEncipherStandard)一、背景簡介該算法是在美國NSA（國家安全局）資助下由IBM公司開發(fā)的密碼算法，其初衷是為政府非機密的敏感信息提供較強的加密保護。它是美國政府擔(dān)保的第一種加密算法，并在1977年被正式作為美國聯(lián)邦信息處理標(biāo)準(zhǔn)。DES主要提供非軍事性質(zhì)的聯(lián)邦政府機構(gòu)和私營部門使用，并迅速成為名聲最大，使用最廣的商用密碼算法。8背景發(fā)明人：美國IBM公司W(wǎng).Tuchman和C.Meyer1971-1972年研制成功基礎(chǔ)：1967年美國HorstFeistel提出的理論產(chǎn)生：美國國家標(biāo)準(zhǔn)局（NBS)1973年5月到1974年8月兩次發(fā)布通告，公開征求用于電子計算機的加密算法。經(jīng)評選從一大批算法中采納了IBM的LUCIFER方案標(biāo)準(zhǔn)化：DES算法1975年3月公開發(fā)表，1977年1月15日由美國國家標(biāo)準(zhǔn)局頒布為數(shù)據(jù)加密標(biāo)準(zhǔn)（DataEncryptionStandard），于

1977年7月15日生效9背景美國國家安全局（NSA,NationalSecurityAgency)參與了美國國家標(biāo)準(zhǔn)局制定數(shù)據(jù)加密標(biāo)準(zhǔn)的過程。NBS接受了NSA的某些建議，對算法做了修改，并將密鑰長度從LUCIFER方案中的128位壓縮到56位1979年，美國銀行協(xié)會批準(zhǔn)使用DES1980年，DES成為美國標(biāo)準(zhǔn)化協(xié)會(ANSI)標(biāo)準(zhǔn)1984年2月，ISO成立的數(shù)據(jù)加密技術(shù)委員會(SC20)在DES基礎(chǔ)上制定數(shù)據(jù)加密的國際標(biāo)準(zhǔn)工作10DES首次被批準(zhǔn)使用五年，并規(guī)定每隔五年由美國國家保密局作出評估，并重新批準(zhǔn)它是否繼續(xù)作為聯(lián)邦加密標(biāo)準(zhǔn)。最近的一次評估是在1994年1月，美國已決定1998年12月以后將不再使用DES。因為按照現(xiàn)有的技術(shù)水平，采用不到幾十萬美元的設(shè)備，就可破開DES密碼體制。目前的新標(biāo)準(zhǔn)是AES，它是由比利時的密碼學(xué)家JoanDaemen和VincentRijmen設(shè)計的分組密碼—Rijndael（榮代爾）。11§1

DES分組密碼算法

二、算法概述（一）基本參數(shù)

分組加密算法：明文和密文為64位分組長度對稱算法：加密和解密除密鑰編排不同外，使用同一算法密鑰長度：有效密鑰56位，但每個第8位為奇偶校驗位，可忽略密鑰可為任意的56位數(shù)，但存在弱密鑰，容易避開采用混亂和擴散的組合，每個組合先替代后置換，共16輪只使用了標(biāo)準(zhǔn)的算術(shù)和邏輯運算，易于實現(xiàn)12輸入64比特明文數(shù)據(jù)初始置換IP在密鑰控制下16輪迭代初始逆置換IP-1輸出64比特密文數(shù)據(jù)DES加密過程13加密框圖14置換定義4.1

：設(shè)S是一個有限集合，φ是從S到S的一個映射。如果對任意的u，v，當(dāng)u≠v時，φ(u)≠φ(v),則稱φ是S上的一個置換。15初始置換與逆初始置換

輸入和輸出比特的序號從左向右編排為1,2,3,…,64含義:輸出的第1比特是輸入的第58比特,該表示方法實現(xiàn)方便.16IP和IP-1IPIP—117（二）加密算法

Li（32位）Ri（32位）Li-1（32位）Ri-1（32位）fDES的第i圈加密結(jié)構(gòu)圖Ki18DES加密算法的圈函數(shù)----屬于Feistel模型:

Li（32位）Ri（32位）Li-1（32位）Ri-1（32位）fDES的圈函數(shù)的結(jié)構(gòu)它等價于兩個對合變換:Ki19注意無論f函數(shù)如何選取，DES的圈函數(shù)是一個對合變換。20DES的F

函數(shù)12321①E盒擴展

擴展變換的作用是將輸入的32比特數(shù)據(jù)擴展為48比特數(shù)據(jù)擴展22①E盒擴展

擴展方式:

(1)將輸入的32比特每4比特為一組分為8塊;(2)分別將第m-1塊的最右比特和第m+1塊的最左比特添到第m塊的左邊和右邊,形成輸出的第k個6比特塊.

主要原因:硬件實現(xiàn)簡單23DES的F

函數(shù)1224壓縮替代S-盒－48位壓縮到32位123456……………………4344454647481234……………………2930313225②S盒行和列的序號從0起算。26②S-盒的構(gòu)造27S-盒的構(gòu)造要求S-盒是算法的唯一非線性部件,因此,它的密碼強度決定了整個算法的安全強度提供了密碼算法所必須的混亂作用非線性度、差分均勻性、嚴(yán)格雪崩準(zhǔn)則、可逆性、沒有陷門28DES的F

函數(shù)12329③P盒置換將S-盒變換后的32比特數(shù)據(jù)再進(jìn)行P盒置換，置換后得到的32比特即為f函數(shù)的輸出。含義:P盒輸出的第1個元是輸入的第16個元?；咎攸c：

（1）P盒的各輸出塊的4個比特都來自不同的輸入塊；

（2）P盒的各輸入塊的4個比特都分配到不同的輸出塊之中；

（3）P盒的第t輸出塊的4個比特都不來自第t輸入塊。30

例:利用DES算法和全0密鑰對輸入1000000119600000進(jìn)行1圈加密的結(jié)果。

（1）輸入的右半部分是19600000=00011001011000000000000000000000（2）經(jīng)E盒擴展后變?yōu)?00011110011

101100

000000

000000

000000

000000

（3）與全0子密鑰模2加后變?yōu)?00011110010

101100

000000

000000

000000

000000

（4）查S盒后的32比特輸出為f8372c4d11111000001101110010

110001001101（5）經(jīng)P盒后得F函數(shù)的32比特輸出:9cd89aa7=

10011100110110001001101010100111（6）將F函數(shù)的輸入放到左邊,將F函數(shù)的輸出與圈函數(shù)的左半輸入模2加后放到右邊,的圈函數(shù)的64比特輸出為

196000008cd89aa6

31DES中的子密鑰的生成32置換選擇1：從64比特密鑰中取出56個有效比特。置換選擇2：從56個密鑰比特中取出48個作為子密鑰33移位次數(shù)意想不到的效果：子密鑰寄存器的內(nèi)容經(jīng)16次迭代后又回到原來的設(shè)置。34（三）脫密算法

脫密結(jié)構(gòu)與加密結(jié)構(gòu)完全相同，只不過是所使用的子密鑰的順序正好相反!

加密子密鑰：

脫密子密鑰：35DES的加密和脫密變換加密：y=IP-1。fek16。D。…。D。fek2。D。fek1。IP(x)脫密x=IP-1。fdk16。D。…。D。fdk2。D。fdk1。IP(y)注意(1)加密密鑰eki和脫密密鑰dki的關(guān)系：

dki=ek(16-i)(2)最后一圈若添加交換則無法正常脫密：y=IP-。D

。fek16。D。…。D。fek2。D。fek1。IP(x)x=IP-。fdk16。D?！。fdk2。D。fdk1。D

。IP(y)36DES分組密碼算法小結(jié)(3)基本參數(shù)●分組長度：64比特●密鑰長度：64比特●有效密鑰長度：56比特●迭代圈數(shù)：16圈●每圈子密鑰長度：48比特

(4)編碼環(huán)節(jié)●6進(jìn)4出的S盒變換●逐位模2加變換●比特移位變換P盒(1)密碼模型●Feistel模型(2)F函數(shù)模型●S----P網(wǎng)絡(luò)實現(xiàn)性能:軟件實現(xiàn)慢、硬件實現(xiàn)塊；可全部用布爾電路實現(xiàn)●比特擴展變換E盒●比特抽取變換PC1、PC2和IP37S盒的設(shè)計準(zhǔn)則

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

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

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

Li=Ri-1

Ri

=Li-1

f(Ri-1,Ki)

式中，Ki是第i輪用的子密鑰，f是任意密碼輪函數(shù)。稱這種分組密碼算法為Feistel網(wǎng)絡(luò)（FeistelNetwork），它保證加密和解密可采用同一算法實施40迭代分組密碼若以一個簡單函數(shù)f，進(jìn)行多次迭代，就稱其為迭代密碼。每次迭代稱作一輪(Round)。相應(yīng)函數(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)=y41對合密碼(InvolutionCipher)

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

F2n的映射。其中，n是分組長，t是密鑰長。若對每個密鑰取值都有f[f(x,k)，k]=x，即f(x,k)2=I(恒等置換)則稱其為對合密碼，以fI表示。42I型迭代分組密碼以對合密碼函數(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)，則加密的變換等價于恒等變換，在實用中需要避免這類密鑰選擇。43

對合置換和II型迭代分組密碼對合置換

令P是對x的置換，即P：F2n

F2n

，若對所有x

GF(2n)，有P[P[x]]=x，即PP=I(恒等置換)，以PI表示。II型迭代分組密碼

每輪采用對合密碼函數(shù)和對合置換級連，即F[x,k]＝PI[fI[x,k]]

并選解密子密鑰與加密子密鑰逆序，則加密解密可用同一器件完成。DES、FEAL和LOKI等都屬此類。44

III型迭代分組密碼群密碼：若密鑰與明文、密文取自同一空間GF(2n)，且y=x

k式中，

是群運算，則稱其為群密碼。顯然x可通過k的逆元求得x=y

k-1令x

k為一群密碼，令fI(x,kB)為一對合密碼，以F[x,k]＝fI

(x

kA,kB)為迭代函數(shù)，可以III型多輪迭代分組密碼。在最后一輪中，另外加了一次群密碼運算，用以保證整個加、解密的對合性。45III型迭代分組密碼

輪函數(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

46IV型迭代分組密碼

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

F[x,k]＝PI[fI[x

kA,kB]]47

IV型迭代分組密碼

輪函數(shù)Fy(1)y(r-1)

F

x

fI

PI···

fI

PIPI

y

kA(1)kB(1)

kA(r)

kB(r)

kA(r+1)(a)加密

FF

y

fI

PI

···

fI

x

(b)解密

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

PI[kA(r)]-1

PI[kA(2)]-1

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

48窮舉攻擊分析

窮舉攻擊就是對所有可能的密鑰逐個進(jìn)行脫密測試,直到找到正確密鑰為止的一種攻擊方法.窮舉攻擊判斷正確密鑰的方法：將利用試驗密鑰脫密得到的可能明文與已掌握的明文的信息相比較，并將最吻合的那個試驗密鑰作為算法輸出的正確密鑰。

窮舉攻擊又稱為窮盡攻擊、強力攻擊、蠻干攻擊等。只要明文不是隨機的，就可實施窮舉攻擊。49窮舉攻擊的算法

已知條件：已知密文c及對應(yīng)的明文m.

Step1

對每個可能密鑰k,計算c’=D(k,m),并判斷c’=c是否成立.不成立時返回Step1檢驗下一個可能密鑰,成立時將k作為候選密鑰,并執(zhí)行Step2.

Step2

利用其它條件對作k進(jìn)一步確認(rèn).確認(rèn)通過時輸出,算法終止.否則返回Step1檢