第1章 分組密碼

1.1 數(shù)據(jù)加密標(biāo)準(zhǔn)和分組密碼的四種工作方式

1.1.1 DES加密算法的研制經(jīng)過(guò)

DES（Data Encryption Standard）加密算法的研究歷經(jīng)6年的時(shí)間（1968年—1974年）。20世紀(jì)60年代末，IBM公司的一個(gè)研究組在菲斯特（Feistel）的帶領(lǐng)下研制出了Lucifer密碼。1971年，IBM公司請(qǐng)塔其曼（Tuchman）和邁耶（Meyer）在Lucifer密碼的基礎(chǔ)上進(jìn)一步做研究，以增加密碼強(qiáng)度。他們經(jīng)過(guò)3年多的研究，試圖破解Lucifer密碼，通過(guò)搜索強(qiáng)有力的代替置換網(wǎng)絡(luò)和密鑰編制函數(shù)，完成了DES加密算法的設(shè)計(jì)和編制工作。

1976年年底，DES加密算法被采納為聯(lián)邦標(biāo)準(zhǔn)，自1977年7月15日起正式生效。1986年，NSA宣布停止執(zhí)行DES計(jì)劃。從1988年1月1日起，除了電子資金過(guò)戶（Electronic Fund Transfer），不再批準(zhǔn)政府部門使用采用DES加密算法的產(chǎn)品，但已批準(zhǔn)的產(chǎn)品可繼續(xù)銷售和使用。美國(guó)安全局（National Security Agency, NSA）感到DES加密算法的廣泛使用已使之成為眾矢之的。

1.1.2 DES加密算法

1.DES加密算法的框架

DES加密算法如圖1.1.1所示。輸入明文塊M0（64比特）, M0=m0m1…m63，經(jīng)初始置換IP（見(jiàn)表1.1.1）換位成M0=m57m49…m6。

將M0分成左右兩個(gè)半塊（32比特）, M0=(L0, R0), (L0, R0)經(jīng)過(guò)第1層變換后記為(L1, R1)，其中，L1=R0, R1=L0⊕f(R0, K1)。

經(jīng)過(guò)第 i（i=1,2, …,16）層變換后記為(Li, Ri)。其中，Li=Ri-1, Ri=Li-1⊕f(Ri-1, Ki)，此處的f函數(shù)將在下面詳述，Ki為密鑰，經(jīng)過(guò)16層變換后，預(yù)輸出為(R16, L16)，再經(jīng)IP-1置換成密文塊C。

2.f函數(shù)

f函數(shù)是DES加密算法的核心部分（見(jiàn)圖1.1.2），進(jìn)入第i層時(shí)，f函數(shù)的輸入Ri-1（32比特）先經(jīng)擴(kuò)張函數(shù)E變成48比特，設(shè)Ri-1=r0 r1r2…r31經(jīng)E擴(kuò)張后記為Ti-1=E(Ri-1)。

Ti-1=t0 t1 t 2…t 47

參考表1.1.2的比特選擇表和置換表，其中t 0=r 31, t 1=r0, t2=r 1, …, t 46=r 31, t47=r 0。Ti-1與Ki的48比特按位進(jìn)行模2加可得B=b0b1…b47。B順序地按6比特分組，分別進(jìn)入代替表（S盒） S0, S1, …, S7，見(jiàn)表1.1.3。

代替的規(guī)則如下：輸入Si的6比特的左端1比特和右端1比特組成二進(jìn)制數(shù)0～3中的某個(gè)數(shù)，作為取Si的行數(shù)；中間4比特組成二進(jìn)制數(shù)0～15中的某個(gè)數(shù)，作為取Si的列數(shù)；在Si表行列交叉處取得一個(gè)數(shù)，用4比特表示作為Si盒的輸出。例如，若輸入S0盒的6比特為“011011”，則行數(shù)為“01”，列數(shù)為“1101”，即13。S0的第1行第13列的元素為5，于是輸出為“0101”，如下所示。

經(jīng)過(guò)S盒后的32比特再經(jīng)過(guò)置換表可改變比特位置，結(jié)果作為f函數(shù)的輸出。

3．子密鑰發(fā)生器

64比特的初始密鑰K通過(guò)子密鑰發(fā)生器變成K1, K2, …, K16，分別作為1到16層的f函數(shù)子密鑰（48比特）。

