DES分組密碼算法設(shè)計理論研究初探

李麗坤 田利芹

摘要：隨著科學(xué)技術(shù)的不斷進步，計算機和通信技術(shù)有力長足發(fā)展。用戶迫切需要對信息進行安全存儲，信息的安全性逐漸成為時代的主體。在這種背景下，現(xiàn)代密碼學(xué)應(yīng)運而生。其中，分組密碼作為現(xiàn)代密碼學(xué)的重要分支，在實際應(yīng)用中發(fā)揮著重要作用。本文通過研究分析分組密碼的設(shè)計原理及其整體結(jié)構(gòu)，并詳細闡述了S盒、P置換、輪函數(shù)的設(shè)計準則及其構(gòu)造，以及密鑰擴展算法的設(shè)計等，進而為用戶的信息安全提供理論保證。

關(guān)鍵詞：分組密碼DES輪算法

隨著科學(xué)技術(shù)的不斷進步，計算機網(wǎng)絡(luò)得到了普及和推廣，進而推動通信技術(shù)的發(fā)展。同時，用戶信息的安全性受到嚴重的沖擊和考驗，為了確保用戶的信息安全，通過借助先進的密碼技術(shù)對用戶信息進行保護。在這種背景下，分組密碼憑借速度快，標準化簡單，以及軟硬件實現(xiàn)容易的優(yōu)勢，進而在信息和網(wǎng)絡(luò)安全中實現(xiàn)數(shù)據(jù)加密、數(shù)字簽名、認證以及管理密鑰等，在信息安全領(lǐng)域得到推廣和使用，其誕生和發(fā)展無論對理論還是實踐都具有重要的價值。

1 分組密碼的設(shè)計原則

通過尋找一種算法來完成分組密碼的設(shè)計，在密鑰的控制下該算法能夠從一個置換子集中簡單快捷地選出一個置換，進而對輸入的明文完成加密變換。通常情況下，一個良好的分組密碼要具備難破譯和易實現(xiàn)雙重優(yōu)點，借助加密函數(shù)E（·，k）和解密函數(shù)D（·，k）是可以計算的。但是，想通過利用方程y=E(x，k)和x=D(y，k)，進而解出密鑰k卻是十分困難的。分組密碼的設(shè)計原則分為：

1.1 實現(xiàn)原則 所謂實現(xiàn)原則就是分組密碼可以通過軟件和硬件實現(xiàn)。其中，軟件實現(xiàn)的優(yōu)點具有很強的靈活性、代價比較低；硬件實現(xiàn)的優(yōu)點是速率高。在性質(zhì)方面由于軟硬件之間存在的差異較大，通常情況下借助預(yù)定的實現(xiàn)方法對分組密碼設(shè)計原則進行考慮。①軟件實現(xiàn)的原則。密碼的簡單運算是借助字塊來實現(xiàn)的。由于在字塊上實現(xiàn)密碼的運算，所以，在長度方面要求子塊要與軟件編程彼此相互適應(yīng)，比如8B、16B、32B等。在通過軟件實現(xiàn)的設(shè)計原則中，利用比特置換實現(xiàn)起來存在一定的難度，因此在實踐中盡量少用它。通過子塊進行的密碼運算從根本上說利用軟件是容易實現(xiàn)的，其中較為理想的借助標準處理器自身所具備的如加法、乘法和移位等指令。②硬件實現(xiàn)的原則。通常情況下，加密盒解密的相似性，實際上就是對加密盒進行解密的過程僅在于使用密鑰的方式不同而已，也就是采用同樣的器件完成加密和解密的雙重功能。一般情況下硬件實現(xiàn)依靠規(guī)則結(jié)構(gòu)，通過標準化組件結(jié)構(gòu)與超大規(guī)模集成電路相互適應(yīng)。

在設(shè)計原則方面，迭代密碼與上述原則相似。通過簡單的輪函數(shù)便可實現(xiàn)迭代密碼，通過選擇適當?shù)妮喓瘮?shù)，必要的混亂和擴散經(jīng)過若干次迭代后可以實現(xiàn)。

1.2 安全原則 分組長度、密鑰長度等因素都會對安全構(gòu)成一定的影響。有關(guān)實用密碼的兩個一般的設(shè)計原則為：①混亂原則。通常情況下，人們設(shè)計的密碼應(yīng)確保密鑰和明文、密匙和密文之間存在相當復(fù)雜的依賴關(guān)系，密碼分析者無法利用依賴關(guān)系。②擴散原則。密碼設(shè)計者設(shè)計的密碼，在一定程度上密鑰的每一位數(shù)字影響密文的多位數(shù)字，進而在最大限度上，避免逐段破譯密鑰。對于密文的許多數(shù)字也要影響明文的每一位數(shù)字，進而隱蔽多位數(shù)字的統(tǒng)計特性。

另外，在攻擊方面，密碼體制必須對所有攻擊方法能具備抵抗作用。

2 分組密碼的整體結(jié)構(gòu)

Feistel網(wǎng)絡(luò)由Horst Feistel在設(shè)計Lucifer分組密碼時發(fā)現(xiàn)的，因DES的使用而廣為流行，F(xiàn)eistel網(wǎng)絡(luò)又稱Feistel結(jié)構(gòu)，其功能是將函數(shù)（輪函數(shù))轉(zhuǎn)化為一個置換，F(xiàn)eistel型密碼的實現(xiàn)的優(yōu)點是加密與解密相似。另外，F(xiàn)eistel型密碼算法需要兩輪才能改變輸入的每一比特，因此，在擴散方面比較慢。Feistel網(wǎng)絡(luò)經(jīng)Schneier B和Kelsey J推廣到非平衡Feistel網(wǎng)絡(luò)（又稱非平衡Feistel結(jié)構(gòu)），簡記為UFN。所謂UFN就是Feistel網(wǎng)絡(luò)左邊和右邊長度不一樣。與此相對應(yīng)的原始的Feistel網(wǎng)絡(luò)又稱平衡Feistel網(wǎng)絡(luò)，簡記為FN。

