不可能差分性质更优的动态S盒构造方法

胡志华 颜硕 熊宽江

摘要：利用有限域的可逆变换与仿射变换产生S盒的思想，提出通过改变仿射变换矩阵中的行来生成动态S盒。分析了该方法生成单个S盒的密码学性质，实验结果显示单个S盒的密码学性质均达到高级加密标准中S盒的安全性；同时也分析了该方法生成动态S盒的动态差分概率、动态线性概率、动态非线性度、动态代数次数和不可能差分个数，理论分析表明该方法生成动态S盒均有较好的密码学性质；通过实验检验可以得出该方法生成的动态S盒具有很好的动态非线性度、动态差分和不可能差分性；而从分析该方法生成动态S盒的硬件实现效率可以看出，该方法具有较好的硬件实现效率。

关键词：行变换；非线性；差分均匀度；不可能差分；动态S盒

中图分类号：TP309 文献标志码：A

Abstract： Based on the idea of using reversible transformation and affine transformation to generate Sbox， a method to produce dynamic Sbox by changing the rows of affine transformation array was proposed. The cryptography properties of single Sbox were analyzed. The experimental results show that the cryptography properties of single Sbox achieve the security standard of Sbox of AES. Moreover， the dynamic differential probability， dynamic linear probability， dynamic nonlinear degree， dynamic algebra times and impossible differential numbers of the dynamic Sbox produced by the proposed method were analyzed. Theoretical analysis shows that the Sbox produced by proposed method possesses good cryptography properties， and experiments also prove that the Sbox so produced has good dynamic nonlinear degree， dynamic differential and impossible differential properties. Finally， by analyzing the hardware implementation efficiency of the generation of the dynamic Sbox， the proposed method has high hardware implementation efficiency.

Key words：row transformation； nonlinearity； difference uniformity； impossible difference； dynamic Sbox

0 引言

分析分组密码加密算法安全性是密码学的一个重要研究方向，S盒是很多加密算法的唯一非线性部分，所以S盒的密码学性质将决定整个密码算法的安全强度。目前S盒的设计主要采用数学函数构造和随机构造等方式。数学函数构造的S盒能从理论上证明S盒的密码特性，更能使用户相信没有陷门。

很多成熟的分组密码加密算法都采用有限域上乘法求逆变换构造S盒[1]，如高级加密标准（Advanced Encryption Standard， AES）、SMS4等。但是在这些加密算法中， S盒在整个加密算法中都是固定不变的。从理论的角度分析，如果在加密算法中动态使用S盒，将会提高密码算法的分析难度。目前，已有一些针对分组密码动态选择S盒及其差分性质的研究。2007年，邱劲等[2]通过遍历混沌映射，提出基于混沌映射的动态S盒的构造方法。2008 年，曹明等[3]通过两次插入遗传算法，提出了一种基于蚁群算法的S盒构造。2011年，Stoianov[4]构造了与 AES中S盒性质相似的两个新的S盒，并在加解密过程中与AES的S盒，逆S盒一起动态选择使用。2014年，王海龙等[5]将多进制与S盒进行组合，形成多进制组合多类S盒设计思想，提出利用多进制组合快速构造S盒的AES算法。不可能差分是最近几年提出的一种有效攻击分组加密算法的攻击方法，该攻击方法与S盒的差分和不可能差分性质有关。2010年，Dunkelman等[6]构造了一个4轮的差分特征，成功分析8轮AES_192和AES_256。2013年，胡志华等[7]通过分析高级加密标准AES的四轮内部加密特征，推导出一个新的4轮差分路径，该路径存在的可能性为2-30，在该性质的基础上利用不可能差分分析方法，分析了8轮AES_128。2014年，刘国强等[8]通过对有限域与仿射变换复合得到动态S盒并分析这类S盒的不可能差分性质。2009年陈利科等[9]通过改进密钥与相关的动态S盒和动态P盒两种基本密码组件结合方式，提出一种基于动态S盒和动态P盒的快速分组密码算法——DSP（Digital Signal Processor）。2014年，申兵等[10]通过分析动态S盒的差分与线性性质规律，提出了动态S盒密码性质的研究。以及文献[11-17]提出的不同构造动态S盒的方法与相关动态S盒的性质研究。上述的这些研究成果存在一个共同的缺陷，生成的动态S盒在具体的加解密实现中不便于实现。

