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

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

根据 Misty L-FK (x 5 ,y 5 ) 的值为:
结构的加密过程, 可得到密文
x 5 = y 0 ⊕ F 1 (x 0 )⊕k 1 ⊕ F 2 (y 0 )⊕k 2 ⊕ F 3 (y 0 ⊕ F 1 (x 0 )⊕k 1 )⊕k 3 ⊕ F 4 (y 0 ⊕ F 1 (x 0 )⊕k 1 ⊕ F 2 (y 0 )⊕k 2 )⊕k 4 ,

y 5 = x 5 ⊕ F 5 (y 0 ⊕ F 1 (x 0 )⊕k 1 ⊕ F 2 (y 0 )⊕k 2 ⊕ F 3 (y 0 ⊕ F 1 (x 0 )⊕k 1 )⊕k 3 )⊕k 5 .
y 5 异或后可得:
将密文的左半部分 x 5 和右半部分

(11)
x 5 ⊕y 5 = F 5 (y 0 ⊕ F 1 (x 0 )⊕k 1 ⊕ F 2 (y 0 )⊕k 2 ⊕ F 3 (y 0 ⊕ F 1 (x 0 )⊕k 1 )⊕k 3 )⊕k 5
根据公式 (11) 可设函数:

(12)
G(x,y) = F 5 (y⊕ F 1 (x)⊕k 1 ⊕ F 2 (y)⊕k 2 ⊕ F 3 (y⊕ F 1 (x)⊕k 1 )⊕k 3 )⊕k 5
n/2
y
y 0 x,y ∈ {0,1}
其中, 变量 x 和 分别对应明文 x 0 和 , n/2 且 G(x,y) ∈ {0,1} . 在公式 (12) 的基础上, 我们可以构建新的
5 轮 Misty L-FK 结构密钥恢复攻击, 具体过程如下.
(x ,y = F 1 (x )) (x ,y = F 1 (x )), 并查询其密文. 根据公式 (11)、(12) 分别进行计算, 并对输出进
2
1
1
2
,
1
2
(1) 选择明文 0 0 0 0 0 0
行异或可得:

1
1
1
2
2
2
G(x ,y )⊕G(x ,y ) = F 5 (k 1 ⊕ F 2 (y )⊕k 2 ⊕ F 3 (k 1 )⊕k 3 )⊕ F 5 (k 1 ⊕ F 2 (y )⊕k 2 ⊕ F 3 (k 1 )⊕k 3 ).
0
0
0
0
0
0
1 2 1 2 1 1
,
,
(2) 设 β 1 = k 1 ⊕ F 2 (y )⊕k 2 ⊕ F 3 (k 1 )⊕k 3 β 2 = k 1 ⊕ F 2 (y )⊕k 2 ⊕ F 3 (k 1 )⊕k 3 , 则 β 1 ⊕β 2 = F 2 (y )⊕ F 2 (y ) G(x ,y )⊕G
0 0 0 0 0 0
,
2 2 1 2 1 1 2 2 1 y 值, 可通过
2
(x ,y ) = F 5 (β 1 )⊕ F 5 (β 1 ⊕ F 2 (y )⊕ F 2 (y )) . 由于已知公开函数 F 5 和 F 2 G(x ,y )⊕G(x ,y ) 值, y 和
0 0 0 0 0 0 0 0 0 0
Grover 算法求出 β 1 值.
β 1 值和公式 k 5 .
(3) 根据 (12), 可计算出
k 4 k 3 k 2 和 .
(4) 在计算出 k 5 后, 可使用步骤 (1)–(3) 类似的方法依次恢复出轮密钥 , , k 1
复杂度分析. 在对 5 轮 Misty L-FK 结构的密钥恢复攻击过程中, 我们仅需选择 2 个明密文对, 且在依次恢复
n/4 n/4 O(1) 且
轮密钥 k 5 k 1 的时间复杂度分别都为 O(2 ). 综上, 我们的攻击总体时间复杂度为 O(2 ), 数据复杂度为
–
经典存储复杂度可忽略不计.
若在 5 轮 Misty L-FK 结构的基础上再增加 r −5 轮, 则可先穷举轮密钥 k 6 k r , 再重复以上步骤恢复其他轮密
–
O(2 n/4+(r−5)n/2 O(1) 且经典存储复杂度
钥, 并用明密文进行验证正确性. 则整体时间复杂度为 ), 数据复杂度依然仅为
可忽略不计.

5.3 对 Misty R-KF 结构的密钥恢复攻击
如图 10 所示的 4 轮 Misty R-KF 结构, 其中, ( k i 为轮密钥且 |k i | = n/2 i = 1,2,3,4 (x 0 ,y 0 )
),
(
F i i = 1,2,3,4) 为轮函数,
为 4 轮 Misty R-KF 结构的明文输入且 |(x 0 ,y 0 )| = n (x 4 ,y 4 ) 作为密文输出.
,

y 1 y 2 y 3
y 0 y 4
x 4
x 0 F 1 F 2 F 3 F 4
x 2 x 3
x 1
k 4
k 1 k 2 k 3
图 10 4 轮 Misty R-KF 结构

根据 Misty R-KF y 4 异或后可得:
结构的加密过程, 得到密文 (x 4 ,y 4 ), 并将左半部分 x 4 和右半部分
x 4 ⊕y 4 = F 3 (F 1 (x 0 ⊕k 1 )⊕ F 2 (F 1 (x 0 ⊕k 1 )⊕y 0 ⊕k 2 )⊕k 3 ) (13)
由公式 (13) 可设函数:

G(x,y) = F 3 (F 1 (x⊕k 1 )⊕ F 2 (F 1 (x⊕k 1 )⊕y⊕k 2 )⊕k 3 ) (14)
n/2
y 0 x,y ∈ {0,1}
其中, 变量 x 和 y 分别对应 x 0 和 , n/2 且 G(x,y) ∈ {0,1} . 依据公式 (14), 我们提出以下针对 4 轮 Misty R-
KF 结构的密钥恢复过程.