Page 398 - 《软件学报》2026年第5期

张语晗 等: 对缩减轮 SPECK 改进的差分-线性分析 2277

决 boomerang 区分器的两部分之间的依赖性问题. 受到 boomerang 分析中 BCT 表的启发, Bar-On 等人 [10] 给出了
DLCT 框架来解决差分-线性区分器 E 0 部分和 E 1 部分之间的依赖性问题, 接下来我们统称该框架为最新的差分-
线性分析框架. 在最新的差分-线性分析框架中, 算法 E 被分解为 E 0 、E m 、E 1 这 3 部分, 即 E = E 1 ◦ E m ◦ E 0 . 其中
E 0
r
E 0 、E m 、E 1 部分的轮数分别为 r 0 、r m 、r 1 . 在 E 0 部分有概率为 p 的差分 ∆ in −→ ∆ m , 在 E m 部分有相关性为 的差分-
E m E 1
线性逼近 ∆ m −−→ λ m , 在 E 1 部分有相关性为 q 的线性逼近 λ in −→ λ out , 如图 2 所示.

Δ in
E 0 E 0
p
Δ m
E m E m
r
λ m λ m
q q
E 1 E 1
λ out λ out
图 2 最新的差分-线性分析框架

E
当 ∆ m 和 λ m 是一个好的选择时, 我们可以通过如下的公式来得到差分-线性逼近 ∆ in −→ λ out 相关性的一个好的估计.

Cor(λ out · E(x)⊕λ out · E(x⊕∆ in )) = prq .
2
精确的相关性被计算为:

∑
Cor(λ out · E(x)⊕λ out · E(x⊕∆ in )) = Pr(∆ in ,∆ m )·Cor(λ m · E m (x)⊕λ m · E m (x⊕∆ m ))·Cor(λ m ,λ out ).
∆ m ,λ m
本文的分析都是基于最新的差分-线性分析框架的.
2 改进的差分-线性区分器搜索
E
∆ in −→ λ out 的相关性被估计为
在最新的差分-线性分析框架中, 当 ∆ m 和 λ m 是一个好的选择时, 差分-线性逼近
2 .
prq E 0 部分的差分概率 p 和 E 1 部分的线性相关性 q 基于现有的差分分析技术和线性分析技术就可以求解得到.
然而, 对于 ARX 类密码算法, 关于 E m 的差分-线性相关性 的计算常常是借助实验方法来计算得到的. 但是, 当通
r
r 的值时存在一些未解释的现象 [13] . 在本节中, 我们深入研究了 SPECK32/64 的差分-线性分析,
过实验方法来计算
对这些现象给出了一些说明. 然后, 我们给出了一个改进的差分-线性区分器搜索算法.
2.1 解释说明
在文献 [13] 中, Chen 等人借助实验方法来估计 E m 部分差分-线性相关性 的值. 通过多次的实验我们发现当
r
r 的值时, 存在一些未解释的现象, 接下来我们主要对如下两个未解释的现象展开讨论, 并给
借助实验方法来估计
出解释说明.
(1) 以 SPECK32/64 为例, 为什么 E m 部分的轮数 r m 的选取不超过 6 轮?
r
(2) 当采用实验方法估计 r 的值时, 样本集合的大小是否会影响 的估计?
在最新的差分-线性分析框架中, E m 部分的主要作用是解决 E 0 部分和 E 1 部分之间的依赖性问题, 当 E m 部分
r m 的选
的轮数 r m 较小时, 很有可能是无法保证 E 0 部分和 E 1 部分是相互独立的, 从这个角度来看 E m 部分的轮数
取越大越好. 但是在文献 [13] 中, 对轮数 r m 的选取似乎是有一些限制的, 例如对于 SPECK32/64, r m 选取的最大值
为 6, 但是为什么这么选取作者并没有给出详细的解释.
根据统计理论, 当使用实验方法估计中间部分的相关性时, 样本量的选择跟实验测量的相关性的大小之间存
在着紧密的关系. 例如, 在文献 [14−16] 中样本量的选择都满足如下的情况: 如果使用 2 个随机数据来实验测量相
n
n
关性, 那么只能较准确地测量到大于 c·2 − 2 (c ≈ 10) 的偏差.