基于DES加密算法的改進研究

張 旭，洪家平

(湖北師范大學 計算機與信息工程學院，湖北 黃石 435002)

1 密碼學概述

密碼學自古以來就一直在被人研究著，如今的加密算法都以Shannon的混淆和擴散兩個思想為基礎，混淆以達到模糊明文、密文及其之間的關系，而擴散則是將明文和密鑰的影響盡可能地反映在密文之中。密碼學不僅僅是用于保護消息的機密性，還可以保護消息的完整性和真實性，除此之外在鑒別、認證、簽名等方面都有長足的應用。

現今網絡的使用已經十分普遍，規模也在不斷增大，隨之也帶來了相關的安全性問題，譬如說隱私的泄漏，商業機密的竊聽，甚至是消息的篡改等。因此，對在網絡環境下數據通信及數據加密技術進行全面的分析具有普遍的現實意義[1]。同時，隨著電子技術不斷更迭，集成電路規模不斷發展，相較于傳統的電路，高集成度的嵌入式系統在越來越多的設備上得到應用。在嵌入式系統中，同樣也需要對一些機密數據進行加密，以防止數據在通信過程中被竊取[2]。因此密碼學無論在嵌入式設備還是在網絡空間的領域中都有著非常廣泛的應用，對于保護嵌入式設備的正常工作，建立安全可靠的通信環境都有著舉足輕重的作用。同樣對云端文件的防護，安全地網上購物等也需要安全可靠的保護手段，如在電子商務中應用 ssl、set等安全協議、數字證書、數字簽名等多項數據加密技術，都能夠實現對交易雙方信息的有效保護[3]。

現在的加密技術可以簡單分為兩種類型[4]，一種是分組加密算法，這種算法將消息分成若干個分組，并對其每個分組進行加密運算，最后將每組的密文拼湊在一起作為整個消息的密文。另一種是序列密碼，使用偽隨機發生器產生與明文等長的密鑰加密明文得到密文。在分組加密算法之中，還細分為對稱加密算法和公鑰加密算法。對稱加密算法的加密和解密都使用同一個密鑰，而公鑰加密算法使用公開的密鑰對消息進行加密，用私密的密鑰進行解密。

2 DES加密算法介紹

對于分組加密算法而言，數據加密標準DES(Data Encryption Standard)是這種算法的典型代表[5]。DES加密算法其明文分組為64位，密鑰64位，經過16輪的運算后輸出密文[6]。DES加密算法的密鑰共有64位，每個字節的最后一位為奇偶校驗位。首先將密鑰中的奇偶校驗位去除[7]，形成56位的初始密鑰K1.之后每輪都將初始密鑰K1拆分為兩部分，對左半部分和右半部分分別進行移位，將移位后的左半部分和右半部分結合在一起形成新一輪的初始密鑰K2，將新一輪的初始密鑰K2進行壓縮置換后得到該輪的子密鑰k1，依次不斷迭代16輪產生16個子密鑰k.由于DES的對稱性，解密的算法和加密算法共同使用同一個算法，唯一需要改變的地方是子密鑰k的使用順序與加密算法中使用子密鑰k的順序相反。

很多年的實際應用證明了DES加密算法非常優秀，但卻或多或少依然存在著不足。眾多專家學者都對其進行了不懈的研究，包括對DES中密鑰的探索，對S盒的改進等，并以此為基礎產生了許多改進的DES加密算法。例如GDES加密算法拓展了DES中采用的Feistel結構，snDES加密算法對DES所使用的S盒進行了探索。同時也進一步研究了對DES及其相關加密算法的攻擊方式，產生了如差分攻擊、線性攻擊、中間相遇攻擊等其他攻擊方法。隨著計算機性能不斷提升，對于DES加密算法，主要的問題還是密鑰長度不足，實際使用中只有56位密鑰的DES加密算法已經禁不起窮舉法的攻擊。

