DES算法的一些探討

西安工程技術(技師)學院 郭學功

一、DES加密算法介紹

1.基本思想

DES加密是典型的按分組方式工作的密碼，其基本思想是將二進制序列的明文分成每64比特一組用64比特的密鑰對其進行16輪代換和換位加密，最后形成密文。

2.DES算法的內在特性

(1)密鑰有效長度是56位(第8，16，?，64位為校驗位)，分組明文長度為64位，而且明文、密文與密鑰存在互補關系。

(2)僅用16次循環迭代，使得相同明文會產生相同密文。

(3)存在著很好的并行結構：產生內部密鑰的左移次數存在著準對稱性(即內部密鑰生成過程存在并行性)。DES屬于傳統的Feistel網絡結構，在DES的基本單元中能夠實施并行操作。

(4)DES有16輪加密，如果將第i輪的P置換移至下一輪后會與下一輪的E擴展操作進行合并，簡化算法的基本操作。

(5)可以通過S盒與P置換合并的方法節省P置換的基本操作時間。

二、DES加密算法實現過程

1.加密過程

數據加密標準過程主要包括三部分：一個是密鑰產生部分；一個是換位操作，即初始置換部分和末置換部分；另一個是乘積交換部分。

2.解密過程

解密運算與加密運算一樣，只是所取子密鑰的順序不同。加密時候的順序是K1→K2→Ki→K16，解密時的順序則為K16→K15→Ki→K1。

三、DES加密算法的安全性

通過對DES加、解密過程分析，從技術上講，DES存在的缺陷主要集中在三個方面：

(1)密鑰較短作為分組密碼，DES的加密單位僅有64位二進制，這對于數據傳輸來說太小，因為每個區組僅含8個字符，而且其中某些位還要用于奇偶校驗或其他通訊開銷。密鑰僅有56位二進制未免太短，各次迭代中使用的密鑰K(i)是遞推產生的，這種相關性必然降低了密碼體制的安全性。如果密鑰的長度再長一些，顯然會更加安全。因此，有人認為:在現有的技術條件下用窮舉搜索法來尋找正確密鑰已趨于可行，因此，若要安全保護10年以上的數據最好不用DES算法。

(2)DES存在一些弱密鑰和半弱密鑰。由它們所產生的16個子密鑰是有相重的。弱密鑰和半弱密鑰的存在無疑是DES的一個不足。

(3)除去S盒，DES里的所有計算全是線性的，而且S盒的設計對密碼算法的安全性至關重要。由于DES算法采用美國國家安全局精心設計的8個S-盒和IP-置換，而實現迭代函數Si所用的S-盒的設計原理尚未公開，其中可能留有隱患。更有人擔心DES算法中有“陷門”，知道秘密的人可以很容易地進行密文解密。

根據目前DES算法的使用情況看，采用DES算法仍然具有極高的安全性。

四、DES加密算法的討論

基于DES算法上的缺陷，各國信息安全專家都在研究，在基本不改變DES算法加密強度條件下提出了幾十種增強DES安全性的方法，經過研究比對，常用的有以下7種，具有可行性：

1.多重DES[3]

為了增加密鑰的長度，可采用多重加密技術。將分組密碼進行級聯，在不同的密鑰作用下，連續多次對一組明文進行加密。對DES，專家的共識是使用三重加密DES，可使加密密鑰長度擴展到128位(112位有效)或192位(168位有效)。用三把不同密鑰對數據連續加密三次，構成所謂Tripe-DES。它等價于把DES的鑰匙長度增加到112位。鑰匙長度每增加一位，鑰匙總數就會翻一番，能有效地防止對密鑰的窮盡搜索。當然，加密、解密的運算量也會是DES的3倍。以128位的密鑰為例，其基本原理是將128位的密鑰分為64位的兩組(K1，K2)：

＜1＞用密鑰K1進行DES加密。

＜2＞用K2對步驟＜1＞的結果進行DES解密。

＜3＞用步驟＜2＞的結果使用密鑰K1進行DES加密。