在64比特的初始密鑰K中，除去8比特（第7、15、23、31、39、47、55、63比特作為校驗(yàn)位），其余56比特送入置換PC I，經(jīng)過(guò)坐標(biāo)置換后分成兩組，每組28比特，分別送入C寄存器和D寄存器中。在各次迭代中，C和D寄存器分別將存儲(chǔ)的數(shù)按移位次數(shù)表進(jìn)行循環(huán)左移。每次移位后將C和D寄存器的第6、9、14、25比特除去，其余比特經(jīng)置換后PC II送出48比特，作為第i次迭代時(shí)所用的子密鑰Ki。子密鑰發(fā)生器如圖1.1.3所示。

DES加密算法可以簡(jiǎn)單歸結(jié)如下。

加密過(guò)程：

L0, R0←IP（64比特輸入）

Li← Ri-1

Ri←Li-1⊕f(Li, …, Ki), i=1,2, …,16

（64比特密文）← IP-1(R16L16)

DES的加密運(yùn)算是可逆的，其解密過(guò)程與加密過(guò)程類似。

解密過(guò)程：

R16, L16←IP（＜64比特密文＞）

Ri-1← Li

Li-1←Ri⊕f(Ri-1, Ki), i=16,15, …,1

＜64比特明文＞ ← IP-1(L0R0)

這里給出了一個(gè)加密過(guò)程的例子（用十六進(jìn)制表示）：

密鑰：03 96 48 C5 39 31 39 65

明文：00 00 00 00 00 00 00 00

經(jīng)置換IPRG: 00 00 00 00 00 00 00 00

第1層：00 00 00 00 85 7E 2A 43

第2層：85 7E 2A 43 D7 2F 0D 7B

第3層：D7 2F 0D 7B C7 6E 6C B1

第4層：C7 6E 6C B1 4C B0 77 8A

第5層：4C B0 77 8A 72 2B BC 81

第6層：72 2B BC 81 59 85 72 7B

第7層：59 85 72 7B 82 67 AE 9C

第8層：82 67 AE 9C E7 DD DB 94

第9層：E7 DD DB 94 71 90 0F 11

第10層：71 90 0F 11 0A AD 33 E4

第11層：0A AD 33 E4 51 61 B2 81

第12層：51 61 B2 81 7D DD 4A 9E

第13層：7D DD 4A 9E 75 17 39 28

第14層：75 17 39 28 9D A0 1E 4E

第15層：9D A0 1E 4E BB 14 FC F2

第16層：73 6A 7F 8A BB 14 FC F2

經(jīng)過(guò)IP-1后的密文：C4 D7 2C 9D EE DE 5E 8B

1.1.3 DES的工作方式

DES的工作方式也適用于其他分組密碼。

（1）電子密本（ECB）方式。將明文＜X＞分成m個(gè)64比特分組，即

＜X＞=(x0, x1, …, xm-1)

如果明文長(zhǎng)度不是64比特的整數(shù)倍，則在明文末尾填補(bǔ)適當(dāng)數(shù)目的規(guī)定符號(hào)。ECB方式對(duì)明文分組用給定的密鑰K分別進(jìn)行加密，可得密文

＜Y＞=(y0, y1, …, ym-1)

式中，yi=DES(K, xi), i=0,1, …, m-1。這種工作方式組間同明即同密，組間可能出現(xiàn)重復(fù)。

（2）密文分組連接（CBC）方式。在CBC方式下，在對(duì)每個(gè)明文分組 xi加密之前先與前一分組的密文yi-1按位進(jìn)行模2加后，再進(jìn)行DES加密，需預(yù)置一個(gè)初始向量(IV)y-1=IV。

CBC方式：

＜X＞ → ＜Y＞, ＜Y＞=CBC(k, ＜X＞)

y-1=IV

yj=DES(K, xj⊕yj-1), 0≤j≤m

脫密CBC-1：

＜Y＞ → ＜X＞

y-1=IV

xj=DES-1(K, yj)⊕yj-1

CBC方式克服了ECB方式組間重復(fù)的缺點(diǎn)，但由于明文分組的加密與前一分組密文有關(guān)，因此前一分組密文的錯(cuò)誤會(huì)傳播到下一分組。

（3）密文反饋（CFB）方式（可用于序列密碼）。設(shè)明文為＜X＞=(x0, x1, …, xm-1)，其中 xi由t比特組成，0＜t≤64。

由圖1.1.4可知，CFB方式實(shí)際上將DES作為一個(gè)密鑰流發(fā)生器，在t比特密文的反饋下，每次輸出t比特亂數(shù)來(lái)對(duì)t比特明文進(jìn)行加密，即：

＜X＞ → ＜Y＞

yi=leftt[DES(k, Zi)]⊕xi

或

yi=rightt[DES(k, Zi)]⊕xi

