一類正形置換的差分分析*

白淑君，張 欣

（海軍計算技術研究所，北京 100841）

一類正形置換的差分分析*

白淑君，張 欣

（海軍計算技術研究所，北京 100841）

正形置換是一類完全映射，也是一種特殊的布爾置換。閱讀大量文獻，探討正形置換的構造問題和相關性質的研究現狀，分析利用布爾函數簇構造的正形置換的差分轉移概率能達到的最大值及最小值，給出這種構造方法所構造的n元t次正形置換的非平凡的差分轉移概率P的一個共同特點，即1/2n-3≤P≤(2t-1-1)/2t-1，討論顯示這類正形置換有良好的代數次數，并且代數免疫度為1。需注意的是，為了抵抗代數攻擊，這類正形置換不能直接應用到密碼系統中。

t次正形置換；非平凡的差分轉移概率；布爾函數簇；代數次數；代數免疫階

0 引 言

正形置換是一類完全映射，也是一種特殊的布爾置換。它具有良好的密碼學特性，在密碼設計和分析中應用廣泛，已成為分組密碼和序列密碼設計中的一類基礎置換[1-2]。自文獻[3]于1995年公開將正形置換的理論用于密碼算法設計以來，正形置換的研究迅速成為熱點。國內外學者對整形置換進行了大量研究，給出了許多重要的結果[3-26]。

正形置換的構造問題是正形置換研究中的一項重要內容，國內外學者對此進行了大量討論，給出了許多重要結論。文獻[4]給出了由n-2元正形置換構造n元正形置換的級聯迭代構造方法，并給出了相應的計數結果；文獻[5]提出了一種關于正形置換的布爾函數簇構造方法；文獻[6]通過正形矩陣對線性正形置換進行研究，給出了線性正形置換計數的遞推公式；文獻[7]基于m1（≥2）元正形置換和m2（≥2）元正形置換構造m1+m2元正形置換，給出了n（≥5）元正形置換的計數下界；文獻[8]在研究正形置換與正形拉丁方性質的基礎上，結合正形置換和正形拉丁方之間的聯系，利用正形拉丁方的一個簡潔的遞歸形式，得出正形置換的一種構造方法和正形置換的界的一個估計；文獻[9]利用對角正形矩陣的特性以及布爾函數序列構造了一批正形置換；文獻[10]利用有限群的理論探討了正形置換的構造問題；文獻[18]給出由n元正形置換構造n+1元正形置換的新方法，該方法利用正形拉丁方An的一個截集及其補序截集，擴展得到正形拉丁方An+1的一個復合截集，并由此構造出正形拉丁方An+1的截集。文獻[23]提出了正形置換環結構的概念，研究了正形置換環結構的性質，得到了一種在適當條件下由兩個沒有相同置換點的n元正形置換來構造一個n+1元正形置換的方法。文獻[24]則給出了一種由兩個n-2元正形置換構造一個n元正形置換的迭代方法，并證明該方法構造的正形置換與已知迭代構造方法所構造的正形置換不同。此外，還證明了所構造的n元正形置換兩兩不同。最后，在已知正形置換基礎上，結合一類特殊正形置換，對所構造的新n元正形置換進行了計數。文獻[26]基于正形置換與正形拉丁方截集之間的一一對應關系，研究正形置換的構造，給出n元正形置換之間的一個等價關系，由此在n元正形置換集合內劃分等價類，在等價類范圍內構造更多的復合截集，并提出基于n元正形置換構造n+1元正形置換的新方法。

盡管人們對正形置換的構造問題已經得到諸多結果，但由于正形置換的數量非常大，目前它的結構還沒有被完全搞清楚。所以，對正形置換的性質進行研究也十分必要。文獻[5]提出了一種關于正形置換的布爾函數簇構造方法。基于這種方法，文獻[4]提出了一種新的正形置換的級聯迭代構造方法。對于正形置換的其他構造方法所得結果都可以用文獻[4]的方法進行級聯迭代構造，從而構造出更多的正形置換。同時，正形置換又是一類特殊的布爾置換。為衡量根據正形置換的布爾函數簇構造方法所構造的正形置換抗差分攻擊能力的強弱，對其差分轉移概率可能達到的最大值及最小值進行分析，并給出這種構造方法所構造的正形置換的非平凡的差分轉移概率的一個共同特點。目前，關于布爾函數的密碼準則主要有平衡性、代數次數和代數免疫階等，其中代數免疫階主要是衡量函數的抗代數攻擊的能力。文中將重點討論此類正形置換的一些密碼學性質，包括代數次數和代數免疫階。