本文提出一种变换仿射变换矩阵中的行来等价产生动态S盒的方法。利用行变换可以生成28个动态S盒，对其动态差分概率、动态线性概率、动态非线性度、动态代数次数进行计算分析，得出对仿射变换矩阵通过行变换得到的动态S盒具有很好的动态差分和非线性等方面的性质。本文还随机选择8个动态S盒对其差分概率分布和不可能差分个数进行分析，得出通过本文方法生成动态S盒比随机选取动态S盒性质更优。

由上述定义可知，描述整体动态S盒密码性质的动态指标，是由组成动态S盒的各单个S盒密码性质的数学期望决定的，而且控制参数服从均匀分布，因此动态S盒密码性质的动态指标也以引理1为界。数学期望描述了指标的平均水平，为了使密码性能更好，这些动态指标还应该满足动态差分概率、动态线性概率尽可能小，动态非线性度、动态代数次数尽可能大。

分析采用改变仿射变换中的矩阵A来生成不同S盒的密码学性质，可以采用上述定义中的方法测试生成动态S盒的性质，并与循环使用AES加密算法中S盒的动态密码学性质进行比较，结果如表4和表5所示。

从表4可以看出，随着m的增大单一动态S盒的动态差分概率、动态非线性度、动态代数次数的值并没有改变，但是动态线性概率随着m的增大而增大，说明动态S盒对线性概率影响明显。综合表4和表5，可以得到，随着m的增大多动态S盒的动态差分概率、动态非线性度、动态代数次数的值并没有削弱，而且可以看出动态线性概率的减小更加明显。

3 不可能差分性质分析与实验比较

3.1 不可能差分性质分析

不可能差分是近年来的一个研究热点[22]，在分组密码中分析其安全性方面起着非常重要的作用。不可能差分的关键就是寻找不可能差分路径，本节将寻找不可能差分路径转化为差分概率与不可能差分个数的对应关系，分析不可能差分性质。

其差分概率的分析可以归结为在输入差分固定时，输出差分变动的平均差分概率的分析，不可能差分个数就与差分概率为0的差分对应。

3.2 不可能差分实验结果比较

在加密算法中到底用多少个动态的S盒最优到目前还没有一个具体的定义，但是文献[11]中指出盒子的数量小于8比较有利于硬件实现。利用定理1中的方法生成前8个动态S盒，让这些动态S盒成为差分路径上活动的S盒，然后对其最大差分概率和不可能差分对应个数进行分析。盒子数量3到8的不可能差分对应个数如表6，盒子数量1到8的动态差分概率分布情况如表7。

由表6可以看出随着m的增大，不可能差分的个数显著降低。不可能差分个数越少，证明在固定输入差分后，对应差分概率为0的输出差分可以在更大的范围内选择。通过表7可以看出，动态S盒的最大差分概率超过1（×2-7）的比例在不断减小，差分分布将没有明显大元素的特性，所以动态S盒要比单个S盒的不可能差分优。我们通过与文献[8]的对比可以发现，通过行变换改变仿射变换矩阵构造的动态S盒，得到的结果要好于文献[8]的构造方法。

3.3 硬件实现效率分析

