遞歸擴散層的權值系數計算方法

毛 明,楊 譜,2,李旭飛,2

(1.北京電子科技學院信息安全系,北京100070;2.西安電子科技大學通信工程學院,西安710071)

遞歸擴散層的權值系數計算方法

毛 明1,楊 譜1,2,李旭飛1,2

(1.北京電子科技學院信息安全系,北京100070;2.西安電子科技大學通信工程學院,西安710071)

遞歸擴散層是一種新型的密碼函數線性擴散層,具有良好的結構特征,能達到最優擴散層的效果,但其構造函數中的參數比較復雜,搜索空間也較大。為此,對遞歸擴散層的結構特點進行分析,從低階擴散層的結構出發,結合最優擴散層的相關理論基礎,得到遞歸擴散層的一般性結論,在此基礎上設計權值系數計算方法,并通過仿真實現得到部分低階遞歸擴散層的構造函數。分析結果表明,該方法構造的擴散層只需要少數的XOR運算、旋轉運算和簡單的求反運算,滿足最優擴散層的性質,具有較好的安全特性。

線性擴散層;遞歸擴散層;分支數;線性函數;權值系數;仿真實現

1 概述

1949年,香農發表了《保密系統的通信理論》一文,從信息論的角度對密碼進行了系統地闡述和分析,使人們對密碼有了科學的認識。從此,密碼研究成了一門新的科學領域,并進入了科學化、系統化的研究階段。同時,香農提出了密碼系統設計的2個基本方法:擴散和混淆。這也成為現今密碼設計和分析的基礎［1］。

線性擴散層是實現密碼系統擴散的核心組件,設計良好的擴散層可以有效地抵抗一些著名的密碼攻擊,如差分密碼分析［2］和線性密碼分析［3］。長久以來,人們主要通過MDS碼、BCH碼和Goppa碼以及范德蒙矩陣和柯西矩陣來構造性能良好的線性擴散層［4］。此外,結合數學方法和計算機搜索也可得到一些滿足不同需求的擴散層,如利用對合矩陣［5］、可逆擴散矩陣［6］以及模加移位［7］的線性變換來構造擴散層。

文獻［8］提出了遞歸擴散層的設計方案,是通過一種類Fesitel的結構構造出的一種擴散層變換,它滿足最優擴散層的條件。但是對于權值系數的判定和計算未給出具體算法。權值系數是設計遞歸擴散層最主要的參數,也是構造遞歸擴散層所需要實現的第一步,因此,設計權值系數的計算具有重要意義。本文結合最優擴散層層性相關理論,給出權值系數的計算方法,并通過仿真得到低階遞歸擴散層的構造函數。

2 相關理論基礎

2.1 擴散層分支數

分支數的概念由J.Daemen首次提出的。在迭代結構中,若S盒的輸入差分非零,則稱這個S盒是活躍的,相應的S盒叫活躍S盒子。分支數即是在連續兩輪的差分或線性特征中活躍S盒的最小數目。分支數又分差分分支數和線性分支數［9］,具體定義為:設X是由S個n-bit元素組成的集合X=［x0(n),x1(n),…,xs-1(n)］。其中,非零元素的個數記為w(X),即X的漢明重量。那么對于一個以X為輸入的線性變換D函數,有如下定義:

定義1 線性變換D的差分分支數為:

已知對于線性變換D,通常可以用一個二進制的矩陣 Bt表示,Bt表示 B的轉置,則Dt可由 Bt得到。

定義2 線性變換D的線性分支數為:

2.2 最優擴散層

對于擴散層安全性能一般用分支數這個量化指標來進行衡量。當擴散層變換的分支數達到最大時,則稱該擴散層是最優擴散層。

理論上如果分支數相對較小,那么這個密碼算法就更容易受到差分分析和線性分析的攻擊;反之,分支數越大,擴散層的擴散效果越好,安全性越好。

定理 若線性擴散層是最優的,那么構成它的變換矩陣的所有子方陣是非奇異的［10］。

2.3 遞歸擴散層定義

定義3 對于一個s個字xi輸入的擴散層D,輸出為s個字yi,稱這樣的擴散層為遞歸擴散層,如滿足以下條件:

其中,F0,F1,…,Fs-1為任意函數。擴散層D有s個字xi作為輸入,其中,i={0,1,…,s-1},同時輸出s個字yi。則可以用下式表示該擴散層:

這類擴散層D可以用下面的程序表示,其中,L是個線性函數,αk,βk∈{0,1},α0=1,β0=0。

輸入 s n-bit words x0,x1,…,xs-1

輸出 s n-bit words y0,y1,…,ys-1

實際上,上述的擴散層就是式(1)的一種特殊形式,它們的Fi函數都是一致的,可寫成下面形式:

可以看出,式(2)的遞歸擴散層實際上是一種類Feistel的結構［11］遞歸擴散層中的線性變換L都是一樣的,在實際應用中,取L為簡單有限域上的線性變換,它包括少數的XOR運算、旋轉運算和一些簡單的求反運算。這種形式的結構是比較容易實現的。

3 權值系數計算

對于式(2)所表示的遞歸擴散層,本文在權值系數αi和βi已知的情況下,對線性函數L作進一步分析。事實上,αi和βi的取值范圍是很大的,對于一個s×s的擴散矩陣,αi和βi的取值就存在22s種可能情況,當s=8時,即有216=65 536種,在具體仿真實現過程中需要建立模型,找到滿足條件的權值系數。

此處需要利用2.2節的定理,這是下面仿真實現最根本的理論基礎和依據。

3.1 3×3階遞歸擴散層模型

但是在式(2)中,存在3種未知的變量,權值系數αi,βi和線性函數L,首先必須得到 αi和βi才能進一步對線性函數L進行分析。為解決在未知變量L的前提下實現 αi和 βi仿真的問題,下文將以3×3階的遞歸擴散層為例進行分析,并推導出一般模型,具體分析過程見下。

對于3×3遞歸擴散層,根據式(2)其方程形式如下:

合并同類項,得:

將y0代入y1,得:

由上式即可得到3×3階遞歸擴散層變換矩陣的部分元素,設變換矩陣為A,則:

由2.2節定理可知,矩陣A的所有子方陣都是非奇異的。為了方便分析,本文只取A矩陣的第1行、第2行、第1列、第3列元素所組成的子方陣進行討論,設該子方陣為B,則:

下面對αi和βi進行取值:

3.2 權值判定的算法實現

這是一個非常好的現象,因為這樣就可以在實際程序執行過程中,摒棄變量L不可操作的限制,而把它們看成一個多項式。

則可將權值系數的判斷改寫成如下過程:

(1)選擇權值系數αi和βi。若取完所有值,結束程序。

(3)判定向量U=(u0,u1,…,un),若U=0,返回(1),若U≠0,返回步驟(2)。

3×3階遞歸擴散層權值系數仿真算法流程如圖1所示。對于3入3出的擴散層,其變換矩陣A為3×3形式的,除9個矩陣元素和本身外,還有9個2×2的子方陣,總共要判定19次,一旦出現零值則跳出程序,重新選擇權值系數,非零則繼續,直到最后一個子方陣,若都為非零的,那么選取該權值系數,它是滿足條件的。

圖1 3×3階遞歸擴散層權值系數算法流程

3.3 通用模型的建立

根據以上的分析可得出3階遞歸擴散層權值系數的實現規則和算法過程,那么對于更高階數的遞歸擴散層,也同樣可以用這種方式進行操作,從而上述結論推廣到其他階數的擴散層。同樣地,本文給出S階遞歸擴散層算法的具體流程,如圖2所示。

圖2 遞歸擴散層權值系數算法流程

遞歸擴散層權值系數實現算法的偽代碼描述如下:

3.4 程序實現及仿真結果

本文對上述的算法模型進行程序實現,在實際編程過程中需要考慮很多問題,如有限域上乘積運算、線性方程的矩陣構造、子方陣的構造、有限域上的行列式運算等。本文利用 C語言［12］進行編程。下面僅對主函數作簡要說明,主函數程序如下:

由上面的主函數程序可以看出,算法主要分為4個步驟:(1)初始系數賦值;(2)生成變換矩陣; (3)變換矩陣判斷;(4)輸出滿足條件的系數。

通過程序實現得到了權值系數的仿真結果,在整個搜索空間中,當s=3時,有196種滿足條件的分支數達到4的權值系數組合,當s=4時,有1 634種滿足條件。對其進行整理,分別得到2階、3階、4階遞歸擴散層的仿真結果的部分生成式,如表1所示。

表1 低階遞歸擴散層權值系數仿真結果

4 結束語

