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

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

0
0
β 1 ⊕β 3 =F d−2 (F d−3 (...F 1 (x )⊕ x ⊕k 1 ...)⊕ x 0 d−3 ⊕k d−3 )
1
0
0
0
∗
⊕ F d−2 (F d−3 (...F 1 (x )⊕ x ⊕k 1 ...)⊕(x 0 ) ⊕k d−3 ).
0 1 d−3
0
0
0
,
0
∗
(6) 设 δ 1 = F d−3 (...F 1 (x )⊕ x ⊕k 1 ...)⊕ x 0 d−3 ⊕k d−3 δ 2 = F d−3 (...F 1 (x )⊕ x ⊕k 1 ...)⊕(x 0 d−3 ) ⊕k d−3 , 则 δ 1 ⊕δ 2 = x 0 d−3
1
0
0
1
⊕(x 0 ) β 1 ⊕β 3 = F d−2 (δ 1 )⊕ F d−2 (δ 1 ⊕ x 0 ⊕(x 0 ) ) , 可利用 Grover 算法求出 δ 1 值.
,
∗
∗
d−3 d−3 d−3
(7) 已知 , x 0 值, 可计算出轮密钥 k d−2 = β 1 ⊕ F d−2 (δ 1 )⊕ x 0 .
δ 1 β 1 和
d−2 d−2
(8) 可重复以上类似步骤, 依次恢复出其他剩余轮密钥.
复杂度分析. 在对 3d −3 轮 Type-1 型广义 Feistel-FK 结构的密钥恢复攻击过程中, 我们仅需选择 4 个明密文
k d−2 , 且在步骤 (2)、(4)、 (6) 中利用 2 , 所以
n/d
对即可恢复轮密钥 Grover 算法搜索未知量, 每一个未知量的规模为
O(2 n/2d ). 对于恢复其他轮密钥的过程所需时间和明文数量, 我们相信与恢复轮密钥
每一步的时间复杂度都分别为
k d−2 所需时间和明文数量基本保持一致, 甚至可能更低, 例如, 可以重复利用明文. 综上, 该密钥恢复攻击的总体时
间复杂度为 O(2 n/2d ), 数据复杂度为 O(1) 且经典存储复杂度可忽略不计. 需要注意的是, Zou 等人 [21] 同样提出了在
Q1 模型下对 Type-1 型广义 Feistel-FK 结构的量子密钥恢复攻击, 其复杂度详见表 1. 然而, 由于他们使用了
d −d +1 轮的量子选择密文区分器, 他们的攻击属于选择密文攻击, 而我们的攻击仅需要加密 Oracle, 即选择明文
2
d = 3 时, 我们的攻击在复杂度乘积方面与 Zou 等人的攻击保持一致, 并且, 我们的攻击仅可以将数
攻击. 当分支数
据复杂度和存储复杂度从 O(2 n/2d ) 降低到 O(1). 不过, 当 d > 3 时, 我们的攻击相比于 Zou 等人的攻击将不具备明
显优势.

7 对类 SMS4 广义 Feistel 结构的密钥恢复攻击
如图 13 所示的 2d −1 轮类 SMS4 广义 Feistel-FK 结构, 其中每个分支与轮密钥 (
k i i = 1,2,...,2d −1) 的比特长
i i = 0,1,...,2d −1) 轮, 下标 表示第 (
i
i
,
度为 n/d F i 为轮函数, x 的上标 表示第 ( j j j = 0,1,...,d −1) 个分支. 明文
j
0
0
(x , x ,..., x 0 d−1 ) 作为其输入, 经过 2d −1 轮加密后得到密文 (x 2d−1 , x 2d−1 ,..., x 2d−1 ). 假设 d 为偶数.
0
0
1
1
d−1

0 0 0 0
x 0 x 1 x 2 x d−1
k 1 F 1
…
2d−3 rounds
k 2d−1 F 2d−1
…
2d−1 2d−1 2d−1 2d−1
x 0 x 1 x d−2 x d−1
2d −1 轮类 SMS4 广义 Feistel-FK 结构
图 13

根据 2d −1 轮类 SMS4 广义 Feistel-FK 结构的加密过程可知:

x 2d−1 = x 0 d−1 ⊕ F d (24)
0
其中,

 d−1
0

 F 1 = F 1 ( ⊕ x )⊕k
 j

 j=1




 d−1
 0 0

 F 2 = F 2 (x ⊕ ⊕ x ⊕ F 1 )⊕k 2
 0 j

j=2 (25)



 ...






 d−2 d−1
 0

 F d = F d ( ⊕ x ⊕ ⊕ F i )⊕k d
 j
j=1 i=1
根据公式 (24)、(25) 可设函数: