3.2 傳統加密方法（對稱密碼）

傳統加密算法是以密鑰為基礎的，是一種對稱加密，加密密鑰與解密密鑰是相同的，或者可以由其中的一個推知另一個。

在早期的密鑰密碼體制中，典型的有換位密碼和代換密碼。

換位是對明文L長字母組中的字母位置進行重新排列，而每個字母本身并不改變。它很像一種字母游戲，打亂字母的順序，設法把打亂的字母重新組成一個單詞。比如：給定明文hedeterminedtogoatonce，將明文分成長為L=6的段，m1=hedete，m2=rmined，m3=togoat，m4=oncexx，最后一段不足6，加添字母x。將各段的字母序號按下述矩陣進行換位：

得到密文如下：

etehedmenrdioaottgnxeoxc

上面的密文利用下述置換矩陣可恢復為明文：

因此，由加密矩陣可推知解密矩陣。

代換有單表代換和多表代換，此處只介紹單表代換。單表代換是對明文的所有字母用同一代換表映射成密文。比如最典型的凱撒密碼是對英文的26個字母進行位移代換，即將每一字母向前推移k位，不同的k將得到不同的密文。若選擇密鑰k=6，則有下述變換，如表3-1所示。

表3-1 密鑰為6的凱撒密碼映射表

對于明文：she avoided signing the document，經k=6的凱撒密碼變換后得到如下密文：MBY UPICXYX MCAHCHA NBY XIWOGYHN。當然這種映射很容易被破譯。

稍復雜的單表代換可以使明文和密文的映射關系沒什么規律可循，比如字母表中先排列出密鑰字母，然后在密鑰后面填上其他字母。若用ZHANG作為密鑰，則映射關系如表3-2所示。

表3-2 密鑰為ZHANG和映射關系表

但無論是上面哪一種，都相對比較簡單，在今天的電子時代很容易被破譯。現在最常用的對稱加密方案是數據加密標準（DES），雖然它正向公鑰交出半壁江山，但它依然是數據加密中所用的最重要的加密方法。

3.2.1 數據加密標準（DES）

DES是最著名的保密密鑰或對稱密鑰加密算法，它是由IBM公司在20世紀70年代發展起來的，并經美國政府的加密標準篩選后，于1976年11月被美國政府采用。

DES可以分成初始置換、16次迭代過程和逆置換。在迭代過程中，使用56位密鑰對64位的數據塊進行加密，并對64位的數據塊進行16輪編碼。在每輪編碼時，首先將待加密的右半部分由32位擴展為48位，然后與由56位密鑰生成的48位某一密鑰進行異或，得到的結果通過S盒壓縮到32位（上述通過圖3-2中的函數f完成），這32位數據經過置換再與左半部分異或，最后產生新的右半部分。它的整體框圖如圖3-2所示。

圖3-2D ES整體框圖

下面把DES框圖用文字分步來進行一下詳細說明。

1）DES的明文初始置換。把64位明文按初始置換表換位，如表3-3所示。表中給出的為每位二進制數據的下標。

表3-3 初始置換表

2）在初始置換后，把64位二進制明文分成左32位和右32位，進入迭代。

3）把R₀（32）賦給L₁（32）。

4）將右半部分R₀（32）進行擴展排列，由32位擴展為48位。擴展排列下標次序如表3-4所示。

表3-4 擴展排列表

5）生成第一輪的子密鑰，首先把64位密鑰每隔7位刪除1位，即刪除第8、16位等，使之成為56位的密鑰。56位密鑰經過置換選擇1，即生成56位初始子密鑰，置換選擇1如表3-5所示（表中為數據下標）。

表3-5 置換選擇1

6）經過置換選擇1后，把56位的初始密鑰分成左28位和右28位，對左右兩部分分別循環移位LS_i位，各輪移位次數如表3-6所示。然后將兩部分拼合起來。

表3-6 各輪移位次數表

7）拼合后，對56位密鑰用置換選擇2進行置換（置換選擇2如表3-7所示，表中為數據下標），置換后即為本輪子密鑰，本輪子密鑰與經過擴展的數據的右半部分進行異或得到48位數據。

表3-7 置換選擇2

8）得到的48位數據按順序平均分成8組，這8組通過S盒（Substitution Box）變換，把每組的6位輸入變成4位輸出，從而得到32位數據。S盒變換數據如表3-8所示。

表3-8 S盒數據變換表

（續）

S盒的用法：對于8組中的每組S_i，6個輸入端依次為b₁b₂b₃b₄b5b6，求出b1b6合在一起的十進制數并作為行，求出b₂b₃b4b5合在一起表示的十進制數并作為列，在S盒數據表中找出對應的值，即為S_i對應的4位二進制給出的十進制值。

例如：S1的輸入為101110，則b₁b₆=（10）2=（2）10，b2b3b4b5=（0111）2=（7）10。

那么在S₁組中查找第2行第7列，可以得到值（11）10，所以S₁（2，7）=11，（11）10的二進制表示形式為（1011）2，得到S₁的輸出就為4位二進制數1011。

9）S盒輸出的32位數據還要經過Permutation置換，簡稱P置換（P置換如表3-9所示）。P置換后再與左32位按位異或，所得即為新的右半部分。

表3-9 P置換位置表

10）上面只是16次迭代中的一次，經過16次這樣的迭代后，把得到的64位二進制數進行逆初始置換，便得到了64位可輸出的密文。逆置換表如表3-10所示。

表3-10 逆初始置換表

至此才算完成了一次DES加密。

DES的解密過程和加密過程類似，不同的16輪子密鑰的順序是顛倒的，即第一輪用子密鑰16，第二輪用子密鑰15，最后一輪用子密鑰1。這個過程用文字表示比較煩瑣，但為了讓讀者對DES加密過程有更強的感性認識，下面用例子來說明DES加密過程的一部分。

假如給出明文為M=’FOOTBALL’，密鑰為K=’OVERSEAS’，它們的ASCII碼如下：

明文M=（0100011001001111010011110101010001000010010000010100110001001100）2

密鑰K=（0100111101010110010001010101001001010011010001010100000101010011）2

1）明文M按表3-3初始變換后得到：

M_{初始置換后}=1111111100001010110011110010011000000000000000001100011000010111

讀者可觀察表3-3，會很容易發現它的規律，在練習初始變換時，畫一張8×8的表格，把明文的二進制數順序寫入，然后依2、4、6、8、1、3、5、7列的次序把數據依次倒寫即可。

2）把明文分成左32位和右32位后得到：

L₀（32）=11111111000010101100111100100110

R₀（32）=00000000000000001100011000010111

把R₀（32）賦給L₁（32），即L1（32）=R0（32）。

3）把R₀（32）按表3-4擴展為48位：

R₀（48）=100000000000000000000001011000001100000010101110

4）再來看密鑰，把64位的密鑰K刪除第8、16、24、32、40、48、56、64位，變成56位的K’：

K’= 01001110101011010001001010010101001010001001000000101001

5）K’按表3-5置換選擇1進行置換，得到：

K’_{置換選擇1}=00000000111111110000000010011001101100100111000000011010

對于密鑰的變換同樣可以用8×8的表格，把密鑰的64位二進制數依次寫入表格，先刪除最后一列，然后把表格中的數值依1、2、3、4列的次序倒著寫數據，寫到第36位，即第4列的中間，再從最后一列依7、6、5的次序把數據倒著往前寫，最后倒著補上第4列的上面4位。讀者可研究一下表3-5置換選擇1中下標的次序，就會得出規律。

6）把K’_{置換選擇1}分成左28位和右28位：

L₀=0000000011111111000000001001

R₀=1001101100100111000000011010

7）把L₀、R0循環左移LS₁位，通過查表3-6各輪移位次數表可知，LS₁為1，循環左移1位后即有：

L₁=0000000111111110000000010010

R₁=0011011001001110000000110101

8）L₁、R1重新拼合在一起，用置換選擇2進行置換（置換見表3-7置換選擇2），即可得到第一個子密鑰K₁：

K₁=101100000001001001000010111100001000000110000001

