遞歸擴散層的權(quán)值系數(shù)計算方法

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

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

遞歸擴散層的權(quán)值系數(shù)計算方法

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

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

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

線性擴散層;遞歸擴散層;分支數(shù);線性函數(shù);權(quán)值系數(shù);仿真實現(xiàn)

1 概述

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

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

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

2 相關(guān)理論基礎(chǔ)

2.1 擴散層分支數(shù)

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

定義1 線性變換D的差分分支數(shù)為:

已知對于線性變換D,通?？梢杂靡粋€二進制的矩陣 Bt表示,Bt表示 B的轉(zhuǎn)置,則Dt可由 Bt得到。

定義2 線性變換D的線性分支數(shù)為:

2.2 最優(yōu)擴散層

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

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

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

2.3 遞歸擴散層定義

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

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

這類擴散層D可以用下面的程序表示,其中,L是個線性函數(shù),α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函數(shù)都是一致的,可寫成下面形式:

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

3 權(quán)值系數(shù)計算

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

此處需要利用2.2節(jié)的定理,這是下面仿真實現(xiàn)最根本的理論基礎(chǔ)和依據(jù)。

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

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

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

合并同類項,得:

將y0代入y1,得:

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

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

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

3.2 權(quán)值判定的算法實現(xiàn)

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

則可將權(quán)值系數(shù)的判斷改寫成如下過程:

(1)選擇權(quán)值系數(shù)αi和βi。若取完所有值,結(jié)束程序。

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

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

圖1 3×3階遞歸擴散層權(quán)值系數(shù)算法流程

3.3 通用模型的建立

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

圖2 遞歸擴散層權(quán)值系數(shù)算法流程

遞歸擴散層權(quán)值系數(shù)實現(xiàn)算法的偽代碼描述如下:

3.4 程序?qū)崿F(xiàn)及仿真結(jié)果

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

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

通過程序?qū)崿F(xiàn)得到了權(quán)值系數(shù)的仿真結(jié)果,在整個搜索空間中,當s=3時,有196種滿足條件的分支數(shù)達到4的權(quán)值系數(shù)組合,當s=4時,有1 634種滿足條件。對其進行整理,分別得到2階、3階、4階遞歸擴散層的仿真結(jié)果的部分生成式,如表1所示。

表1 低階遞歸擴散層權(quán)值系數(shù)仿真結(jié)果

4 結(jié)束語

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

［1］ 楊 波.現(xiàn)代密碼學［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擴散層的分析及改進方案設(shè)計［J］.計算機工程與應(yīng)用,2009,45(36):12-14.

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

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

［7］ 李瑞林,熊 海,李 超.基于循環(huán)移位和異或運算的對合線性變換研究［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-置換的分支數(shù)研究［J］.小型微型計算機系統(tǒng),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］ 胡予濮,張玉清,肖國鎮(zhèn).對稱密碼學［M］.北京:機械工業(yè)出版社,2002.

［12］ 譚浩強.C程序設(shè)計［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

中文引用格式:毛 明,楊 譜,李旭飛.遞歸擴散層的權(quán)值系數(shù)計算方法［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.