DES 加密算法的改進方案*

黃 偉

（廣州科技職業(yè)技術(shù)大學(xué)，廣東 廣州 510550）

0 引 言

數(shù)據(jù)加密算法是由IBM 公司于20 世紀(jì)70年代早期開發(fā)的一種分組加密法，由于其具有數(shù)學(xué)上可證明的安全強度[1]（以擴散模糊和擾亂模糊為特征），易于硬件實現(xiàn)的特點[2]，已逐漸由理論走向?qū)嵺`應(yīng)用，被廣泛應(yīng)用于通信行業(yè)和金融行業(yè)，并在1977 年成為美國政府正式認(rèn)可的數(shù)據(jù)加密標(biāo)準(zhǔn)（Data Encryption Standard，DES）[3]。然而，DES 算法仍未解決所有對稱加密算法共有的缺陷：對稱密鑰的分發(fā)要占用額外的安全信道。同時，隨著計算機計算速度的提升，DES 算法對于窮舉法攻擊的抵抗能力被逐漸削弱。到了互聯(lián)網(wǎng)加密流量爆發(fā)式增長的20 世紀(jì)90 年代，網(wǎng)絡(luò)通信中的主流數(shù)據(jù)加密算法是以RSA 為代表的非對稱加密體系。這種非對稱加密算法具有密鑰易于分配（不占用額外信道）的特點以及強大的抵抗窮舉法攻擊的能力。非對稱加密體系的廣泛應(yīng)用，是技術(shù)進步和對信息安全需求提高所帶來的必然結(jié)果。

如今，對稱加密算法仍然應(yīng)用于通信、經(jīng)濟等眾多領(lǐng)域，并沒有因為科技的發(fā)展而被淘汰。究其原因，是對稱加密和非對稱加密并不是兩種互相對立、互相排斥的密碼體系，它們各有優(yōu)點和缺點，清晰地認(rèn)識到它們的互補性，是構(gòu)造相對完善的密碼體系的關(guān)鍵。公鑰密碼體系雖具有易于分配密鑰和難于被暴力攻擊的優(yōu)點，但這些優(yōu)點是以犧牲效率為代價的。與對稱算法相比，非對稱算法在加密和解密時需要花費更多的時間[4]。這使得非對稱算法在一些需要即時響應(yīng)的應(yīng)用場景中，如邊緣計算，變得不再適用。這說明，要獲得更高的安全強度，同時使算法效率不至于大幅降低，必須把兩種密碼體系有機結(jié)合。

本文選取了在現(xiàn)代密碼算法中具有里程碑意義的對稱加密算法DES 作為研究對象，引入非對稱密碼體系的思想對其進行改進。本文提出的改進算法，除了保留DES 算法原有優(yōu)點，還具備非對稱算法的所有優(yōu)點，是一種適應(yīng)現(xiàn)代網(wǎng)絡(luò)通信的數(shù)據(jù)安全保護的密碼算法。

1 DES 算法

DES 算法是一種分組密碼，明文每64 比特為一組，密鑰為64 比特，除去8 比特奇偶校驗位，實際密鑰為56 比特，因此密鑰組合數(shù)量為 256個。加密時，用同一密鑰依次對每組明文進行加密，得到的每組密文也是64 比特，因此最后得到的密文長度和明文長度一致。對每組等長明文加密時，密鑰不變，算法也不變，因此DES 十分適合以嵌入式硬件實現(xiàn)[5]。DES 加密前先把明文用一個置換函數(shù)IP 映射為初始密文。DES 加密算法由16 輪迭代加密構(gòu)成，每次迭代加密所用密鑰由原始密鑰循環(huán)左移得到，稱為子密鑰K[6]。每輪迭代前，把上一輪迭代得到的密文（如果是第一輪迭代，加密對象是初始密文）分為左半L（第1~32 位）和右半R（第33~64 位）。R被當(dāng)前子密鑰加密為f(R,K)，f為加密函數(shù)。f(R,K)和L異或運算后得到下一輪迭代的右半R'。下一輪迭代的左半L'由R賦值，和R完全一致。16 輪迭代完成后得到的密文，經(jīng)過一個置換函數(shù)IP?1映射后得到最終密文。解密算法和加密算法一致，密鑰也一致，但每輪迭代所使用的子密鑰的順序和加密時相反。

經(jīng)過16 輪迭代的DES 算法已被證明具有充分的對抗統(tǒng)計分析和線性分析的能力。因此，破解16 輪迭代的DES 密文的唯一途徑是暴力破解，即用窮舉法嘗試所有的 256個可能的密鑰[7]，這在DES 算法剛提出時被認(rèn)為是不可能完成的任務(wù)。但隨著計算機運算速度的提高和并行計算技術(shù)的成熟，DES 的安全度被大大弱化。

2 DES 算法的改進方案

對DES 算法的改進原則是使用RSA 保護DES 密鑰，同時在加密前，對明文增加亂序和干擾處理。

2.1 改進方案的總體設(shè)計

DES 算法的密鑰是對稱密鑰，必須通過秘密信道傳送。為了使其也能通過互聯(lián)網(wǎng)等公開信道傳送，必須使用公鑰密碼體系對其進行保護。最常用的公鑰密碼算法是RSA，因此，我們可以把DES 密鑰“封裝”在一個RSA 加密的“頭部”（Header）里，然后把這個頭部附加在DES 密文前，成為一個密文包（Encrypted Data Packet），再把這個密文包發(fā)送給接收方?！胺庋b”主要是指用接收方的公鑰加密DES 密鑰。接收方收到密文包后，先以自己的私鑰解密包頭，取出DES 密鑰后，再用其解密密文包的數(shù)據(jù)部分（即DES 密文），得到明文。

如果頭部封裝的信息僅僅是DES 密鑰，抗攻擊意義并不大，僅解決了密鑰通過公共信道分發(fā)的問題，攻擊者仍然可以用窮舉法對密文包的數(shù)據(jù)部分實施暴力破解。為了增加暴力破解的難度，密文包頭部字段中必須包含一些有助于提高暴力破解難度的信息，并且不能顯著影響密文包頭的RSA 解密效率。主要可以采取以下兩個策略：（1）對明文預(yù)先進行亂序處理，擾亂（Confuse）明文的原來順序；（2）在DES加密前插入無效信息，攻擊者只有在剔除這些無效信息后，才能得到有效的密文分組，并對此分組嘗試暴力破解。

2.2 改進算法詳述

改進算法包括密文包的結(jié)構(gòu)、明文的預(yù)處理和加密流程，以及密文包的頭部結(jié)構(gòu)。

2.2.1 密文包的整體結(jié)構(gòu)

密文包由頭部和密文兩個部分組成。由于頭部是用RSA 加密的密文，因此本文以“RSA 頭”這一名稱指代頭部。明文通過RSA 頭中的密鑰集加密后，生成密文部分。由于無效信息的插入，使密文部分和明文部分的長度不相等，大大增加了破解的難度?！懊荑€集”不僅是DES 密鑰，還包含了加密或解密流程中各階段所使用的密鑰，而DES 加密或解密僅僅是其中一個階段。為方便接收方把頭部分離出來，RSA 頭的長度是固定的，只能用接收方的私鑰解密。

2.2.2 對原始明文的預(yù)處理

加密前需要對原始明文P進行預(yù)處理，詳細(xì)流程如下文所述。

（1）分組。分組長度和DES 加密的分組長度一致（64 位），最后一組不足64 位的以0 補足。

（2）分段。段是比組更高一級的單位，每段包含64個分組，最后一段不足64組的以0補足。

對預(yù)處理后的明文用P0表示，得出P0==S0,S1, …,S63，其中Si為P0的第i個分段，S i==Gi0,Gi1,…,Gi63（Gij為Si段的第j個分組），Gi j=bi j0,bij1,…,bij63（bijk為Gij分組中的第k位）。

整個加密過程需經(jīng)過3 次加密，分別以U，J，D表示，每次加密后的密文分別以A，B，C表示。圖1 說明了3 次加密之間的輸入/輸出關(guān)系。

2.2.3 密文包的頭部結(jié)構(gòu)

RSA 頭包括3 個關(guān)鍵字段和一些輔助字段（如圖2 所示）。關(guān)鍵字段分別存放3 個密鑰，對應(yīng)加密流程的U，J，C 這3 個階段。輔助字段主要存放控制和校驗信息。這些字段的名稱、長度和作用如下文所述。

（1）亂序密鑰（Confusing Key，CK）。亂序密鑰的作用是對每段明文進行重排（Reshuffle）。其長度為64 個字節(jié)，每個字節(jié)最高位恒為0，最低位為校驗位，中間6 位轉(zhuǎn)化為10 進制數(shù)后表示一個加密參數(shù)Ki(i=0, 1, …,63 )，i為字節(jié)的序號。亂序加密算法為U(Gi)=b(0,K i),b(1,Ki),…,

b(63,Ki)，表明第i組的密文由明文各組的第Ki比特排列而成。其中，b(m,n)是第m組的第n位，滿足0≤m≤63。

（2）干擾密鑰（Jamming Key，JK）。干擾密鑰的作用是在密文A的每個分組中插入無效信息，以增加破解難度。其長度為8 位，前6 位表示在分組中插值的位置J( 0≤J≤63) ，后兩位是需要插入的值。如干擾密鑰是01011010,(01011010)2=(010110)2(10)2=(19)10(10)2，可以看出，干擾密鑰前6 位的10 進制數(shù)值為19，故J= 19，二進制10 會被插入到目標(biāo)分組的第19個比特前。干擾密鑰只應(yīng)用在密文A的第1 個分組中，此后，它會發(fā)生動態(tài)變化。應(yīng)用在密文A的第2 個分組的干擾密鑰將從第1 個分組的明文中產(chǎn)生。方法是把一個8 位的空字節(jié)（窗口）放置在明文第1 個分組的起始位置（即0號位），窗口的最高位對應(yīng)分組的0 號位，窗口顯示的字節(jié)即為第2 個分組的干擾密鑰。同樣地，把8 位窗口放置在第2 個分組的1 號位，得到第3 個分組的干擾密鑰。以此類推，每次把窗口右移一位，即可得到下一分組的干擾密鑰。如果窗口越過分組的右邊界，則把越過的比特循環(huán)對應(yīng)分組開始時的幾個比特。這種插值法有一個缺陷，密文分組的長度固定是66 位（因為插值固定是2 位），使攻擊者可以輕松地從密文中分離出有效分組，再對有效分組實施破解。為了使插值后的分組長度不固定，需要改變插值的長度，具體操作是從第2 個分組開始，使算法中干擾密鑰末兩位的含義發(fā)生變化，由原來的“插值的內(nèi)容”變化為“插值的位數(shù)”。插值的內(nèi)容從窗口后截取，截取的長度就是末兩位所指出的插值的位數(shù)。同樣地，截取插值時把背景分組看成首尾相接的環(huán)。這樣一來，插值長度可能是0，1，2，3 其中之一。

（3）DES 密 鑰（DES Key，DK）。DES 密鑰的作用、形式、應(yīng)用方法和經(jīng)典DES 加密密鑰一致，在RSA 頭占64 位，它作用于干擾加密的結(jié)果B，產(chǎn)生密文C。

（4）標(biāo)志位（Flags）。標(biāo)志位占2 位，分別指出在加密過程中是否使用了干擾加密和亂序加密。

（5）摘要算法（Hash Algorithm，HA）。摘要算法占6 位，對RSA 頭中特定部分應(yīng)用本算法，得出摘要（Hash）字段的值。特定部分是指RSA頭中從起始到標(biāo)志位（包括標(biāo)志位）的部分，本文稱為“上段”。這一字段最多可表示62 =64 種摘要算法，包括常用的MD5 信息摘要算法（MD5 Message-Digest Algorithm，MD5）、安全散列算法（Secure Hash Algorithm，SHA）等算法。

（6）保留位（Reserved Bits）。未使用位，留待優(yōu)化算法時使用。

（7）摘要（Hash）。摘要是對RSA 頭上段應(yīng)用“摘要算法”字段指定的散列算法而得到的哈希值，長128 位。

（8）校驗值（Checksum）。校驗值是密文部分的校驗值，所用散列算法由“摘要算法”字段指定，長128 位。

2.2.4 加密和解密流程

加密流程如下文所述。

（1）把原始明文P預(yù)處理為P0 。

（2）隨機產(chǎn)生3 個密鑰，即CK，JK，DK。

（3）對P0 應(yīng)用CK，得到A。

（4）對A應(yīng)用JK，得到B。

（5）對B應(yīng)用DK，得到C。

（6）填寫RSA 頭各字段。

（7）計算并填寫摘要（Hash）和校驗值（Checksum）字段。

（8）用接收方的公鑰加密RSA 頭的明文，得到密文包的頭部。

（9）把密文包頭部和密文C連接，整合成一個完整的密文包。

解密流程與加密流程各步驟的順序相反，要注意以下幾點。

（1）容易分離出密文包頭部，因為它的長度是固定的896 位。

（2）在解密密文包頭部時，須使用接收方的私鑰。

（3）對B應(yīng)用JK時（清除無效信息），是從第1 個分組開始，而不是相反地從最后一個分組開始。即先用JK恢復(fù)第1 個分組，再用8 位窗口循環(huán)右移的方法得到第2 個分組的干擾密鑰，從而恢復(fù)第2 個分組，以此類推。

（4）對于加密前的預(yù)處理，沒有逆算法，因而解密時不需要執(zhí)行逆算法。

3 改進DES 算法的抗攻擊能力分析

本文提出的改進DES 算法的密鑰不再是單一的對稱密鑰，而是由3個互相獨立的密鑰CK，JK，DK組成的密鑰集，并受RSA 密碼的保護。即使通過窮舉法暴力破解密鑰集CK，JK，DK，其面臨的可能密鑰組合數(shù)量為：64！×28×256=64！×264，這個組合數(shù)量已經(jīng)具備足夠的強度來抵抗當(dāng)前計算技術(shù)下可以實現(xiàn)的暴力破解攻擊。

對于統(tǒng)計分析攻擊的防御，DES 加密所實現(xiàn)的擴散模糊有效地抵御了基于統(tǒng)計的攻擊。這是經(jīng)典DES 算法的優(yōu)點之一[8]，本文的算法完整保留了這一優(yōu)點。

對于差分分析[9]、線性分析等數(shù)學(xué)分析方法的防御，因為多重密鑰必然會帶來分析參數(shù)數(shù)量的暴增，使得數(shù)學(xué)分析難度加大[10]，同時，分階段的加密流程使本算法難以使用單一的數(shù)學(xué)分析方法破解。表明對稱密碼和非對稱密碼體系在應(yīng)用中可以混合使用，取長補短，互為加固。

4 結(jié) 語

本文在經(jīng)典的DES 加密算法的基礎(chǔ)上，提出了一種改進算法。其設(shè)計思想是用非對稱密碼算法保護DES 密鑰，產(chǎn)生“密鑰外殼”，使加殼密鑰和密文組成了防御破解的共同體；同時在DES 加密的基礎(chǔ)上，增加了亂序加密和干擾加密，其密鑰同樣受到密鑰外殼的保護，使攻擊者無法在不攻破密鑰外殼的情況下，單獨對密文實施暴力破解。然而，這種算法的軟硬件實現(xiàn)方式和性能仍有待進一步評估和測試，這關(guān)系到它在何種范圍、何種場景中才能得到實際的應(yīng)用。