分组密码最小活跃S盒个数快速搜索算法  

Fast algorithm to search for the minimum number of active S-boxes of block cipher

作　　者：刘正斌 李永强[2] 朱朝熹 LIU Zhengbin;LI Yongqiang;ZHU Chaoxi(Science and Technology on Communication Security Laboratory,Chengdu 610041,China;Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China)

机构地区：[1]保密通信重点实验室,四川成都610041 [2]中国科学院信息工程研究所,北京100093

出　　处：《通信学报》2023年第1期118-128,共11页Journal on Communications

基　　金：国家自然科学基金资助项目(No.61772517)。

摘　　要：为了解决密码设计中最小活跃S盒个数的快速计算问题,研究了扩散层的差分和掩码传播性质,提出了一种计算最大距离可分(MDS)矩阵和二元域矩阵的差分/掩码模式分布表的方法,并证明了所提方法计算复杂度的下界。基于扩散矩阵的差分/掩码模式分布表,提出了一种快速搜索分组密码最小活跃S盒个数的算法,将其用于代入置换网络(SPN)型分组密码,找到了LED、SKINNY、CRAFT和FIDES的全轮最小活跃S盒个数。To solve the problem of fast calculation of the minimum number of active S-boxes in cryptographic design, the difference and mask propagation of the diffusion layer were investigated, and a method was proposed to compute the difference(resp. mask) pattern distribution table of MDS(maximum distance separable) matrices and binary matrices. A lower bound on the computation complexity of the proposed method was also given. Based on the difference(resp. mask)pattern distribution table of diffusion matrix, a fast algorithm to search for the minimum number of active S-boxes of block cipher was proposed. The proposed algorithm is applied to some SPN(substitution permutation network) block ciphers, and finds the minimum number of active S-boxes for the full round of LED, SKINNY, CRAFT and FIDES.

关 键 词：分组密码 差分密码分析 线性密码分析 活跃S盒 自动化搜索 

分 类 号：TN918[电子电信—通信与信息系统]