基于SAT的线性扩散层分支数的快速计算方法  

Fast Evaluation Method of Branch Number of Linear Diffusion Layer Based on SAT

作　　者：苗旭东 张晶 胡建勇 董新锋 张文政[1] MIAO Xudong;ZHANG Jing;HU Jianyong;DONG Xinfeng;ZHANG Wenzheng(No.30 Institute of CETC,Chengdu Sichuan 610041,China)

机构地区：[1]中国电子科技集团公司第三十研究所,四川成都610041

出　　处：《通信技术》2022年第5期634-639,共6页Communications Technology

基　　金：四川省科技计划(2020JDJQ0076)。

摘　　要：将线性扩散层差分和线性分支数的计算问题转化为布尔可满足性问题(Boolean Satisfiability Problem,SAT),提出了一种通用的快速计算分组密码线性扩散层分支数的方法,该方法可以在较短的时间内求解出分组大于32比特线性扩散层的分支数。为了检验本方法的实际应用效果,测试了一批随机构造的循环异或(Rotation-XOR,RX)结构分组为64比特线性扩散层的分支数。结果显示,所提方法均能在较短的时间内计算出分支数,并且当线性扩散层的分组为64比特、分块为8、异或项数为9时,首次得到分支数达到8的RX结构的扩散层。In order to transform the calculation problem of differential and linear branch number of linear diffusion layer into SAT problem,a general and fast method to evaluate the branch number of linear diffusion layer in block cipher is proposed.This method can solve the linear diffusion branch number problem with blocks greater than 32 bits in a relatively short time.In order to test the practical application effect of this method,a batch of randomly constructed RX(Rotation-XOR)structures grouped into 64-bit linear diffusion layers are tested.The results indicate that the proposed method can calculate the branch number in a short time,and when the grouping of the linear diffusion layer is 64 bits,divided into 8 bytes,and the number of XOR items is 9,the diffusion layer of the RX structure with a branch number of 8 is obtained for the first time.

关 键 词：布尔可满足性问题 线性扩散层 分支数 循环异或 

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