一类正形置换的差分分析*

白淑君，张 欣

（海军计算技术研究所，北京 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—），男，硕士，高级工程师，主要研究方向为信息安全。