密码算法中采用单个S盒的安全性已经受到质疑[7-11]，为了提升密码算法的安全性，部分算法中采用多S盒。目前关于多S盒的研究主要集中在生成方法和安全性方面，关于硬件执行的效率还是一个起步阶段。在文献[23]中总结了单S盒的硬件实现的最有效方法：一种是基于查找表的方法；一种是基于逻辑运算的方法。在文献[23]也指出高级加密标准（Advanced Encryption Standard， AES）中S盒的硬件实现效率非常高。本文构造动态S盒的核心是通过调整放射变换的行和列来得到新的S盒，其硬件执实现效率是单S盒的线性叠加，因此不论采用哪种硬件实现方法的效率不超过重复使用单S的效率。在文献[2，8]中的两种构造动态S盒的方法都存在一部分S盒的密码学性质不能达到最优，存在选择S盒等缺陷，其硬件的实现效率要高于使用重复使用单S盒的效率。如何提升多S盒的硬件执行效率将是下一步研究的目标。

4 结语

S盒是许多加密算法中的唯一的非线性部分，S盒的密码特性的好坏直接决定了密码算法的安全性。通过改变仿射变换矩阵，生成动态S盒，分析单个S盒的密码学特性，其各项指标和高级加密标准中使用的S盒一致，当把这些S盒动态使用时其动态密码学特性高于使用单个S盒；以使用8个动态S盒为例，通过实验计算发现除了代数次数没有发生变化，其他各项指标都优于使用单一S盒。使用动态S盒是一种能有效抵抗不可能差分分析的方法，最后分析了通过本文方法构造新的动态S盒的抵抗不可能差分攻击的性质更优，同时分析了该方法具有较好的硬件实现效率。

参考文献：

[1]冯登国，吴文玲，张文涛.分组密码的设计与分析[M].北京：清华大学出版社，2009：48-110.（FENG D G， WU W L， ZHANG W T. Design and Analysis of Block Cipher [M]. Beijing： Tsinghua University Press， 2009： 48-110.）

[2]邱劲，王平.基于混沌映射的动态S盒构造方法[J].计算机科学，2007，34（5）：89-91.（QIU J， WANG P. A method to construct dynamic Sbox based on chaotic map[J]. Computer Science， 2007， 34（5）： 89-91.）

[3]曹明，黄银峰，谷利泽，等.基于遗传蚁群算法的S盒构造[J].计算机应用研究，2008，25（5）：1553-1554. （CAO M， HUANG Y F， GU L Z， et al. Construction of Sboxes based on genetic and ant colony algorithm [J]. Application Research of Computers， 2008， 25（5）： 1553-1554.）

[4]STOIANOV N. One approach of using keydependent Sboxes in AES [C]// MCSS 2011： Proceedings of 4th International Conference on Multimedia Communications， Services and Security， Volume 149 of the series Communications in Computer and Information Science. Berlin： SpringerVerlag， 2011： 317-323.

[5]王海龙，孟繁军，张跃军，等.利用多进制组合快速构造S盒的AES算法设计[J].合肥工业大学学报（自然科学版），2014，37（4）：432-434. （WANG H L， MENG F J， ZHANG Y J， et al. AES algorithm design of SBox based on Mary hexadecimal conversion method [J]. Journal of Hefei University of Technology （Natural Science），2014，37（4）：432-434.）

[6]

DUNKELMAN O， KELLER N， SHAMIR A. Improved singlekey attacks on 8round AES192 and AES256 [C]// ASIACRYPT 2010： Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security， LNCS 6477. Berlin： SpringerVerlag， 2010： 158-176.

[7]胡志华，覃中平.一种新的8轮AES_128不可能差分分析[J].小型微型计算机系统，2013，34（9）：2111-2115. （HU Z H， QIN Z P. Novel method for impossible differential cryptanalysis of 8round AES128 [J]. Journal of Chinese Computer Systems， 2013， 34（9）： 2111-2115.）

[8]刘国强，金晨辉.一类动态S盒的构造与差分性质研究[J].电子与信息学报，2014，36（1）：74-81. （LIU G Q， JIN C H. Investigation on construction and differential property of a class of dynamic Sbox [J]. Journal of Electronics & Information Technology， 2014， 36（1）： 74-81.）

