Page 400 - 《软件学报》2026年第5期
P. 400
张语晗 等: 对缩减轮 SPECK 改进的差分-线性分析 2279
根据实验结果我们得到了如下的观察结果.
● 观察 1. 对于 SPECK32/64, E m 部分的轮数 r m 的选取不超过 6 轮是因为当轮数不超过 6 轮时, 有明显大于
2 −16 的相关性, 并且不同密钥下的相关性的值都大于 2 −16 .
30
22
当利用实验方法计算差分-线性逼近的相关性时, 因为计算资源有限, 一般采用一个小的样本集合, 如 2 –2 .
22 30 2 −11 (2 −15 ) 时,
通过实验我们发现, 如果选择的样本集合的大小为 2 (2 ) 时, 在实验计算得到的相关性的值趋近于
实际的相关性的值其实已经很接近随机情况了. 这也侧面反映了当采用实验方法计算 E m 部分的差分-线性逼近的
相关性的值时, 对于 E m 部分差分-线性逼近的选择, 应该选择相关性的值尽可能大的差分-线性逼近. 但是, 相关性
r m 的
的值越大, 也就意味着轮数 r m 的选择不能太大, 这也将会影响 E 0 部分和 E 1 部分的依赖性. 因此, 当选择轮数
值的时候, 一方面应该选择尽可能长的轮数来保证 E 0 部分和 E 1 部分的独立性; 另一方面, 不能选择太长的轮数来
保证实验方法计算的相关性的值的准确性. 基于上述实验结果, 我们得到了如下的观察.
● 观察 2. 当通过实验方法计算 E m 部分差分-线性逼近的相关性的值时, 为了得到更加接近实际值的相关性估
N
计, 在选择 E m 部分差分-线性逼近的时候, 我们应该尽可能选择相关性的取值远大于 2 − 2 的差分-线性逼近, 其中样
N
本集合的大小为 2 .
在本节中, 我们参考文献 [14−16] 并通过遍历 SPECK32/64 的 32 比特明文空间, 测试差分-线性逼近的实际相
关性. 随后, 对文献 [13] 中未解释的现象给出了一些说明.
2.2 差分-线性区分器搜索算法
目前已有的差分-线性区分器搜索算法往往先从搜索相关性高的中间部分的差分-线性逼近出发, 然后再分别
向后和向前搜索差分部分的特征和线性部分的特征, 基于该策略搜索到的差分-线性特征的差分部分和线性部分
的特征往往不是最优或者次优的, 容易错过一些高相关性的差分-线性区分器. 在本节中我们首先从高概率且输出
差分汉明重量低的差分特征和高相关性且输入掩码汉明重量低的线性特征出发, 然后再测量中间部分的相关性,
得到了一些新的差分-线性区分器.
在文献 [13] 中, 作者给出了一个基于 Meet-in-the-Middle 思想的搜索方法来搜索 ARX 类密码算法的差分-线
性区分器, 得到了 SPECK 和 LEA 算法概率更高轮数更长的差分-线性区分器. 在本节中, 我们借鉴了该 Meet-in-
the-Middle 的搜索思想, 给出了一个改进的差分-线性区分器搜索算法. 我们的搜索算法考虑了差分概率 p, 差分-
线性相关性 r 和线性相关性 q 三者的折中. 首先, 给出如下两个观察结果.
● 观察 3. 在差分-线性区分器搜索中, 当差分 (线性) 部分的特征为次优、次次优特征时更容易得到高相关性
的差分-线性区分器.
● 观察 4. 在差分-线性区分器搜索中, ∆ m 中的差分活跃比特个数较少且 λ m 中的线性活跃比特数较少时更容易
得到高相关性的差分-线性区分器.
基于观察 3 和观察 4, 我们通过如下的步骤来搜索密码算法 E 的 r DL 轮差分-线性区分器.
(1) 首先, 确定 E 0 、E m 和 E 1 部分的轮数 r 0 、r m 和 .
r 1
∪ ∪ r 0
r 0
(2) 然后, 搜索得到密码算法 E 的 r 0 轮最优、次优、次次优差分特征的输出差分集合 S = b S (p,b), 其
∆ p ∆
r 0
中 S (p,b) 表示概率为 p, 输出差分的活跃比特个数为 b 的 r 0 轮差分特征的输出差分的集合.
∆
∪ ∪
r 1
(3) 接着, 搜索得到密码算法 E 的 r 1 轮最优、次优、次次优线性特征的输入线性掩码集合 S = q b S r1
Λ
Λ
r1
q
(q,b), 其中 S (q,b) 表示相关性为 , 输入线性掩码的活跃比特个数为 b 的 r 1 轮线性特征的输入线性掩码的集合.
Λ
r 0 r 1 中选择相关性高且活
(4) 从集合 S 中挑选差分概率高且活跃比特个数少的差分作为 ∆ m 的候选, 从集合 S
∆ Λ
E m
跃比特个数少的线性掩码作为 λ m 的候选, 并计算差分-线性逼近 ∆ m −−→ λ m 的相关性 r.
2
(5) r DL = r 0 +r m +r 1 轮的差分-线性逼近的相关性被计算为 cor = prq .
(6) 重复步骤 (1)–(5), 直到找到一个高相关性的差分-线性逼近.
注意到, 对于步骤 (2) 和 (3) 可以通过预计算得到:
