基于流密碼的改進DES的研究

劉海峰 曹語默 梁星亮

1(陜西科技大學(xué)文理學(xué)院 陜西 西安 710021)2(陜西科技大學(xué)電氣與信息工程學(xué)院 陜西 西安 710021)

0 引 言

數(shù)據(jù)加密標準也稱為數(shù)據(jù)加密算法，是近20年來廣泛使用的加密算法。后來，人們發(fā)現(xiàn)DES在強大攻擊下太脆弱，因此使DES的應(yīng)用有所下降[1]。二重DES是在DES的基礎(chǔ)上研究出來的，其密鑰長度是DES密鑰長度的2倍。然而，當二重DES遇到中間相遇攻擊時，有效密鑰長度將減少為56位。DES易受窮舉搜索攻擊，二重DES易受中間相遇攻擊。徐鵬等[2]提出了一種抗差分功耗攻擊的DES算法，采用掩碼技術(shù)增強了算法安全性；閆喜亮[3]提出將DES應(yīng)用到芯片加密中，提高了電路中的安全性；謝志強等[4]提出基于前綴碼的DES算法改進研究；周建欽等[5]提出DES加密算法的密鑰擴展；邱偉星等[6]提出一種DES密鑰延長方法。這些對DES加密算法的研究在一定程度上增強了DES的安全性，但都沒有改變DES子密鑰的生成方式。序列密碼是密碼學(xué)的一個很重要的分支，通常也稱為流密碼，它可以利用密鑰流生成器生成一段偽隨機序列，該序列即可作為密鑰對明文進行加密。1949年，香農(nóng)證明了只有一次一密的密碼體制是絕對安全的，是牢不可破的[7]。因為密文與明文統(tǒng)計獨立，所以即使擁有無限計算能力都無法猜測出信息比特[8]。文獻[9]將RC4算法應(yīng)用于移動設(shè)備上的多媒體文件的加密。本文提出基于流密碼的改進DES算法，提高了算法的安全性，使得算法更難破譯。

1 DES算法[10-11]

1.1 傳統(tǒng)DES加密算法

(1) 初始IP置換。IP置換主要是將64位明文按照IP置換表按位進行重新排序，將新的64位數(shù)據(jù)分為、兩部分，每部分的長度均為32位。

(2) E擴展置換。擴展置換主要是將部分的32位的輸入進行處理加工，最后得到一組48位的輸出。通過將第32、1、4、5、8、9、12、13、16、17、20、21、24、25、28、29共16位分別放置在兩個位置，從而將32位的數(shù)據(jù)擴展為48位，具體如表1所示。

表1 擴展置換表

(3) S盒代替。將經(jīng)過移位處理后的48位密鑰與擴展分組進行“異或”運算得到48位新的數(shù)據(jù)，將其作為S盒的輸入進行替代運算得到處理之后的數(shù)據(jù)。替代運算是將處理后的48位數(shù)據(jù)進行分組運算，將數(shù)據(jù)分成8組分別輸入到8個S盒內(nèi)，這樣就可以得到8組4位的輸出結(jié)果，即32位輸出數(shù)據(jù)。

(4) P盒置換。P盒置換主要是對S盒輸出的數(shù)據(jù)進行置換處理。通過將32位中的每一位進行映射，最終得到輸出結(jié)果。置換運算表中的第一行第一列為16，則將S盒輸出的第16位放置在第一位上，以此類推，實現(xiàn)置換處理，置換運算表如表2所示。

表2 置換運算表

(5) 置換。置換是初始置換的逆過程，當DES執(zhí)行到第16輪時，直接將L0、R0進行結(jié)合，將合并的結(jié)果直接作為置換的輸入即可得到密文。

1.2 傳統(tǒng)DES子密鑰生成算法

(1) 由于DES的密鑰存在奇偶校驗位，首先將密鑰的第8、16、24、32、40、48、56、64位去除，使得密鑰長度只有56位，然后根據(jù)選擇置換將這56位分成兩塊C0和D0。

(2) 將C0和D0進行循環(huán)左移變化。變換后生成C1和D1，然后合并C1和D1，并通過選擇置換PC-2即可得到子密鑰K1(48位)。

(3) 同理，循環(huán)左移變換C1和D1可以得到C2和D2，然后合并C2和D2，采用選擇置換PC-2處理合并結(jié)果得到密鑰K2(48位)。

(4) 以此類推，得到K16(48位)。

1.3 算法評價

DES加密算法對于相同的明文，只要密鑰不變，加密結(jié)果就會相同，這使得攻擊者根據(jù)截獲的明文密文對，即可分析出密鑰。同時DES密鑰長度只有64位(實際只有56位)，并且之間存在較強的依賴性，攻擊者可以通過窮舉搜索的方法對DES的密鑰進行破譯[12-13]。

2 RC4算法

2.1 算法簡介

RC4算法[14]屬于流密碼(序列密碼)之一，主要作用是利用初始密鑰經(jīng)過一些置換操作來擴展密鑰，生成偽隨機序列。RC4算法的密鑰長度范圍在1～256字節(jié)之間，對于長度相同的密鑰也可以產(chǎn)生不同長度的密鑰流序列，然后通過將明文或密文與密鑰流進行“異或”運算來實現(xiàn)加解密運算。RC4算法的優(yōu)點是算法易于理解，運算速度非?？臁Ｍ瑫r，在軟件和硬件中都很容易實現(xiàn)該算法。它廣泛應(yīng)用在一些協(xié)議和標準里，如WEP、WPA、SSL等。

(1) 初始化S和T首先初始化狀態(tài)數(shù)組S，數(shù)組S中元素的值被按升序從0到255排列，即S[0]=0,S[1]=1,…,S[255]=255。然后建立一個數(shù)組T，該數(shù)組是包含256個元素且每個元素均以字節(jié)形式存儲的數(shù)組。使用初始密鑰K來對數(shù)組T進行賦值，如果密鑰K的長度恰好為256個字節(jié)，則直接將K賦給T。如果密鑰K的長度不足256，假設(shè)密鑰長度為n，則將K的值分配給T的前n個元素，然后依次用K的值分配給T剩下的元素，直到T的所有元素均已分配到對應(yīng)的值。

(2) 初始排列S設(shè)置下標變量i和j，并將i和j的值均初始化為0，將下標變量i從1～255循環(huán)，對于每一個i的取值，計算j=(j+S[i]+T[i])mod 256，然后交換S[i]和S[j]。

2.2 算法分析

RC4算法簡潔易于軟件實現(xiàn)，加密速度快，安全性比較高，密鑰長度可變。關(guān)于分析RC4的攻擊方法有許多公開發(fā)表的文獻，但沒有哪種方法對于攻擊足夠長度密鑰(如128位)的RC4有效[15]。

3 基于RC4的改進DES算法步驟

針對RC4算法具有密鑰長度可變的特點，提出一種新的基于RC4算法的改進DES加密算法，具體步驟如下：

(1) 用戶隨機生成一個n字節(jié)的密鑰(1

(2) 初始化S和T。S中元素的值被按升序從0到255排列，即S[0]=0,S[1]=1,…,S[255]=255。設(shè)置向量T，運用初始密鑰K將T的所有元素賦值。

(3) 初始化下標變量i和j值為0，將下標變量i的循環(huán)范圍是從1～255，每取一個i的值，計算j=(j+S[i]+T[i])mod 256，然后將S[i]和S[j]互換。

(4) 初始化下標變量i、j和r值為0。由于每組DES加密算法需要進行16輪加密，每輪加密需要長度為48位的子密鑰(即長度為6字節(jié)的子密鑰)，所以每組加密需要16×6=96字節(jié)長度的子密鑰。假設(shè)DES算法的明文分組的組數(shù)為m，則m組明文共需要長度為96m字節(jié)的子密鑰。將r從1到96m進行循環(huán)賦值，對于每一個r值，i=(i+1)mod 256；j=(j+S[i])mod 256；然后交換S[i]和S[j]，同時將下標變量t賦值為(S[i]+S[j])mod 256；并將S[t]值賦值給K[r]，得到96m個字節(jié)的密鑰流。

(5) 將96m個字節(jié)的密鑰每96個字節(jié)分為一組，即可得到m組DES加密的子密鑰。將96個字節(jié)每6個字節(jié)(6字節(jié)即48位)分為一組，即可得到每組DES加密過程中16輪加密所用到的子密鑰。

(6) 由于解密的需要，將隨機選取的RC4算法的密鑰K利用接收方的公鑰進行RSA加密，并與密文一起傳送給接收方[16]。

(7) 解密時，接收方利用RSA私鑰對隨機選取的RC4算法的密鑰K進行解密，根據(jù)所選取的密鑰通過RC4算法求出DES子密鑰，然后執(zhí)行DES的逆過程即可得到明文。

4 改進算法示例

隨機選取密鑰字節(jié)數(shù)n=8，并隨機生成對應(yīng)字節(jié)的密鑰K=70399AEC769284DA，運用RC4算法生成DES加密算法所需子密鑰，每一組DES加密所需子密鑰的長度為768位，即96個字節(jié)。選取一組明文進行加密，該明文滿足前64位與后64位相同。以明文m=computercomputer為例，首先將明文用ASCII碼表示為：

m=01100011 01101111 01101101 01110000

01110101 01110100 01100101 01110010

01100011 01101111 01101101 01110000

01110101 01110100 01100101 01110010

或用十六進制表示為：

m=63 6F 6D 70 75 74 65 72

63 6F 6D 70 75 74 65 72

由此可得，需將明文分成兩組進行加密。下面運用RC4算法生成DES加密的子密鑰，初始密鑰K=70399AEC769284DA依次經(jīng)過RC4算法的以下操作：(1) 初始化S和T向量；(2) 按照一定的規(guī)則交換S[i]和S[j]；(3) 循環(huán)賦值，最終得到192字節(jié)的DES加密的子密鑰，如表3所示(表3中DES加密子密鑰以16進制形式表示)。

表3 DES加密子密鑰

續(xù)表3

運用表3中的DES加密子密鑰對DES的每組明文分別進行加密，即可得到所對應(yīng)的密文結(jié)果。解密時，執(zhí)行該改進算法的逆過程即可將密文解密成明文，計算結(jié)果如表4所示。

表4 加解密結(jié)果

傳統(tǒng)DES加密算法的子密鑰之間是互相依賴的，容易受到窮舉搜索等方法的攻擊。本文提出的基于RC4的改進DES算法是由RC4算法產(chǎn)生密鑰流。由于RC4算法產(chǎn)生的密鑰流是偽隨機序列，所以即使所加密的明文相同，也會產(chǎn)生不一樣的加密結(jié)果。

5 安全性分析

傳統(tǒng)DES加密密鑰的破譯需要進行256次窮舉，本文提出的基于RC4的改進DES算法是通過RC4算法生成密鑰流，將生成的密鑰流作為DES的16輪加密密鑰，從而將明文進行加密。攻擊者如果想破譯密鑰有兩種途徑：(1) 對生成密鑰流的RC4算法的初始密鑰進行窮舉；(2) 對生成的密鑰流進行窮舉。

RC4算法的優(yōu)點在于它的初始密鑰長度范圍可以在1～256個字節(jié)之間變化，所以使用第一種破譯辦法需要進行窮舉28+216+…+2256次；第二種途徑的窮舉次數(shù)與明文分組有關(guān)，由于每組加密都需要進行16輪，每輪需要48位的密鑰，所以每組加密需要768位的密鑰流，假設(shè)將明文分成G組進行加密，則使用第二種破譯辦法需要進行窮舉的次數(shù)為2768G次。

同時，密鑰的生成不是由密鑰擴展而來，密鑰之間沒有相關(guān)性，所以即使攻擊者截獲到了部分明文以及對應(yīng)密文，也沒有辦法推導(dǎo)出密鑰流序列，算法的安全性大大增加，因此基于RC4的改進DES算法是安全的。

6 結(jié) 語

DES的算法設(shè)計很好，它的不安全性主要是子密鑰的生成互相依賴，并且易受窮舉搜索攻擊。本文在DES的算法基礎(chǔ)上，對DES子密鑰的生成采用流密碼的RC4算法，隨機生成DES加密密鑰，實現(xiàn)了一次一密，使得攻擊者每次破譯DES一組子密鑰至少需要進行2768窮舉，大大提高了DES的安全性和可靠性。