对ARX密码最优差分路径自动搜索算法的改进

Improvement of Automatic Search Algorithm for the Best Differential Trails in ARX Ciphers

针对Biryukov算法在构造轮差分转移时概率计算效率不高的问题,将逐位比特赋值改为两比特块赋值,有效减少等概率值的计算次数和时间复杂度。利用该方法,概率值的计算次数和时间复杂度最多可减少1/3。将上述改进的搜索算法应用于SPECK算法,实验结果表明,在4和5轮时改进算法比Biryukov算法的时间复杂度减少1/10,在6轮时减少1/5。

To improve the efficiency of Biryukov algorithm,the bit-by-bit assignment is changed to the two-bit-block assignment,which can decrease the frequency of differential probability calculation. By using this method,the time complexity of the search algorithm can be reduced by 1/3 at most. When the improved algorithm is applied to the SPECK algorithm,the experimental results show that the time complexity of the search algorithm is reduced by 1/10 on 4 and 5 rounds,1/5 on6 rounds.