本文通過對遞歸擴散層的結構分析,給出了權值系數的仿真實現方法,并得到了實驗結果,確定了通用遞歸擴散層的基本結構,此外,還給出了1階～4階擴散層系數仿真的結果。根據最優擴散層的條件——分支數達到最大,便可以很容易地分析得到滿足條件的線性變換L,從而實現遞歸擴散層的構造,它滿足最優擴散層的性質,具有很好的安全特性。但由于資源和條件的限制,本文主要從低階遞歸擴散層進行分析,給出了低階模型的通用分析方法和實驗結果,這種方法原則上可以推廣到更高階次,但對于高階遞歸擴散層,由于計算成本較高,模型更為復雜,算法實現的復雜度較高,這還需進一步改進和優化。

［1］ 楊 波.現代密碼學［M］.北京:清華大學出版社,2010.

［2］ Biham E,Shamir A.Differential Cryptanalysis of DES-like Cryptosystems［C］//Proceedings of Cryptology'90.Santa Barbara,USA:Springer-Verlag,1990:3-72.

［3］ Matsui M.Linear Cryptanalysis Method for DES Cipher［C］//Proceedings of Eurocrypt'93.Lofthus,Norway: Springer-Verlag,1993:386-397.

［4］ 楊宏志,韓文報,沈 勇.AES擴散層的分析及改進方案設計［J］.計算機工程與應用,2009,45(36):12-14.

［5］ 王念平,金晨輝,余昭平.對合型列混合變換的研究［J］.電子學報,2005,33(10):1917-1920.

［6］ 田英倩,徐克艦,范修斌.一類可逆線性變換的分支數分析［J］.青島大學學報:自然科學版,2009,22(4): 34-46.

［7］ 李瑞林,熊 海,李 超.基于循環移位和異或運算的對合線性變換研究［J］.國防科技大學學報,2012, 34(2):46-50.

［8］ Sajadieh M,Dakhilalian M,Mala H.Recursive Diffusion Layers for Block Ciphers and Hash Functions［C］// Proceedings of Fast Software Encryption Workshop.Washington D.C.,USA:［s.n.］,2012:385-401.

［9］ 韓海清,張煥國.分組密碼P-置換的分支數研究［J］.小型微型計算機系統,2010,31(5):921-926.

［10］ Damgard I.A Design Principle for Hash Functions［C］// Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology.London,UK: Springer-Verlag,1989:416-427.

［11］ 胡予濮,張玉清,肖國鎮.對稱密碼學［M］.北京:機械工業出版社,2002.

［12］ 譚浩強.C程序設計［M］.北京:清華大學出版社,2003.

編輯 金胡考

Computing Method for Weight Coefficient of Recursive Diffusion Layer

MAO Ming1,YANG Pu1,2,LI Xufei1,2
(1.Department of Information Security,Beijing Electronic Science and Technology Institute,Beijing 100070,China;
2.School of Communication Engineering,Xidian University,Xi'an 710071,China)

Recursive diffusion layer is a new type of cryptographic linear diffusion layer.It has good structure characteristics,and can achieve the optimal effect of diffusion layer.It is more complex in the concrete implementation process because its function structure parameters in the search space is large.It seriously impacts on its cryptographic function in the actual application ability.After analyzing the structure and the lower order based on the structure of the diffusion layer,and combining with the optimal diffusion layer of relevant theoretical basis,this paper gets some general conclusions of recursive diffusion layer,and based on this,it gives a method to design the recursive diffusion layer and puts forward a scheme to improve the coefficient's implementation of recursive diffusion layer.By the simulation realization,it gets the results of recursive diffusion layer's structure in low order.The diffusion layer only needs a few XOR operation, rotating operations and some simple complementation operations,and it has a better security character.

linear diffusion layer;recursive diffusion layer;branch number;linear function;weight coefficient; simulation realization

1000-3428(2014)11-0126-04

A

TP309

10.3969/j.issn.1000-3428.2014.11.025

毛 明(1963-),男,教授,主研方向:信息安全,密碼學;楊 譜、李旭飛,碩士。

2013-11-26

2014-01-17E-mail:yangpu616@163.com

中文引用格式:毛 明,楊 譜,李旭飛.遞歸擴散層的權值系數計算方法［J］.計算機工程,2014,40(11):126-129.

英文引用格式:Mao Ming,Yang Pu,Li Xufei.Computing Method for Weight Coefficient of Recursive Diffusion Layer［J］.Computer Engineering,2014,40(11):126-129.