[9]陈利科，张润彤.一种基于动态S盒和动态P盒的快速分组密码算法——DSP[J].计算机科学，2009，36（2）：78-80. （CHEN L K， ZHANG R T. Novel software block cipher using dynamic Sbox and Pbox [J]. Computer Science， 2009， 36（2）： 78-80.）

[10]申兵，霍家佳.动态S盒的密码性质[J].通信技术， 2014， 47（12）： 1429-1433. （SHEN B， HUO J J. Cryptographic property of dynamic Sbox [J]. Communications Technology， 2014， 47（12）： 1429-1433.）

[11]殷新春，杨洁，谢立.密钥控制的多S盒Rijndeal算法[J].通信学报， 2007，28（9）：125-132. （YIN X C， YANG J， XIE L. Keycontrolled Rijndael algorithm with multiple Sboxes [J]. Journal on Communications， 2007， 28（9）： 125-132.）

[12]王文华，郑志明.基于可变S盒的随机加密方案[J].北京航空航天大学学报，2011，37（7）：811-816. （WANG W H， ZHENG Z M. Random encryption scheme based on variable Sboxes [J]. Journal of Beijing University of Aeronautics and Astronautics， 2011， 37（7）： 811-816.）

[13]MERKLE R C. Fast software encryption functions [C]// Proceedings of the Advances in Cryptology， LNCS 537. Berlin： SpringerVerlag， 1991： 477-501.

[14]SCHNEIER B. Description of a new variablelength key， 64bit block cipher[C]// Proceedings of the 1994 Cambridge Security Workshop on Fast Software Encryption， LNCS 809. Berlin： Springer， 1994： 191-204.

[15]NEDJAH N， DE MACEDO MOURELLE L. Designing substitution boxes for secure ciphers [J]. International Journal of Innovative Computing and Application， 2007， 1（1）： 86-91.

[16]TU C. Design of an improved method of Rijndael Sbox [C]// ICCIC 2011： Proceedings of the 2011 International Conference on Computing and Information， Volume 231 of the series Communications in Computer and Information Science. Berlin： SpringerVerlag， 2011： 46-51.

[17]CLARK J A， JACOB J L， STEPNEY S. The design of Sboxes by simulated annealing [J]. New Generation Computing， 2005， 23（3）： 219-231.

[18]WEBSTER A F， TAVARES S E. On the design of Sboxes[C]// CRYPTO 85 Advances in Cryptology. London： SpringerVerlag， 1986： 523-534.

[19]NYBERG K. Perfect nonlinear Sboxes [C]// EUROCRYPT 91： Proceedings of the 1991 Workshop on the Theory and Application of Cryptographic Techniques， LNCS 547. Berlin： SpringerVerlag， 1991： 378-386.

[20]温巧燕，钮心忻，杨义先.现代密码学中的布尔函数[M].北京：科学出版社，2000：147-152. （WEN Q Y， NIU X Q， YANG Y X. Boolean Function in Modern Cryptography [M]. Beijing： Science Press， 2000：147-152.）

[21]刘景伟，韦宝典，吕继强，等.AES S盒的密码特性分析[J]. 西安电子科技大学学报（自然科学版），2004，31（2）：255-259. （LIU J W， WEI B D， LYU J Q， et al. Analysis of the cryptographic properties of the AES Sbox [J]. Journal of Xidian University， 2004， 31（2）： 255-259.）

[22]吴文玲，张蕾.不可能差分密码分析研究进展[J].系统科学与数学，2008，28（8）：971-983. （WU W L， ZHANG L. The stateoftheart of research on impossible differential cryptanalysis [J]. Journal of Systems Science and Mathematical Sciences， 2008， 28（8）： 971-983.）

[23]杨红志，韩文报，赵龙.适用硬件实现的S盒构造方法[J].计算机应用，2010，30（3）：674-684. （YANG H Z， HAN W B， ZHAO L. Construction method of Sbox suitable for hardware implementation [J]. Journal of Computer Applications， 2010， 30（3）： 674-684.）