2次旋轉(zhuǎn)對(duì)稱布爾函數(shù)的兩個(gè)密碼學(xué)性質(zhì)﹡

黃景廉， 王 卓

（西北民族大學(xué) 電氣工程學(xué)院，甘肅 蘭州 730030）

0 引言

布爾函數(shù)在密碼系統(tǒng)的設(shè)計(jì)中有著重要的應(yīng)用，密碼系統(tǒng)的安全性取決于布爾函數(shù)的密碼學(xué)性質(zhì)，如非線性度、代數(shù)次數(shù)、相關(guān)免疫性、擴(kuò)散性、線性結(jié)構(gòu)、平衡性、代數(shù)免疫性等[1-3]。對(duì)布爾函數(shù)密碼學(xué)性質(zhì)的研究是序列密碼、分組密碼、Hash函數(shù)、數(shù)字簽名體制、數(shù)據(jù)加密技術(shù)的關(guān)鍵內(nèi)容，其已成為密碼安全問(wèn)題的一個(gè)重要研究領(lǐng)域。 2003年，法國(guó)密碼學(xué)家Nicolas和Wilimeier提出基于線性反饋移位寄存器的代數(shù)攻擊方法[4]。Courtois和Meier等學(xué)者隨之提出抵抗代數(shù)攻擊的布爾函數(shù)代數(shù)免疫性和代數(shù)免疫階 ()AI f的概念[4]。對(duì)布爾函數(shù)這一新性質(zhì)的研究[5]更是當(dāng)前密碼體制安全性研究的熱點(diǎn)。

旋轉(zhuǎn)對(duì)稱布爾函數(shù)是密碼學(xué)中已有良好實(shí)際應(yīng)用的密碼學(xué)函數(shù)，用于某些密碼算法，如 MD4、MD5和HAVAL的快速實(shí)現(xiàn)中。在1999年由Pieprzyk和Qu提出[6]后一直受到重視，一直在對(duì)其進(jìn)行深入研究[7-15]。文中將對(duì)旋轉(zhuǎn)對(duì)稱布爾函數(shù)、旋轉(zhuǎn)對(duì)稱H布爾函數(shù)的平衡性和代數(shù)免疫性展開研究，以得出一些有用的結(jié)果。

1 預(yù)備知識(shí)

定義1 設(shè)nI+∈，對(duì)任意(2)nGF,kI+∈,且,其中：

2次旋轉(zhuǎn)對(duì)稱H布爾函數(shù)已具有擴(kuò)散性，在后面的討論中，還會(huì)涉及其它次數(shù)次的旋轉(zhuǎn)對(duì)稱布爾函數(shù)，故給出如下定義。

2 旋轉(zhuǎn)對(duì)稱布爾函數(shù)的性質(zhì)

下面討論旋轉(zhuǎn)對(duì)稱布爾函數(shù)的一個(gè)性質(zhì)。

3) 在旋轉(zhuǎn)對(duì)稱布爾函數(shù)中，存在2次旋轉(zhuǎn)對(duì)稱平衡H布爾函數(shù)。

3) 由式(1)，便有：

又有：

于是由式(4)、式(5)便可推得：

故由式(4)知，存在旋轉(zhuǎn)對(duì)稱平衡H布爾函數(shù)。

進(jìn)一步還可推出：當(dāng) N1> N2，且，則必有只是這種隨維數(shù)的增大向 2n-1的逼近是很慢的，已無(wú)密碼學(xué)上的實(shí)際意義，不再以極限來(lái)描述。

推論2 奇數(shù)n維2次旋轉(zhuǎn)對(duì)稱H布爾函數(shù)中，存在平衡布爾函數(shù)；偶數(shù)n維2次旋轉(zhuǎn)對(duì)稱H布爾函數(shù)不是平衡布爾函數(shù)。

下面討論旋轉(zhuǎn)對(duì)稱布爾函數(shù)的代數(shù)免疫性。

i

(21)ik

+

由式(7)、式(9)，便知有：

于是

2) 和1) 相似的道理，必有：

故

推論 3 若旋轉(zhuǎn)對(duì)稱布爾函數(shù) ()f x只由完全純奇數(shù)次布爾函數(shù)的和構(gòu)成，即