3 S盒的設(shè)計準則和構(gòu)造

3.1 設(shè)計準則 在Lucifer算法中首次出現(xiàn)S盒，隨著DES的使用S盒變得廣為流行。在許多密碼算法中S盒是唯一的非線性部件。因此，整個密碼算法的安全強度受到S盒密碼強度的影響。在本質(zhì)上可以將S盒看作S（X）=（f1(x)，…，fm(x)）：F2n F2m的映射，通常情況下可以簡稱S是一個n×m的S盒。當選擇的參數(shù)m和n比較大時，所有的S盒幾乎都是非線性的，而且難以發(fā)現(xiàn)某些攻擊所用的統(tǒng)計特性。同樣，過大的m和n將增加算法的存儲量，給S盒的設(shè)計帶來許多困難。當前，比較流行的S盒是8×8的。S盒的功能是為分組密碼算法提供混淆作用，設(shè)計S盒的準則為：①非線性度。②差分均勻性。③代數(shù)次數(shù)及項數(shù)分布。④完全性和雪崩效應(yīng)。⑤擴散特性。⑥可逆性。⑦沒有陷門。

3.2 構(gòu)造S盒的方法 ①隨機選取并測試。通過隨機選擇的小規(guī)模的S盒，其安全性并不高。但也有實踐表明，隨著S盒規(guī)模的增大，其隨機產(chǎn)生的密碼性能就越好。隨著n值的不斷增大，F(xiàn) 上的置換均是非退化置換，特別是當S盒一方面既隨機，另一方面對密鑰構(gòu)成依賴時，那么S盒的強度就會越高。通過進行隨機選取，利用測試對某些特定需求進行篩選。在時間和計算能力允許的情況下，設(shè)計者利用該方式可以構(gòu)造所需的S盒，而且使用戶堅定沒有陷門的信心。②按規(guī)則構(gòu)造并測試。借助已有的“好”的S盒，進而在一定程度上對滿足需要的S盒進行構(gòu)造，通過這種構(gòu)造方式，利用DES的S盒生成Serpent算法所用的S盒。并且通過此種方法構(gòu)造的S盒使用戶相信沒有陷門。

4 P置換的設(shè)計準則及其構(gòu)造方法

4.1 P置換準則 一般情況下，通過將若干個S盒進行并置，進而構(gòu)成SP網(wǎng)絡(luò)中的混淆層，P的目的是制造雪崩效應(yīng)，而一個置換P可以實現(xiàn)擴散層。由于在軟件實現(xiàn)中難以實現(xiàn)比特置換，因此，如果m個n×n的S盒并置而成混淆層，一般將P設(shè)計成(F2n)m→(F2n)m的一個置換，其中(F2n)m=F2n×…×F2n。

4.2 P置換的構(gòu)造方法 ①分支數(shù)最佳的置換P的構(gòu)造。②多維2-點變換擴散器（multi-dimensional 2-point

transform diffuser）。其中，上述兩種構(gòu)造方法各具優(yōu)勢，方法①實現(xiàn)起來比較困難，但是構(gòu)造的P的分支數(shù)是最佳的；相對①而言方法②實現(xiàn)起來相對容易，但是所構(gòu)造的P的分支數(shù)比較少。

5 輪函數(shù)的設(shè)計準則及其構(gòu)造

5.1 設(shè)計準則 ①安全。②速度。③靈活。

5.2 構(gòu)造輪函數(shù) 在當前的密碼算法中，輪函數(shù)分為：①有S盒的，例如，DES、LOKI系列、E2等。②沒有S盒的，例如，IDEA，RC5、RC6等。對于沒有S盒的輪函數(shù)，通過借助加法運算、乘法運算、數(shù)據(jù)依賴循環(huán)等實現(xiàn)“混淆”。

6 密鑰擴展算法的設(shè)計

所謂密鑰擴展算法就是由種子密鑰生成的子密鑰的算法，子密鑰統(tǒng)計的獨立和靈敏性是密鑰擴展算法理論設(shè)計的目標。子密鑰統(tǒng)計獨立在密碼算法設(shè)計中是不可能做到的，在設(shè)計的過程中，設(shè)計者只能使子密鑰趨于統(tǒng)計獨立。對于密匙擴展算法的靈敏性是指密鑰更換的有效性，即對種子密鑰的少數(shù)幾比特進行改變，在較大范圍對子密鑰進行改變。為了實現(xiàn)上述目標，設(shè)計密鑰擴展算法應(yīng)遵循：①實現(xiàn)簡單。②速度。③沒有簡單關(guān)系。④每個子密鑰比特受種子密鑰所有比特的影響相似。⑤在計算上難以實現(xiàn)從一些子密鑰比特獲得其他的子密鑰比特。⑥沒有弱密鑰。

參考文獻：

[1]馮登國，吳文玲.分組密碼的設(shè)計與分析[M].清華大學(xué)出版社，2009.

[2]Adams C,Tavares S.The structured design of cryptographically good S-boxes.Journal of Cryptology,1990.3(1):27-

41.

[3]Detombe J,Tavares S.Constructing large cryptographically strong S-boxes.In:Advances in Cryptology-Auscrypt92 Proc,Berlin:Springer-Verlag,2008.,165-181.

[4]O,Connor L.Enumerating nondegenerate permutations. In:Advances in Cryptology-Eurocrypt91,Berlin:Springer-Verlag,2010，368-377.