9）得到R₀（48）和K₁后，把這兩個48位的數值進行異或后得到：

A=001100000001001001000011100100000100000100101111

10）將上面的A值平均分成8組，再通過查表3-8的S盒數據變換表，得到：

A1=001100，S₁（0，6）=11=（1011）2

A2=000001，S₂（1，0）=3=（0011）2

A3=001001，S₃（1，4）=3=（0011）2

A4=000011，S₄（1，1）=8=（1000）2

A5=100100，S₅（2，2）=1=（0001）2

A6=000100，S₆（0，2）=10=（1010）2

A7=000100，S₇（0，2）=2=（0010）2

A8=101111，S₈（3，7）=13=（1101）2

11）依次合并S₁（0，6）到S₈（3，7），得到以下數據：

B=10110011001110000001101000101101

12）對B值進行Permutation置換，查表3-9的P置換位置表，得到：

X₀=01111100101000000100111001000110

13）L₀（32）與X₀按位異或可以得到：

R₁（32）=10000011101010101000000101100000

令L₂（32）=R₁（32），這樣第一輪迭代就完成了，有了R₁（32）和L₁（32）就可以開始下一輪迭代了，以此類推就可求出R₁₆（32）和L₁₆（32），然后把R16（32）和L16（32）拼合在一起進行逆初始變換就可得到密文。

DES算法具有極高的安全性，到目前為止，除了用窮舉搜索法對DES進行攻擊外，還沒有發現更有效的辦法，即到目前為止還沒有發現DES算法有什么陷門。但隨著計算機速度的提高和價格下降，DES也存在密鑰長度不足、不夠復雜以及密鑰傳遞困難等因素，針對DES存在的問題，人們發展了許多變形DES算法，比如多重DES、S盒可選擇的DES、具有獨立子密鑰的DES和G-DES等。

多重DES是將DES進行級聯，在不同密鑰的作用下連續多次對一組明文進行加密，現在人們建議使用三重DES，并已達成共識。三重DES（TDEA）是將128位的密鑰分成兩個64位的組，用這兩個密鑰對明文進行三次加解密。假設兩個密鑰為K1、K2，首先用密鑰K1對明文進行DES加密，然后用K2對上面加密后的結果進行DES解密，最后再用密鑰K1對解密后的信息進行DES加密。據稱，目前尚無人找到針對此方案的攻擊方法。

S盒可選擇的DES也稱交換S盒的DES算法。它可使S盒的次序隨密鑰而變化或使S盒的內容本身可變。

3.2.2 其他對稱分組密碼

（1）國際數據加密算法IDEA

國際數據加密算法（International Data Encryption Algorithm，IDEA）是賴學家（Xuejia Lai）和梅西（Massey）開發的，在1990年首次成型，稱為PES（建議的加密標準）。次年，設計者對該算法進行了強化并稱之為IPES（改進的建議加密標準）。1992年改名為IDEA，即“國際加密標準”。

IDEA算法的密鑰長度為128位，每次加密一個64位的數據塊。IDEA密碼中使用了3種不同的運算，即逐位異或運算、模2加運算和模2+1乘運算。

IDEA算法由8圈迭代和隨后的一個輸出變換組成。它將64位的數據分成4塊，每個16位，令這4個子塊作為迭代第一輪的輸出，全部共8圈迭代。每圈迭代都是4個子塊彼此間以及16位的子密鑰進行異或、模2加運算、模2+1乘運算。任何一輪迭代，第三和第四子塊互換。

IDEA有大量的弱密鑰，這些弱密鑰是否會威脅它的安全性還是一個謎。

（2）LOKI算法

LOKI算法作為DES的一種潛在替代算法于1990年在密碼學界首次亮相。LOKI和DES一樣以64位二進制分組加密數據，也使用64位密鑰（只是其中無奇偶校驗位），所有64位均為密鑰。LOKI密鑰公布之后，有關專家對其進行了研究破譯并證明不大于14圈的LOKI算法極易受到差分密碼分析等的攻擊。不過，這仍然優于56位密鑰的DES。