1 預備知識

設n是一個正整數，F2為二元域，是一個基于F2的n維線性空間。一個n元布爾函數f(x)是從到F2的一個映射。

因為每個yi都是x=(x1,x2,…,xn)的函數，記yi=fi(x)=fi(x1,x2,…,xn)。于是，上述映射便可用m個布爾函數f1, f2,…, fm來表示，記為：

在多輸出函數φ(x)=( f1(x),…, fm(x))中，當n=m時，φ(x)就成為上的變換。若φ(x)還是一個單射，則φ(x)便成為一個置換。

下面介紹正形置換的定義。

定義1 設P(x)=( f1, f2,…, fn)是上的一個n元布爾置換，若滿足也是上的一個n元布爾置換，則稱P(x)是上的一個n元正形置換。

則稱Pf(α→β)為f(x)的差分轉移概率。

定義3 若某一差分轉移概率P滿足0＜P＜1，則稱此差分轉移概率為非平凡的差分轉移概率。

定義4 多輸出函數的代數次數：設F(x)=( f1(x), f2(x),…, fm(x))是到的多輸出函數，令：

則稱D(F)為F(x)的代數次數。

定義5 布爾函數f的代數免疫度：設f是布爾函數，把使得fg=0的布爾函數g稱為f的零化子。特別地，g=0稱為f的平凡零化子。若g≠0，則稱g為f的非平凡零化子，記做An( f )={g | fg=0}。于是AI(f)=min{?(g)|g≠0,g∈An( f )∪An( f+1)}稱為布爾函數f的代數免疫度，即f和f+1的最低次非平凡零化子的次數。特別地，常值函數f=0和f=1的代數免疫度為0。

為了避免代數攻擊，要求所給的布爾函數的代數免疫階越高越好。但是，文獻[27]證明，對任意的n元布爾函數，有其中，表示不小于x的最小整數

定義6 置換的代數免疫度：設F(x)=(f1(x), f2(x),…, fm(x))是上的一個置換，則稱：

是置換F(x)的代數免疫度。

2 主要結論

文獻[4]提出了一種關于正形置換的布爾函數簇構造方法，描述如下：

引理1[4]設h2(x3, x4,…,xn)為n-2元布爾函數，h3(x4,…,xn)為hn-1(xn)元布爾函數，…，hn-1(xn)為1元布爾函數。令：

則F(x)=( f1, f2,…, fn)為正形置換。

定義7 設hi=hi(xi+1,…,xn),2≤i≤n-1是引理1中的n-i元布爾函數，記t=max{deg(hi)}，則稱引理1中正形置換P(x)為t次正形置換。

引理2 設f(x)是m元r次布爾函數，記：

令M=max{t1,t2}，則M的最大值為

證明：不失一般性，我們考慮情形t1＞t2。

由布爾函數小項表示的含義可知，小項的數目與其函數值為1的數目相同。因此，小項數目越多，f(x)取值為1的情況越多。下面討論f(x)的小項數目最多能達到多大。

由于f(x)的次數為r，不妨設其一個r次項為x1x2…xr。在f(x)的小項中，若有x1x2…xrY這種形式（其中，Y是中的任意m-r項的組合），則當Y跑遍的所有2m-r種情況時，小項的數目達到最多，且仍然滿足最高次項次數為r。同樣，在f(x)的小項中，若有這種形式，則仍然在Y跑遍的所有2m-r種情況時，滿足要求。

證畢。

定理8 在正形置換的布爾函數簇構造法中，設P是n元t次正形置換對應的非平凡最大差分轉移概率，則P≤(2t-1-1)/2t-1。