如此對明文數據進行三次普通的DES加解密操作，從而提高了加密強度。據稱，目前尚無人找到針對此方案的攻擊方法。

2.S-盒可變的DES[1]

通過優化S-盒的設計，使S-盒的次序隨密鑰而變化或使S-盒的內容本身是可變的，就可以抵抗破譯時差分密碼分析，以達到進一步增強DES算法加密強度的目的。

在DES算法中S-box是核心。其設計準則是：

＜1＞沒有一個S-box的輸出位是輸入位的線性函數。

＜2＞如果將輸入的兩端固定，中間4位變化，產生的輸出只能得到一次。

＜3＞如果S-box的兩個輸入之間有一位的差異，則輸出中至少兩位不同。

3.具有獨立子密鑰的DES

這種改進是每一輪迭代都使用一個不同的子密鑰，而不是由一個56位二進制的密鑰產生。由于16輪迭代的每一輪使用一個48位二進制的密鑰，所以這種變形的DES密鑰長度是768位。這一方法可以大大地增加窮舉破譯難度，相應增強了DES的加密強度，

4.xDESi

xDESi方案利用DES構造了一族分組密碼，加大了數據分組和密鑰長度。當i=0時，就是DES；

當i＞0時，xDESi:GF(2)56i(2i+1)×GF(2)128i→GF(2)128i，即為采用密鑰長度為56×i×(2i+1)位、組長為128×i位的分組密碼；

當i=1時，它將分組長度加倍，成為密鑰長度增至3倍的三輪方案，它比一般三重加密DES快；

當i≥3時，由于實現復雜而不實用。

5.對DES算法實現方法的改進

DES算法實現時最關鍵的是初始置換表IP、末變換表IP-1及S盒的設計，但出于安全的需要，分組密碼DES的若干換位表都是直接引出，使使用者很難理解，更無法找到其換位規則，下面就通過對它的分析力圖找到DES算法的換位規則和提高其運算效率的實現方法。

IP變換表分析及實現方法的改進

通過對表1分析可以看出，先輸入64比特的一組明文M(64)，編號次序為0，1，2，3，…，63，把M(64)的第2，4，6，8，1，3，5，7列變成第1，2，3，4，5，6，7，8行后再首尾翻轉180°就得到明文M(64)的初始換位表IP(64)。IP-1換位表是將64比特的字符串R16L16的第1，2，3，4，5，6，7，8行變成2，4，6，8，1，3，5，7列后再首尾翻轉180°得到的。找到這個規律有助于程序實現的改進并能夠提高計算速度。軟件設計上，可以用一個表實現兩個表的操作，減少程序的大小；也可以直接用算式代替IP及IP-1變換表，由計算代替查表，可以大大提高計算的速度。

6.S盒實現方法的改進

在進行S盒運算時，設6位輸入為A=a1，a2，a3，a4，a5，a6，記h=a1a6，k=a2a3a4a5，則在Si(i=1，2，...，8)表中第h行，k列所對應的值即為輸出值。由于a1a2a3a4a5a6=a1a6*16+a2a3a4a5，所以在具體軟件實現時，可以將S盒的二維表化為一維表來操作，將在4行，16列的一個二維表中查找對應的值Si(a1a6，a2a3a4a5)變成逐行接續的一維表，直接查找一維表中a1a2a3a4a5a6所對應的值，這樣可以大大提高程序運行速度。進一步將E表第6列變到第2列，PC-2表第6列變到第2列，在查找Si(i=1，2，...，8)表時，只須去查找a1a6行，a2a3a4a5列所對應的值，變成一維表后，直接查找表中a1a2a3a4a5a6所對應的值即可。

通過以上改進，減少了DES算法設計上的難度，同時提高了算法的執行效率。

[1]陳運.信息加密技術[M].電子科技大學出版社,1996.

[2]胡予濮,張玉清,肖國鎮.對稱密碼學[M].北京:機械工業出版社,2002,7.

[3]盧鐵成.信息加密技術[M].四川科學技術出版社,1986.

[4]朱文余,孫琦.計算機密碼應用基礎[M].北京:科學出版社,2000,8.