崔雅馨, 徐 洪, 戚文峰

信息工程大学, 郑州450001

1 引言

分组密码是密码学的重要分支, Feistel、SPN、Lai-Massey 等是常见的分组密码算法结构. 以AES算法为典型代表, SPN 结构通常是由两个重要组件构成: 非线性函数S 和可逆线性变换P. 非线性函数S 作为混淆层, 可逆线性变换P 则发挥扩散作用. 除AES 算法外, Serpent[1]、ARIA[2]、PRESENT[3]、RECTANGLE[4]、Skinny[5]、GIFT[6]以及我国分组密码算法竞赛提交的uBlock[7]、FESH[8]、TANGRAM[9]等都是来自SPN 结构的典型算法.

比特切片技术起初由Biham 等人[10]在1997 年提出用于加速DES 算法的软件实现效率, 之后Anderson 等人采用比特切片的思想设计了Serpent 算法[1]. 比特切片技术主要优势体现在可以高效提升算法的软件实现性能: 对于n 个S 盒并置构成的混淆层,每个S 盒需要查表一次,整个混淆层需要做n 次查表操作, 可以把S 盒每个输出比特通过输入比特的若干逻辑指令计算得到, 如果每个S 盒是相同的, 则对于n 个S 盒的相同位置比特只需要一次相同的逻辑指令计算完成. 对于RECTANGLE、TANGRAM等扩散层采用行循环移位的比特切片型分组算法, 本文将利用其结构特点, 对其安全性做进一步分析.

差分分析和线性分析是分组密码最重要的两类分析方法. 如何求解最小活动S 盒数目以估计差分概率(线性偏差) 的安全界, 和如何寻找具有最大差分概率(线性偏差) 的密码特征是其中面临的关键问题.2011 年, Mouha 等人[11]利用混合整数线性规划方法(mixed integer linear program, MILP) 给出了基于字节的最小活动S 盒个数的自动化搜索. 随后, 孙思维等人[12,13]进一步扩展了Mouha 等人的想法,提出了基于比特的MILP 模型, 将S 盒的具体差……