為了克服傳統DES加密算法的缺點，Wang Yihan和Li Yongzhen所提出的《Improved Design of DES Algorithm Based on Symmetric Encryption Algorithm》一文[8]，在該文中，將密鑰與明文分組長度拓展到128位。該算法每輪將Lli-1與Lri-1加密后得到的Lli與Lri交換，分別作為下一輪的Lri-1與Lli-1，重復16輪相同的操作后將所得的各個部分合并為一個密文分組，具體流程如圖1所示。該算法擴展了DES的密鑰位數使得窮舉攻擊變得更加困難，增強了算法的安全性，但與DES相比卻失去了對合性。

圖1 Improved Design of DES Algorithm算法流程圖

3 優化改進的DES加密算法

3.1 DES加密算法一般改進方案

上面介紹的Wang Yihan和Li Yongzhen所提出的改進算法，不足之處在于其不是對合運算，解密的算法需要重新編寫。為了解決上述問題，做出了如下改進，主要是對最后一輪的算法進行了改動，如圖2所示。

圖2 一般改進方案中最后一輪算法流程圖

交換運算定義為交換L’li與R’li，則包含最后一輪在內的每一輪迭代則是在傳統的Feistel結構上加上了所定義的交換運算。記上圖中的Ll16為Rr16，Lr16為Rl16，Rl16為Lr16，Rr16為Ll16，則可以得到該方案加密算法結構的一般形式如下：

Lli= Rri-1

Lri= Lli-1⊕f( Lri-1, kli)

Rli= Lri-1

Rri= Rli-1⊕f( Rri-1, kri)

其中i=1，2，…，16.

該方案更具一般性，只需在原有的代碼上稍加改動即可，實現也更加便捷，同時也繼承了對合性，編寫解密算法時只需要交換左右加密子密鑰以及更改使用子密鑰的順序即可，無需更改整體算法結構。

3.2 DES加密算法優化改進方案DESTH分析

上述所介紹的改進方案只適用于具有Feistel結構的加密算法，不適用于有獨特的f函數的DES加密算法。為了能夠擴展DES加密算法的密鑰長度并進一步加強相關的安全性，對上述的改進方案進行更進一步的優化，提出了新的優化改進方案，將該算法命名為DESTH.DESTH加密算法在每輪加密時，左半部分使用Kl產生的子密鑰kli，右半部分使用Kr產生的子密鑰kri.

DESTH算法的1-8輪流程如圖3所示。

圖3 DESTH加密算法結構1～8輪原理圖

在第1輪至第7輪加密中，每一輪均在DES加密算法迭代結束前交換L’li與R’li，在第8輪加密時延用DES加密算法最后一輪的加密方法。

記圖3中第8輪的Ll8為Lr8，Lr8為Rl8，Rl8為Rr8，Rr8為Ll8，則可以得到DESTH加密算法結構第1 - 8輪的一般形式如下：

Lli= Rri-1

Lri= Lli-1⊕f( Lri-1, kli)

Rli= Lri-1

Rri= Rli-1⊕f( Rri-1, kri)

其中i=1，2，…，8.

DESTH算法的9～16輪流程如圖4所示。

圖4 DESTH加密算法結構9～16輪原理圖

在第9輪至第15輪加密中，每一輪則在DES加密算法迭代結束前交換L’ri與R’ri，在最后一輪加密時使用與DES加密算法相同的方案。

記圖4中最后一輪的Ll16為Rr16，Lr16為Ll16，Rl16為Lr16，Rr16為Rl16，則可以得到DESTH加密算法結構第9～16輪的一般形式如下：

Lli= Lri-1

Lri= Rli-1⊕f( Rri-1, kri)

Rli= Rri-1

Rri= Lli-1⊕f( Lri-1, kli)

其中i=9，10，…，16.

則初始的明文數據Ll0和Rl0在1，3，5，7，10，12，14以及16輪進行總計8次的加密操作，初始明文數據Lr0與Rr0在2，4，6，8，9，11，13和15輪進行總計8次的加密操作。

上述的改進算法依然為對合算法，解密算法中的子密鑰使用序列與方案一中一致，僅需逆序使用加密算法中的子密鑰順序即可，不必交換左半部分和右半部分加密的子密鑰。

