比特切片型算法差分及线性特征的快速构造

作者：崔雅馨; 徐洪^*; 戚文峰

来源：密码学报, 2021, 8(01): 154-166.

DOI：10.13868/j.cnki.jcr.000428

• 比特切片
• 差分特征
• 线性特征
• RECTANGLE
• TANGRAM

比特切片方法由Biham等人于1997年提出,该方法可以高效提升算法的软件实现性能,后来被广泛应用于Serpent、RECTANGLE、TANGRAM等分组算法.本文针对扩散层采用简单行循环移位的RECTANGLE、TANGRAM等比特切片型分组算法,根据算法S盒的性质以及行移位参数,给出了快速判断其是否存在单轮循环差分/线性特征的方法.基于找到的单轮循环差分/线性特征,结合MILP自动化搜索技术,实现了这类算法长轮数差分/线性特征的快速构造.进一步,我们扩展寻找单轮循环特征的思想,利用MILP方法自动化搜索了不超过4轮的循环差分/线性特征,基于此可以更方便构造长轮数差分/线性特征.利用此方法,我们找到了RECTANGLE算法的14轮差分特征和13轮线性特征, TANGRAM128算法的24轮差分特征和23轮线性特征, TANGRAM 256算法的48轮差分特征和44轮线性特征.特别地,我们找到的TANGRAM 256算法的44轮线性特征是目前找到的最长轮数的线性特征.我们的方法只依赖于算法的结构特点和S盒的性质,该研究对采用这种结构的分组算法长轮数差分/线性特征的寻找和相应算法的设计都有重要意义.

• 单位
  信息工程大学