Page 410 - 《软件学报》2024年第4期

1988 软件学报 2024 年第 35 卷第 4 期

可分性传播时, 其可分迹对应的子矩阵一定包含置换矩阵. 然而, 一个可逆矩阵一定包含一个置换矩阵, 但包含置
换矩阵的矩阵不一定为可逆矩阵. 例如: 一个矩阵的所有元素均为 1 时, 该矩阵包含单位矩阵作为置换矩阵, 但是
该矩阵并不是一个可逆矩阵. 因此, 给定相同的输入可分性, X 方法得到的可分迹一定包含 ZR 方法的可分迹, 这
也表明 X 方法的可分迹中可能包含无效的迹. 同样地, X 方法得到的可分迹一定包含 ZR + X 方法的可分迹. 基于
上述分析, 我们可以推导出如下命题.
命题 M ∈ F n×n ZR + X 方法得到的可分迹一定是 X 方法的可分
1. 给定一个矩阵
2 以及相同的输入可分性, 通过
迹的子集.
上述命题可以说明 ZR + X 方法不弱于 X 方法, 即 ZR + X 方法可以删除 X 方法中的一些无效可分迹. 因此,
+
ZR HZ 方法刻画线性层可分性传播的精确程度不弱于 HZ 方法和 SW 方法. 而 EY 方法只是将 ZR 方法中不
等式数量太多的情况结合首轮固定输入可分性一起考虑: 若初始可分性固定, 则首轮线性层的输入可分性只有少
数几种情况, 由定理 1 可知此时线性层矩阵所有有效可分迹对应的子矩阵的列只有少数几种情况, 因此刻画所有
可逆子矩阵时只需考虑少数几种列确定情况下的所有行, 对每种列确定的情况下组成的新的子矩阵, 根据高斯消
元法将子矩阵转化为行阶梯型矩阵, 进而将子矩阵的可逆判断等价为矩阵行向量的线性无关判断从而进行可分性
SW 方法刻画可分性的传播. 考虑到大部分情况下初始可分性传播到首
传播的刻画, 而中间轮的线性层仍然采用
轮线性层时, 线性层输入可分性汉明重量一般属于集合 Θ ZR , 因此 EY 方法刻画线性层可分性传播的精确程度不
EY 方法、
强于 ZR SW 方法. 综上所述, 动态选取策略刻画线性层可分性传播的精确程度不弱于 SW 方法、
+
HZ 方法, 且克服 ZR 方法难以在有效时间内求解复杂线性层矩阵的可分性传播模型的缺点.
3 基于动态选取策略搜索密码算法的积分区分器

本节通过动态选取策略的新技术构建 MILP 模型, 并搜索 uBlock 和 Saturnin 算法的积分区分器. 在比特可分
性的传播过程中, 与常数异或不会改变比特可分性质. 因此, 在构建 MILP 模型的过程中仅需要考虑 S 盒和线性
层. 对于 S 盒可分性传播的 MILP 建模可以参考文献 [8,21]; 对于复杂矩阵线性层矩阵的可分性传播则采取动态
选取策略进行 MILP 建模. 为了方便起见, C ,A ,B ,U 分别表示 i 个常数比特, 活跃比特, 平衡比特, 以及未知比特.
i
i
i
i
3.1 uBlock 算法积分区分器的搜索
uBlock 算法是一族 SPN 结构的分组密码, 其分组长度 n /密钥长度 分别为 128/128、128/256 和 256/256 比
k
特, 分别记 uBlock128/128, uBlock128/256 和 uBlock256/256, 迭代轮数分别为 16, 24, 24 轮. 轮结构如图 1 所示.

n n
4 2 2 4
S S ... S S S ... S

<<<4
32
<<<8
32
<<<8
32
<<<20
32

PL n PR n

图 1 uBlock 算法轮结构