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

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

为了解决密码设计中最小活跃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.