混沌分組密碼抗差分密碼攻擊的分析

鄭曉麗， 姜迪剛

（①軍事體育進修學院，廣東 廣州 510500；②中山大學基礎醫學院，廣東 廣州 510080）

0 引言

隨著互聯網和計算機技術的迅猛發展，計算機和通信網絡已經融入軍事作戰、軍事偵查中，而保證軍事通信信息的安全就成為亟待解決的問題。隨著密碼技術不斷發展，密碼學中的混沌理論與密碼學的融合也日趨成熟，混沌密碼學也成為密碼學的一個重要分支[1-2]。目前主要采用的方法是，利用混沌映射構造出S盒[3-4]，再與分組密碼進行結合。但是，對于混沌密碼的安全性分析卻非常少，有的也僅僅是對S盒的抗差分、線性分析，并沒有對整個密碼結構進行完整的安全性分析[5]。本文針對基于Feistel結構的動態混沌密碼，對其密碼算法進行了系統的安全性分析[6]。

1 基于Feistel結構的混沌分組密碼

Feistel結構是 20世紀60年代末IBM 公司的Feistel和 Tuchman在設計Lucifer分組密碼時提出的，后因 DES算法的廣泛使用而流行[7-8]。它最大的特點是加解密相似，就是在設計輪函數時不管多么復雜也不用考慮解密時的結構，它已被證明具有很好的安全性[9]。基于 Feistel結構的混沌分組密碼算法流程如圖1示。

將128 bit的明文進行加密，加密過程中將f函數對應的 Logistic映射取兩個不同的初值生成兩個不同的S盒f1和f2，加密中奇數輪使用f1，偶數輪使用f2，經過整個擴展加解密結構后得到128 bit偽明文，將其輸入初始逆變換中求逆，得到明文，這樣便完成了整個加解密流程。

圖1 算法流程

擴展Feistel結構的分組加密算法包括8輪，第i輪中(1≤i≤8)，Bi-1是輸入，Bi是輸出，B0是明文，B8是經過加密的密文，明文的長度是128 bit，加密產生的密文也是128 bit，每個分組Bi,j是8 bit。整個加解密過程首先對128 bit明文進行初始變換，讓明文通過一個類似P盒的結構，對明文的比特位進行置亂，但是不改變明文中的0和1 bit數，然后對產生的序列進行分組，將其按照8 bit為一組分成16組輸入擴展加解密結構，其中，f函數采用Logistic映射生成的S盒，混沌迭代的初值采用輸入密鑰。

每一輪的加密函數是：

對應的解密函數是：

加密輪結構中的f為使用Logistic映射構造的S盒，奇數輪用S1，偶數輪用S2。本算法使用動態S盒構造如下：

首先，初始S盒的生成，使用Logistic映射，K為二進制128位長的初始密鑰；

其次，使用Baker映射對生成的S盒進行置亂，經過離散化后的Baker映射表示為個整數的和是N，N=256，即令，其中，整個的Baker映射置亂表達式是：

密鑰選取Cubic映射來生成密鑰，Cubic映射的迭代方程式為：

其中通常選取A=4，B=3，0

2 固定S盒情況下的不可能差分分析

假設上述算法的S盒是固定狀態（即S1、S2為已知S盒）

2.1 S盒的第7輪是不可能差分

圖2所示為算法的7輪不可能差分。

圖2 七輪不可能差分

圖2可看出第7輪差分：(a7,a6,a5,a4,a3,a2,a1,a0,0,0,0,0,0,0,0,0)→(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,h)不可能發生，其中( i = 0 ,1,2,3,4,5,6,7)和g表示任意字節。輸入差分0,0,0,0,0)，0,14B?與子密鑰1,15K異或，經過S盒變換后，再與0,15B?異或得到1,14B?為一未知的非0字節7b。0,13B?與子密鑰1,14K異或，經過S盒變換后，再與0,14B?異或得到1,13B?為一未知的非0字節6b。以此類推，可以得出1,12B?,1,11B?,…,1,8B?,1,7B?的值分別為5b,4b,…,1b,0a。其余字節差分為 0，于是在第 1輪變換后的輸出差分變為同理，第2輪，第3輪，……第 7輪變換后的輸出差分分別為：，其中，其中8,9)≠0，0,0,0,0)，其中

