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

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

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

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

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

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

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

1 概述

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

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

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

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

2.1 擴(kuò)散層分支數(shù)

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

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

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

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

2.2 最優(yōu)擴(kuò)散層

對(duì)于擴(kuò)散層安全性能一般用分支數(shù)這個(gè)量化指標(biāo)來(lái)進(jìn)行衡量。當(dāng)擴(kuò)散層變換的分支數(shù)達(dá)到最大時(shí),則稱(chēng)該擴(kuò)散層是最優(yōu)擴(kuò)散層。

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

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

2.3 遞歸擴(kuò)散層定義

定義3 對(duì)于一個(gè)s個(gè)字xi輸入的擴(kuò)散層D,輸出為s個(gè)字yi,稱(chēng)這樣的擴(kuò)散層為遞歸擴(kuò)散層,如滿(mǎn)足以下條件:

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

這類(lèi)擴(kuò)散層D可以用下面的程序表示,其中,L是個(gè)線(xiàn)性函數(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

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

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

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

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

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

3.1 3×3階遞歸擴(kuò)散層模型

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

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

合并同類(lèi)項(xiàng),得:

將y0代入y1,得:

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

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

下面對(duì)αi和βi進(jìn)行取值:

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

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

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

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

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

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

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

3.3 通用模型的建立

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

［1］ 楊 波.現(xiàn)代密碼學(xué)［M］.北京:清華大學(xué)出版社,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］ 楊宏志,韓文報(bào),沈 勇.AES擴(kuò)散層的分析及改進(jìn)方案設(shè)計(jì)［J］.計(jì)算機(jī)工程與應(yīng)用,2009,45(36):12-14.

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

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

［7］ 李瑞林,熊 海,李 超.基于循環(huán)移位和異或運(yùn)算的對(duì)合線(xiàn)性變換研究［J］.國(guó)防科技大學(xué)學(xué)報(bào),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］ 韓海清,張煥國(guó).分組密碼P-置換的分支數(shù)研究［J］.小型微型計(jì)算機(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］ 胡予濮,張玉清,肖國(guó)鎮(zhèn).對(duì)稱(chēng)密碼學(xué)［M］.北京:機(jī)械工業(yè)出版社,2002.

［12］ 譚浩強(qiáng).C程序設(shè)計(jì)［M］.北京:清華大學(xué)出版社,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-),男,教授,主研方向:信息安全,密碼學(xué);楊 譜、李旭飛,碩士。

2013-11-26

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

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