3 結(jié)語(yǔ)

文中給出了旋轉(zhuǎn)對(duì)稱布爾函數(shù)、完全純k次布爾函數(shù)的定義，討論了旋轉(zhuǎn)對(duì)稱布爾函數(shù)的性質(zhì)，給出了相應(yīng)的證明，得出 2次旋轉(zhuǎn)對(duì)稱布爾函數(shù)對(duì)平衡性的相容性、代數(shù)免疫階的結(jié)果，這些結(jié)果將為進(jìn)一步深入研究旋轉(zhuǎn)對(duì)稱布爾函數(shù)、旋轉(zhuǎn)對(duì)稱H布爾函數(shù)的相關(guān)免疫性、代數(shù)免疫性、平衡性、重量分布范圍，平衡性、相關(guān)免疫性與維數(shù)的關(guān)系，以及多種密碼學(xué)性質(zhì)的相容性等提供方便。

[1] 齊云,劉玉孝.相關(guān)免疫函數(shù)和Hamming重量之間的關(guān)系[J].通信技術(shù),2008,41(12):363-365.

[2] 黃景廉,張椿玲.一次擴(kuò)散布爾函數(shù)的一些密碼學(xué)性質(zhì)[J].通信技術(shù),2012,45(03):43-45.

[3] 蔡海,周亮.對(duì)AES算法的S盒布爾函數(shù)分析[J].信息安全與通信保密,2008(04):77-79.

[4] COURTOIS N, MEIER W. Algebraic Attacks on Stream Ciphers with Linear Feedback[C]//Eurocrypt 2003,Lecture Notes in Computer Science 2656. Berlin:Springer-Verlag,2003:345-359.

[5] 董新鋒,張鳳榮,譙通旭,等.具有最優(yōu)代數(shù)免疫階的1階彈性函數(shù)的構(gòu)造[J].信息安全與通信保密,2010(12):112-115.

[6] PIEPRZYK J,QU C.Fast Hashing and Rotationsymmetric Functions[J].Journal of Universal Computer Science,1999,5(01):20-31.

[7] CUSICK W,STANICA P,MAITRA S.Fast Evaluation,Weight and Nonlinearity of Rotation Symmetric Functions[J].Discrete mathematics,2002,258(1-3):289-301.

[8] STANICA P,MAITRA S.Rotation Symmetric Boolean Functions-count and Cryptographic Properties[J].Discrete Applied Mathematics, 2008(156):1567-1580.

[9] STANICA P,MAITRA S.Construction of Rotation Symmetric Boolean Functions with Optimal Algebraic Immunity[J]. Computer Systems, 2009, 12(03):267-284.

[10] 張鵬,付紹靜,屈龍江,等.平衡旋轉(zhuǎn)對(duì)稱布爾函數(shù)的計(jì)數(shù)[J].應(yīng)用科學(xué)學(xué)報(bào),2012,30(01):45-51.

[11] FU S,QU L,LI C,et al.Balanced Rotation Symmetric Boolean Functions with Maximum Algebraic Immunity[J].Information Security,IET, 2011, 5(02):93-99.

[12] 袁書宏,厲曉華,鄒池佳.關(guān)于旋轉(zhuǎn)對(duì)稱布爾函數(shù)性質(zhì)之研究[J].浙江大學(xué)學(xué)報(bào),2011,38(01):55-57.

[13] 熊曉雯,魏愛(ài)國(guó),張智軍.構(gòu)造具有良好密碼學(xué)性質(zhì)的旋轉(zhuǎn)對(duì)稱布爾函數(shù)[J].電子與信息學(xué)報(bào),2011,38(01):55-57.

[14] 王斌,張習(xí)勇,陳衛(wèi)紅.一類4次旋轉(zhuǎn)對(duì)稱布爾函數(shù)的漢明重量和非線性度[J].數(shù)學(xué)學(xué)報(bào),2012,55(04):55-57.[15] 董德帥,李超,屈龍江,等.偶變?cè)狹AI旋轉(zhuǎn)對(duì)稱布爾函數(shù)[J].國(guó)防科技大學(xué)學(xué)報(bào),2012,34(04):85-89.