證明：在正形置換的布爾函數簇構造法中，令F(x)=( f1,…, fn)。?α∈F2n/{0}，若α=(α1,…,αn)，則α所對應的差分形式為：

其中c1,…,cn,d∈F2。

再令：

同時，不妨設h2(x)的最高次數為t次，則deg(g2)=t-1，且t≤n-2。由于此時差分對應的形式為(c1,c2,c3⊕g2,…，cn-1⊕gn-2,cn)，因此要使差分轉移概率盡量大，只需以上差分對應的x的個數盡量多，即(g2,…, gn-2)的某種取值所對應的x的數目盡量多。

由于g2是n-2元t-1次布爾函數，由引理2知：對x=(x2,…, xn)∈F2n-1而言，g2取某個值所對應的x的數目最大為因此(g2,…,gn-2)取某種值所對應的x的數目最大為2n-t-1(2t-1-1)，故此時差分轉移概率為：

若最高次項在g3中，則對g3進行同樣的分析可知：對而言，g3取某個值所對應的x的數目最大為由于g3中不含變量x1,x2和x3，因此此時差分轉移概率為：

由此不難推出，t次項出現在g2,…, gn-2中任意一個時，差分轉移概率P均滿足P≤(2t-1-1)/2t-1。

證畢。

定理9 在正形置換的布爾函數簇構造法中，所有非平凡的差分轉移個數都是8的倍數。

式中l是某個正整數。

因此，在正形置換的布爾函數簇構造法中，所有非平凡的差分轉移個數都是8的倍數。

證畢。

由定理2可得出以下推論：

推論 當n≥4時，若正形置換有非平凡的差分轉移概率，則最小的非平凡差分轉移概率為8/2n=1/2n-3。證畢。

定理10 在正形置換的布爾函數簇構造中，其代數次數為min{n1,n2+1}。

證明：設兩個n-2元正形置換P1=[g1,…,gn-2]和P2=[h1,…,hn-2]的代數次數分別為：n1=deg(P1)≥1和n2=deg(P2)≥1。由多輸出函數代數次數的定義可知：

進一步展開，有：

是關于置換P1=[g1,…,gn-2]的一個線性組合，因此，deg(L1)≥n1。

等式的第二行記做：

綜括號中是關于置換P1=[g1,…,gn-2]的一個線性組合，因此綜括號中的代數次數≥n1，乘以xn后，deg(L2)≥n1+1。

同理，記等式的第三行為L3，與L2的分析相同，得到deg(L3)≥n2+1。

第四行為一次項忽略。

因此，置換P的代數次數為：min{n1,n2+1}。

證畢。

定理11 在正形置換的布爾函數簇構造中，其代數免疫度為1。

證明：由定義6可知，置換P的代數免疫度為：

令u=(u1,u2,…,un)=(0,0,…,0,1,1,0)代入式（*），可以得到置換P關于u的線性組合：

這是一個線性函數，因此代數免疫度為1。

證畢。

3 結 語

研究正形置換的性質在密碼學中具有重要的意義。本文分析利用布爾函數簇構造的正形置換的差分轉移概率可能達到的最大值及最小值，給出這種構造方法所構造的n元t次正形置換的非平凡的差分轉移概率P的一個共同特點：1/2n-3≤P≤(2t-1-1)/2t-1，同時討論此類正形置換的一些密碼學性質，包括代數次數和代數免疫階。討論結果顯示，這類正形置換的代數次數與用于構造的兩個函數相關，且其代數免疫階為1。為了抵抗代數攻擊，這類正形置換不能直接應用到密碼系統中。

[1] CARLET C.Vectorial Boolean Functions for Cryptography,Chapter of the Monography Boolean Models and Methods in Mathematics,Computer Science, and Engineering[M].Cambridge:Cambridge University Press,2010.

[2] FENG D G,FENG X T,ZHANG W T,et al.Loiss:A Byte-Oriented Stream Cipher[C].International Workshop,2010(6639):109-125.

[3] Mittenthal L.Block Substitutions Using Orthomorphic Mappings[J].Advances in Applied Mathematics,1995,16(01):59-71.