式中，Z0=IV（初始向量為64比特）。

Zi=right64[Zi-1‖yi-1], 1≤i＜m-1

式中，“‖”表示相接，leftt[·]表示取左邊的t比特，rightt[·]表示取右邊的t比特。

由于CFB方式采用密文反饋，因此對(duì)密文錯(cuò)誤（通常由信道傳輸?shù)仍斐桑┍容^敏感，t比特密文中只要有1比特的錯(cuò)誤，就會(huì)導(dǎo)致連續(xù)數(shù)個(gè)t比特出錯(cuò)。

（4）輸出反饋（OFB）方式（可用于序列密碼）。

由圖1.1.5可看出，OFB方式與CFB方式的不同點(diǎn)只是OFB方式直接取DES加密算法輸出的t比特作為反饋（而CBF方式以密文yi作為反饋），其余都與CFB方式相同。

＜X＞ → ＜Y＞

yi=leftt[DES(k, Zi)]⊕xi

或

yi=rightt[DES(k, Zi)]⊕xi

Z0=IV（初始向量為64比特）

Zi=right64{Zi-1‖left t[DES(k, Zi-1)]}

或

Zi=right64[Zi-1‖rightt[DES(k, Zi-1)]]

OFB方式以DES加密算法的輸出作為反饋，因而克服了CFB方式密文錯(cuò)誤傳遞的缺點(diǎn)。

1.1.4 DES加密思想和特點(diǎn)

香農(nóng)（Shannon）曾建議使用不同類型的函數(shù)（如反復(fù)、交替地進(jìn)行代替和簡(jiǎn)單的線性變換）來(lái)構(gòu)成一個(gè)混攪變換（Mixing Transformation），通過(guò)這種變換可以把明文消息隨機(jī)、均勻地分布在所有可能的密文消息集合上。DES加密算法每層的f函數(shù)包含加亂（⊕Ki）、代替（S盒）、移位（置換P），也就是反復(fù)、交替地使用這些變換使輸出的每個(gè)比特都依賴于整個(gè)輸入組，使加密的每個(gè)比特都依賴于整個(gè)密鑰，即通過(guò)多層的反復(fù)變換，使密文的每個(gè)比特都是明文和密鑰的完全函數(shù)。

DES加密算法采用擴(kuò)張函數(shù)E實(shí)現(xiàn)S盒和P置換，采用S盒進(jìn)行小塊的非線性變換，以達(dá)到混合（Confusion）；采用P置換進(jìn)行大塊的線性變換，以達(dá)到擴(kuò)散（Diffusion）。因此， S盒的設(shè)計(jì)是DES加密算法的一個(gè)核心問(wèn)題。實(shí)際使用的S盒是經(jīng)過(guò)精心設(shè)計(jì)和嚴(yán)格挑選的，因?yàn)?span id="qbco4su" class="italic">S盒的某些設(shè)計(jì)原則是敏感的，NSA給出了下列三條屬于設(shè)計(jì)準(zhǔn)則。

① S盒的輸出不是輸入的線性函數(shù)或仿射函數(shù)。

② 改變S盒的1個(gè)輸入比特，就至少可引起S盒的2個(gè)輸出比特不同。

③ S(X)與S(X+001100)至少有2個(gè)比特不同。

DES加密算法具有互補(bǔ)性的特點(diǎn)，假設(shè)對(duì)明文X逐位取補(bǔ)，記為；密鑰逐位取補(bǔ)，記為。若密文組為：

則有

式中，是Y的逐位取補(bǔ)。互補(bǔ)性特點(diǎn)是由DES加密算法中的兩次異或運(yùn)算決定的，一次是在S盒之前，另一次是在P置換之后。

DES加密算法存在弱密鑰和半弱密鑰。

DES加密算法每次迭代都有一個(gè)子密鑰供加密使用，16次迭代子密鑰分別為 K1, K2, …, K16，由初始密鑰K生成。如果K通過(guò)子密鑰發(fā)生器生成的K1, K2, …, K16都相同，則稱密鑰K為弱密鑰，DES加密算法存在4個(gè)弱密鑰。如果用初始密鑰K對(duì)明文X進(jìn)行2次加密或2次解密，都可恢復(fù)出明文（即加密運(yùn)算與解密運(yùn)算沒(méi)有區(qū)別），則稱這類密鑰K為半弱密鑰，即

DES加密算法存在6對(duì)半弱密鑰。

弱密鑰和半弱密鑰是不安全的，屬于禁用密鑰。當(dāng)采用隨機(jī)途徑生成密鑰時(shí)，要檢查并刪除禁用密鑰。