Feistel结构差分活动S盒的搜索算法

Search Algorithm for Differential Active S-boxes of Feistel Structure

为了设计安全的分组密码算法,评估算法抵抗差分分析和线性分析的能力至关重要。目前一个比较实际的方法就是计算分组算法活动S盒的最小数目,或者最小数目的下界。2004年Shirai等人在FSE会议上提出了一种基于汉明重量针对Feistel结构的估计差分活动S盒数量下界的算法。本文指出了此算法的不足,并基于一种特殊的剪枝策略,对原算法提出了一个改进方案,将算法提升到实际应用水平。

In order to design secure block ciphers, the ability of evaluation algorithm to resist differential cryptanalysis and linear cryptanalysis is of utmost importance. Currently, a relatively practical measure is to calculate the minimum quantity of differential active S-boxes, or the lower bound of the minimum quantity. In 2004, Shirai et al. proposed a search algorithm to estimate the lower bound of active S-boxes quantity of Feistel based on hamming weight at FSE conference. This paper points out the flaw of this proposed search algorithm, and based on a special branch cutting strategy, puts forward an improved scheme is introduced to upgrade the algorithm to a practical application level.