[4] 溫巧燕,鈕心忻,楊義先.現代密碼學中的布爾函數[M].北京:科學出版社,2000:178-180. WEN Qiao-yan,NIU Xin-xin,YANG Yi-xian.Boolean Functions in Modern Cryptography[M].Beijing:Science Press,2000:178-180.

[5] 馮登國,劉振華.關于正形置換的構造[J].通信保密,1996,66(02):61-64. FENG Deng-guo,LIU Zhen-hua.On the Construction of Orthomorphic Permutations[J].Communication Security,1996,66(02):61-64.

[6] DAI Zong-duo,Golomb S W.Generating All Linear Orthomorphisms without Repetition[J].Discrete Mathema tics,1999,205(01-03):47-55.

[7] HUANG Gen-xun,ZHU Yue-fei.The Lower Bound for the Numbers of Orthomorphic Permutations and a Method to Construct Them[C].Beijing:Proceeding of China Crypt'2000,2000:27-30.

[8] 王鵬.正形置換的一種構造方法[J].中南民族學院學報:自然科學版,2001,20(01):50-53. WANG Peng.A Method of Constructing Orthomorphic Permutation[J].Journal of Central South University(Natural Science Edition),2001,20(01):50-53.

[9] 李志慧,李瑞虎,李學良.正形置換的構造[J].陜西師范大學學報:自然科學版,2002,30(04):18-22. LI Zhi-hui,LI Rui-hu,LI Xue-liang.Construction of the Orthomorphic Permutation[J].Journal of Shaanxi Normal University:Natural Science,2002,30(04):18-22.

[10] 亢保元.密碼體制中的正形置換的構造與記數[J].電子與信息學報,2002,24(09):1294-1296. KANG Bao-yuan.Structure and Notation of Orthomorphic Permutations in Cryptosystems[J].Journal of Electronics and Information Counter,2002,24(09):1294-1296.

[11] 朱華安,謝端強.關于密碼體制中正形置換的幾個結果[J].應用科學學報,2004,22(02):132-135. ZHU Hua-an,XIE Duan-qiang.Some Results of Orthomorphic Permutations in Cryptosystems[J].Journal of Applied Science,2004,22(02):132-135.

[12] Harald N,Arne W.Cyclotomic R-orthomorphisms of Finite Fields[J].Discrete Mathematics,2005,295(01-03):161-171.

[13] ZHAO Ya-qun,WANG Jue.Walsh Spectral Characteristics and the Auto-correlation Function Characteristics of Forming Orthomor-phic Permutations of Multi-output Functions[J].Wuhan University Journal of Natural Sciences,2006,11(06):1895-1898.

[14] 常祖領,柯品惠,莫驕等.F2n上的正形置換[J].北京郵電大學學報,2006,29(01):115-118. CHANG Zu-ling,KE Pin-hui,MO Jiao,et al.Orthomorphic Permutation on F2n[J].Journal of Beijing University of Posts and Telecommunications,2006,29(01):115-118.

[15] 任金萍,呂述望.正形置換的枚舉與計數[J].計算機研究與發展,2006,43(06):1071-1075. REN Jin-ping,LV Shu-wang.Enumeration and Enumeration of Orthomorphic Permutations[J].Computer Research and Development,2006,43(06):1071-1075.

[16] 徐海波,劉海蛟,荊繼武等.一種正形置換的逐位遞增構造方法[J].中國科學院研究生院學報,2006,23(02):251-256. XU Hai-bo,LIU Hai-jiao,JING Ji-wu,et al.A Positive Permutation of Bit-wise Incremental Construction Method[J].Graduate School of Chinese Academy of Sciences,2006,23(02):251-256.

[17] 周建欽.關于正形置換的構造[J].華中科技大學學報:自然科學版,2007,35(02):40-42. ZHOU Jian-qin.About the Construction of the PositivePermutation[J].Huazhong University of Science and Technology(Natural Science Edition),2007,35(02):40-42.

