一种快速求解密码S盒差分均匀度下界的新方法  

New Method for Fast Computation the Low Bound of Differential Uniformity of Cryptographic S-Boxes

作　　者：蔡婧雯 韦永壮[1] 赵海霞[2] CAI Jing-wen;WEI Yong-zhuang;ZHAO Hai-xia(Guangxi Key Laboratory of Cryptography and Information Security,Guilin University of Electronic Technology,Guilin 541004,China;School of Mathematics and Computational Science,Guilin University of Electronic Technology,Guilin 541004,China)

机构地区：[1]桂林电子科技大学广西密码学与信息安全重点实验室,广西桂林541004 [2]桂林电子科技大学数学与计算科学学院,广西桂林541004

出　　处：《小型微型计算机系统》2023年第5期1081-1086,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61872103)资助;广西自然科学基金项目(2019GXNSFGA245004)资助;认知无线电与信息处理省部共建教育部重点实验室主任基金项目(CRKL180107)资助。

摘　　要：密码S盒是对称密码算法的核心部件,其代数性质通常决定着密码算法整体的安全强度.密码S盒的差分均匀度是度量其抵御差分密码分析的能力.对于n比特输入及n比特输出的密码S盒,传统求解其差分均匀度的方法需要大约O(2^(3n))次运算;而当n较大时(比如n>15),因搜索空间较大,从而导致花销时间太长(甚至计算不可行)等问题.如何快速判定(大状态)密码S盒的差分均匀度是目前的研究难点之一.本文基于密码S盒的循环差分特性,提出了一种求解其差分均匀度下界的新方法:通过统计循环差分对出现的次数,快速评估其解存在的个数,并由此给出密码S盒差分均匀度的下界.该方法所需的时间复杂度仅为O(2^(n))次运算.实验结果证实:对于4比特、5比特、7比特、8比特、9比特及多个16比特的S盒,利用该求解算法捕获的差分均匀度下界与真实的差分均匀度值是完全一致的.特别地,针对PRESENT、Keccak、MISTY-7、AES、MISTY-9、NBC及其变体使用的密码S盒,该方法求解其差分均匀度下界时所花销的时间均比传统算法节省82%以上.该方法为进一步评估大状态密码S盒的代数性质提供全新的思路.The cryptographic S-box is the core component of the symmetric encryption algorithm,and its algebraic property usually determines the overall security strength of the encryption algorithm.The differential uniformity measures the capability against the differential cryptanalysis.For the given S-box with n-bit input and n-bit output,the traditional method for solving its differential uniformity generally requires the time complexity of about O(2^(3n))operations.It is clear that the computation is usually infeasible for relatively large parameter(even for n>15,a long search time will be spent because of the large search range and resource).How to effectively determine the differential uniformity of the(large-state)input size S-box appears to be a difficult task now.In this article,a novel method for solving the lower bound of the differential uniformity of the S-box is proposed by basing on the cyclic differential characteristic.More precisely,for given S-box,this method calculates the number of existence solutions for each cyclic differential pairs,and thus gives the lower bound of the differential uniformity.The time complexity of this method requires only about O(2^(n))operations.For 4-bit,5-bit,7-bit,8-bit,9-bit,and even larger input size 16-bit S-boxes,the experimental results illustrate that the lower bound of the differential uniformity captured by the method are completely consistent with their real differential uniformity.In particular,for the S-boxes from PRESENT,Keccak,MISTY-7,AES,MISTY-9,NBC and their variants,this approach saves more than 82%calculation time when it is compared with the traditional solving algorithm.Actually,this approach provides new research idea for further evaluating the algebraic properties of the large-state input size S-boxes.

关 键 词：对称密码 差分攻击 密码S盒 差分均匀度 时间复杂度 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]