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

许垠松 等: 分组密码结构的低数据量子密钥恢复攻击 3335

d−2 d−1
0
0
G(P) = x d−1 ⊕ F d ( ⊕ x ⊕ ⊕ F i )⊕k d (26)
j
j=1 i=1
,
0
0
n
其中 P = (x , x ,..., x 0 , x 0 , x 0 ) P ∈ {0,1} 且 G(P) ∈ {0,1} n/d . 依据公式 (24)–(26), 我们提出以下针对 2d −1 轮类
0 1 d−3 d−2 d−1
SMS4 广义 Feistel-FK 结构的密钥恢复过程.
d−1
(
,
′
′
′
′
(1) 选择明文 P = (c,...,c,α) P = (c ,...,c ,α) c , c ), 查询其对应的密文. 并计算出 G(P) = α⊕ F d (c⊕ ⊕ F i )
i=1
d−1
′
′
⊕k d , G(P ) = α⊕ F d (c ⊕ ⊕ F i )⊕k d .
i=1
d−1 d−1
,
′
,
′
′
′
(2) 设 β 1 = c⊕ ⊕ F i β 2 = c ⊕ ⊕ F i , 则 β 1 ⊕β 2 = c⊕c G(P)⊕G(P ) = F d (β 1 )⊕ F d (β 1 ⊕c⊕c ), 可利用 Grover 算法
i=1 i=1
β 1 .
求出未知量
β 1 值, 可根据公式 k d .
(3) 已知 (26) 求出轮密钥
(4) 其他轮密钥可通过以上类似的方式依次求出来.
2d −1 轮类 SMS4 广义 Feistel-FK 结构的密钥恢复攻击过程中, 我们仅需选择 2 个明密文对
复杂度分析. 在对
即可恢复轮密钥 k d , 且在步骤 (2) 中利用 Grover 算法搜索未知量, 时间复杂度为 O(2 n/2d ). 对于恢复其他轮密钥的
过程所需时间和明文数量, 我们相信与恢复轮密钥 k d 所需时间和明文数量基本保持一致. 综上, 该密钥恢复攻击
的总体时间复杂度为 O(2 n/2d ), 数据复杂度为 O(1) 且经典存储复杂度可忽略不计. Cui 等人 [6] 也提出了对类 SMS4
广义 Feistel-FK 结构的量子密钥恢复攻击, 具体复杂度可见表 1. 但是, 他们的攻击属于 Q2 模型, 对攻击者的能力
2
要求较高. 此外, 当攻击轮数都为 r = r 0 时, 我们的攻击在复杂度乘积方面相比于他们的攻击可从 O(2n /(r 0 −1)
·2 2n/(r 0 −1) ) 降低为 O(n2 n/(r 0 +1) ). 但是, 当分支数 d 和攻击轮数相同时, 我们的攻击在复杂度乘积方面将提高 O(2 3n/2d )
因子.

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

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

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

 2d−1 0
 x = x ⊕ F 1 ⊕k 1 ⊕...⊕ F d−1 ⊕k d−1 ⊕...⊕ F 2d−1 ⊕k 2d−1
 0 d−1


 x = x ⊕ F 2 ⊕k 2 ⊕...⊕ F d ⊕k d ⊕...⊕ F 2d−1 ⊕k 2d−1
 2d−1 0

 1 0 (27)

 ...





x = x ⊕ F 1 ⊕k 1 ⊕...⊕ F d ⊕k d ⊕...⊕ F 2d−2 ⊕k 2d−2
 2d−1 0
d−1 d−2
由于 d 是偶数, 则: