Page 403 - 《软件学报》2025年第7期

3324 软件学报 2025 年第 36 卷第 7 期

qCPA 环境下利用 Simon 算法在多项式时间区分是否随机. 随后, Gouget 等人 [25] 改进了这一结果, 给出了一个 4
轮 Misty L 结构的 qCPA 区分器. 而 Cui 等人 [6] 则更进一步, 分别提出了 Misty L-FK 结构的 5 轮 qCPA 区分器和
Misty R-FK 结构的 5 轮 qCCA 区分器. Zou 等人 [21] 通过结合 Simon 算法的周期函数和生日攻击的思想, 在 Q1 模
型下提出了对 5 轮 Misty L/R-F 结构和 6 轮 Misty L/R-KF/FK 结构的密钥恢复攻击.
Type-1 型广义 Feistel 结构是 Feistel 结构的一个推广, CAST-256 [26] 则是基于该结构设计出来的. Deng 等人 [27]

基于中间相遇方法提出了 5d −3 轮 d 分支 Type-1 型广义 Feistel 结构的密钥恢复攻击方法. 在量子环境 Q2 模型
下, Dong 等人 [14] 基于 Simon 算法提出了 2d −1 轮 Type-1 型广义 Feistel 结构的量子区分器. 随后, Ni 等人 [28] 进一
3d −3 轮 qCPA d −d +1 轮 qCCA 区分器. Zou 等人 [21] d −d +1 轮 qCCA
2
2
步改进了这一结果, 提出了 区分器和 在
区分器基础上, 在 Q1 模型下提出了 d Type-1 型广义 Feistel 结构的密钥恢复攻击.
2
SMS4 是中国公布的商用分组密码 [29] . You 等人 [30] 提出了 6 轮 SMS4 的 qCPA 区分器. Cid 等人 [31] 进一步证
明了 7 轮 SMS4 在量子环境下也是不安全的. Cui 等人 [6] 为了更一般化地评估 SMS4 底层结构, 将 SMS4 所使用的
加密结构称为类 SMS4 广义 Feistel 结构, 并提出了 2d −1 轮类 SMS4 广义 Feistel-F/KF 结构的 qCPA 区分器和
2d +1 类 SMS4 广义 Feistel-FK 结构的 qCPA 区分器.
Cui 等人 [6] 称呼 MARS 分组密码所用的底层结构为类 MARS 广义 Feistel 结构. Moriai 等人 [32] 已证明 5 轮
MARS 方案是伪随机的且 8 轮 MARS 方案是超伪随机的. 在 Q2 模型下, Cui 等人 [6] 提出了 2d −1 轮类 MARS 广
义 Feistel-F/KF 结构的 qCPA 区分器和 2d +1 类 MARS 广义 Feistel-FK 结构的 qCPA 区分器.

2 相关密码结构

本文主要针对 Lai-Massey 结构、Misty 结构、Type-1 型广义 Feistel 结构、类 SMS4 广义 Feistel 结构和类
MARS 广义 Feistel 结构, 下面就相关概念予以介绍.

2.1 Lai-Massey 结构
本文中被攻击的 Lai-Massey 结构使用 XOR 运算代替一般的加法和减法运算, 且置换 σ 满足 σ(x L , x R ) = (x R ,
x L ⊕ x R ), 如图 1(a) 所示. 第 i 轮 Lai-Massey 结构的输入为 (x i−1 ,y i−1 ), 则输出为 (x i ,y i ) ← (σ(x i−1 ⊕ F i (∆ i−1 )),y i−1 ⊕
i
,
F i (∆ i−1 )), 其中 ∆ i−1 = x i−1 ⊕y i−1 F i 为第 轮轮函数. 在最后一轮, 左半分支将无须置换 σ, 即输出为 (x i ,y i ) ← (x i−1 ⊕
F i (∆ i−1 ),y i−1 ⊕ F i (∆ i−1 )). 本文中设 Lai-Massey 结构的输入为 n 比特, 则其左右分支状态均为 n/2 比特.

x i−1 y i−1 x i−1 y i−1
k i
Δ i−1
Δ i−1 k i
F i F i

σ σ

x i y i x i y i
(a) (b)
图 1 Lai-Massey 结构

类似于 Ito 等人在文献 [16] 中的命名方式, 我们根据密钥注入的方式, 即将轮密钥 k i 与中间态 ∆ i−1 异或后作
为轮函数 F i 的输入, 称其为 Lai-Massey-KF 结构, 如图 1(b) 所示.

2.2 Misty 结构
由于 XOR 运算位置不同, Misty 结构可分为 L 和 R 两种结构, 如图 2 所示. 设 Misty L 结构第 i 轮的输入状态
i
为 (x i−1 ,y i−1 ), 则其第 轮的输出状态为 (x i ,y i )←(y i−1 ,F i (k i , x i−1 )⊕y i−1 ). 类似地, 如图 2(b) 所示, Misty R 结构第 i 轮的
输出状态为 (x i ,y i )←(y i−1 ⊕ F i (k i , x i−1 ),F i (k i , x i−1 )). 同样地, 本文假设 Misty 结构的输入为 n 比特, 则其左右分支状态
均为 n/2 比特.