第1章 分組密碼

1.1 數(shù)據加密標準和分組密碼的四種工作方式

1.1.1 DES加密算法的研制經過

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

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

1.1.2 DES加密算法

1.DES加密算法的框架

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

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

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

2.f函數(shù)

f函數(shù)是DES加密算法的核心部分（見圖1.1.2），進入第i層時，f函數(shù)的輸入Ri-1（32比特）先經擴張函數(shù)E變成48比特，設Ri-1=r0 r1r2…r31經E擴張后記為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比特按位進行模2加可得B=b0b1…b47。B順序地按6比特分組，分別進入代替表（S盒） S0, S1, …, S7，見表1.1.3。

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

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

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

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

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

DES加密算法可以簡單歸結如下。

加密過程：

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

Li← Ri-1

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

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

DES的加密運算是可逆的，其解密過程與加密過程類似。

解密過程：

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

Ri-1← Li

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

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

這里給出了一個加密過程的例子（用十六進制表示）：

密鑰：03 96 48 C5 39 31 39 65

明文：00 00 00 00 00 00 00 00

經置換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

經過IP-1后的密文：C4 D7 2C 9D EE DE 5E 8B

1.1.3 DES的工作方式

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

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

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

如果明文長度不是64比特的整數(shù)倍，則在明文末尾填補適當數(shù)目的規(guī)定符號。ECB方式對明文分組用給定的密鑰K分別進行加密，可得密文

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

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

（2）密文分組連接（CBC）方式。在CBC方式下，在對每個明文分組 xi加密之前先與前一分組的密文yi-1按位進行模2加后，再進行DES加密，需預置一個初始向量(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方式組間重復的缺點，但由于明文分組的加密與前一分組密文有關，因此前一分組密文的錯誤會傳播到下一分組。

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

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

＜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方式采用密文反饋，因此對密文錯誤（通常由信道傳輸?shù)仍斐桑┍容^敏感，t比特密文中只要有1比特的錯誤，就會導致連續(xù)數(shù)個t比特出錯。

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

由圖1.1.5可看出，OFB方式與CFB方式的不同點只是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方式密文錯誤傳遞的缺點。

1.1.4 DES加密思想和特點

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

DES加密算法采用擴張函數(shù)E實現(xiàn)S盒和P置換，采用S盒進行小塊的非線性變換，以達到混合（Confusion）；采用P置換進行大塊的線性變換，以達到擴散（Diffusion）。因此， S盒的設計是DES加密算法的一個核心問題。實際使用的S盒是經過精心設計和嚴格挑選的，因為S盒的某些設計原則是敏感的，NSA給出了下列三條屬于設計準則。

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

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

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

DES加密算法具有互補性的特點，假設對明文X逐位取補，記為；密鑰逐位取補，記為。若密文組為：

則有

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

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

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

DES加密算法存在6對半弱密鑰。

弱密鑰和半弱密鑰是不安全的，屬于禁用密鑰。當采用隨機途徑生成密鑰時，要檢查并刪除禁用密鑰。