2.2 對7輪不可能差分密碼進行分析

將上述7輪不可能差分用于第1輪--第7輪。

第2步：對1272 個明文對。篩選出密文差分8B滿足下面條件的數據對：，其中1h和h為任意非0字節，總共有個可能的密文對滿足條件，因此概率大約為，經過過濾，大約剩余151272 (2= ×個數據對。

第3步：猜測最后一輪子密鑰8K的前2個字節8,1K 、8,0K ，對于剩余的每一個數據對，計算并檢驗是否有如果等式成立，則說明相應的數據對滿足7輪不可能差分，所建議的密鑰猜測值就是錯誤的，這時刪除相應的密鑰猜測8,1K 、8,0K 。

攻擊復雜度分析：分析了 215個密文對進行刪除錯誤密鑰之后，大約會剩余密鑰猜測值。可以忽略第2步的時間復雜度。第3步需要大約231(=216×215)次1輪加密。因此，攻擊的數據復雜度大約為264個選擇明文，時間復雜度大約為228次8輪加密。

3 混沌動態S盒情況下的安全性分析

由以上分析可知，在S盒已知的情況下，不可能差分可以有效地攻擊此算法。所謂動態S盒是指，每一次加、解密所用的S盒是變化的，這就要求加、解密雙方所使用的S盒必須相同，否則接收方將無法正確獲得明文。因此，雙方共享的數據并不僅僅只有初始密鑰K，同時還包括迭代次數 1n+。

通過以上分析可得出如下結論，在S盒未知的情況下，7輪不可能差分路徑仍然可以通過上述方法構造，因為其中并沒有涉及到具體數據；上述步驟1、2也可如法炮制，但在分析步驟3時，由于并不知道 S盒的具體內容，這一步驟完成后并不能得到正確的數值，而想要通過強力攻擊來遍歷S盒幾乎是不可能的，因此，差分攻擊對于這種動態S盒的分組密碼并不能實施有效地攻擊。

本文所分析的混沌分組密碼能夠更有效地抵抗差分密碼分析。從分析過程中可以看出，這種基于Feistel結構的混沌分組密碼的安全性主要體現在混沌動態 S盒的變化性和不可知性上。這為混沌分組密碼的發展提供了良好的安全性保證。但從分析過程中也可以看出此算法每 1輪中的擴散度很少，8輪結構不足以使1比特擴散至其他所有比特中，適當增加輪數可以有效地解決這一問題；同時，由于此算法使用了混沌動態 S盒，雖然提高了加解密的安全性，但同時也增加了加解密的復雜度。

4 結語

本文對一種基于Feistel結構的混沌分組密碼進行了差分密碼分析，分析結果表明，由于混沌動態S盒的存在，使得此算法能夠有效地抵抗差分密碼分析。分析的同時也指出了一些此算法的不足，為混沌分組密碼的研究提供了參考。

[1] 廖曉峰,肖迪,陳勇.混沌密碼學的原理及應用[M].北京:科學出版社,2009:59-61.

[2] 鄭曉麗.基于單向函數樹的多播密鑰安全性分析[J].信息安全與通信保密,2007(05):127-128.

[3] ZHAO Geng,CHEN Guanrong, FANG Jingqing,et al.Block Cipher Design: Generalized Single-use-Algorithm based on Chaos[J]. Journal of Tsinghua University,2011,16(02):194-206.

[4] KOCAREV L,JAKIMOSKI G.Logistic Map as a Block Enryption Algorithm[J].Physics Letters A,2001,289(4-5):199-206.

[5] JAKIMOSKI G,KOCAREV L.Differential and Linear Probabilities of a Block-encryption Cipher[J].IEEE Trans. Circuits and Systems-I,2003,50(01):121-123.

[6] 吳文玲,馮登國,張文濤.分組密碼的設計與分析[M].第2版.北京:清華大學出版社,2009:1-2.

[7] 鄭曉麗.基于無證書公鑰密碼體制的密鑰管理[J].通信技術,2010,43(07):95-97.

[8] 鄭曉麗.基于無證書公鑰的IP注冊的移動協議認證[J].通信技術,2011,44(08):127-129.

[9] 韓睿.一種基于 Feistel結構的混沌分組密碼設計與分析[D].西安:西安電子科技大學通信工程學院,2011.