3.3 DESTH加密算法的實現

DESTH加密算法的實現代碼所使用的部分函數如下所示。

void DESTHEN ( char M[], char K1[], char K2[], int C[]) // DESTH加密主體函數，M為需要加密的明文數據，K1為用于左半部分加密的密鑰，K2為用于右半部分加密的密鑰，C為以二進制形式輸出的加密數據。

{

void PRE ( char string[], char K1[], char K2[], int MLL[], int MLR[], int MRL[], int MRR[],int KL[], int KR[]) ; //準備函數，將輸入的字符串分

為LL0，LR0，RL0和RR0四部分，同時將輸入的密鑰轉換為二進制。密鑰每個字節的二進制表示由低位到高位占據1～7位，并在第8位添加偶校驗碼。

void KREP ( int KD[]) ; //密鑰置換

void KMOVL1 ( int K[]) ; //密鑰向左移動1位，用于產生加密子密鑰

void KMOVL2 ( int K[]) ; //密鑰向左移動2位，用于產生加密子密鑰

void DESTHST1 ( int MLL[], int MLR[], int MRL[], int MRR[], int KL[], int KR[] ) ; // GESTH第1～7輪加密函數

void DESTHST2 ( int MLL[], int MLR[], int MRL[], int MRR[], int KL[], int KR[] ) ; // GESTH第9～15輪加密函數

void DESLAST ( int MLL[] , int MLR[] , int MRL[], int MRR[], int KL[], int KR[] ) ; // DES最后一輪的加密函數，在DESTH算法中用于第8輪與第16輪

}

準備函數中使用void SDOU ( char instr[],int outstr[])函數將temp[i]中的明文轉為二進制存放在對應分組中。

3.4 DES加密算法的對比分析

以下使用DES加密算法與本文所提出的DESTH加密算法對相同的明文進行加密與解密的對比操作，DES的密鑰則取自DESTH密鑰的前半部分。通過分析這兩個不同的加密算法在加密與解密操作中所用時間的長短來比較這兩種加密與解密算法的運行效率。

對明文“It is a program.”使用密鑰“security”通過DES加密的情況如圖5所示。

圖5 DES加密截圖

將上圖5中所得到的密文通過DES解密的情況如圖6所示。

圖6 DES解密截圖

對明文“It is a program.”使用密鑰“security”和“solution”通過DESTH加密的情況如圖7所示。

圖7 改進的DESTH加密截圖

將上圖中所得到的密文通過DESTH解密的情況如圖8所示。

圖8 改進的DESTH解密截圖

由于程序運行時間包括輸入參數的時間，因此沒有實際的參考價值和意義。所以在程序中加入“time.h”頭文件，引入函數clock_t clock(void)測試加密和解密過程所花的實際時間。從上圖中可以得到兩種加密算法的加密耗時均比解密耗時長，這是由于在加密時需要將明文轉換為二進制數進行操作得到密文，而密文以二進制的字符串輸入轉換為二進制速度更快造成的。

通過以上2組運行截圖的對比，由此可以看出，盡管DESTH密鑰由64位擴展到了128位，改進了DES算法上的不足，但是DESTH在加密和解密所花的時間上與DES算法卻并沒有太大的變化。

4 結語

本文在分析DES加密算法和研究Wang Yihan和Li Yongzhen所提出的基礎上，提出了DESTH加密算法，與原有的DES加密算法相比，DESTH加密算法通過擴展加密明文的分組以及加密的密鑰，將64位的密鑰擴展到了128位，同時通過左半部分和右半部分的交互通信進一步加強了算法的安全性，提高了抵抗窮舉攻擊目的的能力。與2DES相比，實現了抵抗中間相遇攻擊的目標。也克服了Wang Yihan和Li Yongzhen提出的不足，該算法還具有對合性，使得解密算法的實現僅需在加密算法的基礎上稍加改動即可，節省了需要存儲解密代碼的空間，也節約了需要實現解密算法電路的空間及其設計實現的過程。