基于DES加密算法的改進(jìn)研究

張 旭，洪家平

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

1 密碼學(xué)概述

密碼學(xué)自古以來就一直在被人研究著，如今的加密算法都以Shannon的混淆和擴(kuò)散兩個(gè)思想為基礎(chǔ)，混淆以達(dá)到模糊明文、密文及其之間的關(guān)系，而擴(kuò)散則是將明文和密鑰的影響盡可能地反映在密文之中。密碼學(xué)不僅僅是用于保護(hù)消息的機(jī)密性，還可以保護(hù)消息的完整性和真實(shí)性，除此之外在鑒別、認(rèn)證、簽名等方面都有長(zhǎng)足的應(yīng)用。

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

現(xiàn)在的加密技術(shù)可以簡(jiǎn)單分為兩種類型[4]，一種是分組加密算法，這種算法將消息分成若干個(gè)分組，并對(duì)其每個(gè)分組進(jìn)行加密運(yùn)算，最后將每組的密文拼湊在一起作為整個(gè)消息的密文。另一種是序列密碼，使用偽隨機(jī)發(fā)生器產(chǎn)生與明文等長(zhǎng)的密鑰加密明文得到密文。在分組加密算法之中，還細(xì)分為對(duì)稱加密算法和公鑰加密算法。對(duì)稱加密算法的加密和解密都使用同一個(gè)密鑰，而公鑰加密算法使用公開的密鑰對(duì)消息進(jìn)行加密，用私密的密鑰進(jìn)行解密。

2 DES加密算法介紹

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

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

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

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

3 優(yōu)化改進(jìn)的DES加密算法

3.1 DES加密算法一般改進(jìn)方案

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

圖2 一般改進(jìn)方案中最后一輪算法流程圖

交換運(yùn)算定義為交換L’li與R’li，則包含最后一輪在內(nèi)的每一輪迭代則是在傳統(tǒng)的Feistel結(jié)構(gòu)上加上了所定義的交換運(yùn)算。記上圖中的Ll16為Rr16，Lr16為Rl16，Rl16為L(zhǎng)r16，Rr16為L(zhǎng)l16，則可以得到該方案加密算法結(jié)構(gòu)的一般形式如下：

Lli= Rri-1

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

Rli= Lri-1

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

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

該方案更具一般性，只需在原有的代碼上稍加改動(dòng)即可，實(shí)現(xiàn)也更加便捷，同時(shí)也繼承了對(duì)合性，編寫解密算法時(shí)只需要交換左右加密子密鑰以及更改使用子密鑰的順序即可，無需更改整體算法結(jié)構(gòu)。

3.2 DES加密算法優(yōu)化改進(jìn)方案DESTH分析

上述所介紹的改進(jìn)方案只適用于具有Feistel結(jié)構(gòu)的加密算法，不適用于有獨(dú)特的f函數(shù)的DES加密算法。為了能夠擴(kuò)展DES加密算法的密鑰長(zhǎng)度并進(jìn)一步加強(qiáng)相關(guān)的安全性，對(duì)上述的改進(jìn)方案進(jìn)行更進(jìn)一步的優(yōu)化，提出了新的優(yōu)化改進(jìn)方案，將該算法命名為DESTH.DESTH加密算法在每輪加密時(shí)，左半部分使用Kl產(chǎn)生的子密鑰kli，右半部分使用Kr產(chǎn)生的子密鑰kri.

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

圖3 DESTH加密算法結(jié)構(gòu)1～8輪原理圖

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

記圖3中第8輪的Ll8為L(zhǎng)r8，Lr8為Rl8，Rl8為Rr8，Rr8為L(zhǎng)l8，則可以得到DESTH加密算法結(jié)構(gòu)第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加密算法結(jié)構(gòu)9～16輪原理圖

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

記圖4中最后一輪的Ll16為Rr16，Lr16為L(zhǎng)l16，Rl16為L(zhǎng)r16，Rr16為Rl16，則可以得到DESTH加密算法結(jié)構(gòu)第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.

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

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

3.3 DESTH加密算法的實(shí)現(xiàn)

DESTH加密算法的實(shí)現(xiàn)代碼所使用的部分函數(shù)如下所示。

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

{

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

為L(zhǎng)L0，LR0，RL0和RR0四部分，同時(shí)將輸入的密鑰轉(zhuǎn)換為二進(jìn)制。密鑰每個(gè)字節(jié)的二進(jìn)制表示由低位到高位占據(jù)1～7位，并在第8位添加偶校驗(yàn)碼。

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

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

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

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

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

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

}

準(zhǔn)備函數(shù)中使用void SDOU ( char instr[],int outstr[])函數(shù)將temp[i]中的明文轉(zhuǎn)為二進(jìn)制存放在對(duì)應(yīng)分組中。

3.4 DES加密算法的對(duì)比分析

以下使用DES加密算法與本文所提出的DESTH加密算法對(duì)相同的明文進(jìn)行加密與解密的對(duì)比操作，DES的密鑰則取自DESTH密鑰的前半部分。通過分析這兩個(gè)不同的加密算法在加密與解密操作中所用時(shí)間的長(zhǎng)短來比較這兩種加密與解密算法的運(yùn)行效率。

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

圖5 DES加密截圖

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

圖6 DES解密截圖

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

圖7 改進(jìn)的DESTH加密截圖

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

圖8 改進(jìn)的DESTH解密截圖

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

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

4 結(jié)語(yǔ)

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