[18] 鄭浩然,張海模,崔霆等.一種新的正形置換構造方法[J].電子與信息學報,2009,31(06):1438-1444. ZHENG Hao-ran,ZHANG Hai-mo,CUI Ting,et al.A New Positive Permutation Constructor[J].Electronics & Information Technology,2009,31(06):1438-1444.

[19] 鄭浩然,張海模,樊東.對一個正形置換構造方法的修正及其計數結果的改進[J].通信學報,2009,30(12):45-57. ZHENG Hao-ran,ZHANG Hai-mo,FAN Dong.On a Regular Permutation Correction Method of Constructing and Counting Improve Results[J].Communicatio ns,2009,30(12):45-57.

[20] ZHOU J Q.A Note on the Constructions of Orthomorphic Permutations[J].International Journal of Network Security,2010,10(01):57-61.

[21] LIU Q,ZHANG Y,CHEN C,et al.Construction and Counting Orthomorphism based on Transversal[C]// In 2008 International Conference on Computational Intelligence and Security.Suzhou,2008:369-373.

[22] HUANG G X,ZHU Y F.The Lower Bound for the Numbers of Orthonorphic Permutations and a Method to Construct Them[C].Beijing,2000:27-30.

[23] 王月,鄭浩然,李坦.正形置換的級聯構造方法[J].信息工程大學學報,2013,14(03):269-274. WANG Yue,ZHENG Hao-ran,LI Tan.Method of Cascade Construction of Orthomorphic Permutations[J].Journal of Information Engineering University,2013,14(03):269-274.

[24] 張鳳榮,胡予濮,馬華等.正形置換的迭代構造與計數[C].鄭州:2011第四屆中國計算機網絡與信息安全學術會議(CCNIS2011),2011. ZHANG Feng-rong,HU Yu-pu,MA Hua.Orthomorphic Permutation of the Iterative Construction and Counting[C].Zhengzhou:2011 4th China Computer Network and Information Security Conference CCNIS2011,2011.

[25] 郭瑞,金晨輝.Lai-Massey結構偽隨機特性研究[J].電子與信息學報,2014,36(04):828-833. GUO Rui,JIN Chen-hui.Lai-Massey Structure Characteristics of the Pseudo-random[J].Journal of Electronics and Information,2014,36(04):828-833.

[26] 廖大見，唐元生．正形置換的一種新構造與計數[J]．通信學報,2010,31(8A):70-75. LIAO Da-jian,TANG Yuan-sheng. A New Construction of Orthomorphic Permutations and Counting [J].Journal on Communications,2010,31(8A):70-75.

[27] Courtois N,Meier W.Algebraic Attacks on Stream Ciphers with Linear Feedback[C].Berlin:Biham E ed. Advances in Cryptology-EuroCrypt'2003,2003:345-359.

Differential Cryptanalysis of an Orthormophic Permutation

BAI Shu-jun, ZHANG Xin
(Navy Institute of Computing Technology, Beijing 100841,China)

Orthomorphic permutation is a complete mappings, and a special Boolean permutation as well. By reading a lot of literatures, exploring the research status of structural problems and related properties of orthomorphic permutations, and analyzing the maximal and minimal values of the differential transitional probability of the orthormophic permutation constructed with Boolean functions class, the common characteristics of nontrivial differential transitional probability P of this t-degree orthormophic permutation in n variables are given, that is, 1/2n-3≤P≤(2t-1-1)/2t-1.The study indicates that this orthormophic permutation is of high algebraic degree,and has an algebraic immunity of 1. However, it should be noticed that this permutation chould not be applied in cryptosystem directly for resisting algebraic attacks.

t-degree orthormophic permutation; nontrivial differential transitional probability; Boolean functions class; algebraic degree; algebraic immunity

TN918.1

A

1002-0802(2016)-07-0896-06

10.3969/j.issn.1002-0802.2016.07.020

白淑君（1976—），女，碩士，高級工程師，主要研究方向為信息安全；

2016-03-16;

2016-06-17 Received date:2016-03-16;Revised date:2016-06-17

張 欣（1979—），男，碩士，高級工程師，主要研究方向為信息安全。