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

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

(2) 假设:

β 0 = [F 1L ([0,0]⊕k 1 )⊕ F 1R ([0,0]⊕k 1 ),α 0 ⊕ F 1L ([0,0]⊕k 1 )]⊕k 2 ,

β 1 = [F 1L ([0,0]⊕k 1 )⊕ F 1R ([0,0]⊕k 1 ),α 1 ⊕ F 1L ([0,0]⊕k 1 )]⊕k 2 ,
则公式 (2) 可简写成:

0
0
0
0
x (P 0 )⊕y (P 0 )⊕ x (P 1 )⊕y (P 1 ) = α 0 ⊕α 1 ⊕ F 2L (β 0 )⊕ F 2R (β 0 )⊕ F 2L (β 1 )⊕ F 2R (β 1 ) (3)
3 3 3 3
,
n
且 β 0 ⊕β 1 = [0,α 0 ⊕α 1 ]. 设 β 0 =: x x ∈ {0,1} , 根据公式 (3) 构造函数:

G(x) = α 0 ⊕α 1 ⊕ F 2L (x)⊕ F 2R (x)⊕ F 2L (x⊕[0,α 0 ⊕α 1 ])⊕ F 2R (x⊕[0,α 0 ⊕α 1 ]) (4)
0 0 0 0 α 0 、 α 1 值, 则可通过 x
由于函数 F 2 公开已知, 且已知 x (P 0 )⊕y (P 0 )⊕ x (P 1 )⊕y (P 1 ) 值和 Grover 算法搜索出
3
3
3
3
0 0 0 0
使得 G(x) = x (P 0 )⊕y (P 0 )⊕ x (P 1 )⊕y (P 1 ), 即 β 0 值.
3 3 3 3
(3) 选择明文 P 2 = [0,0]||[α 0 ,α 1 ] 和 P 3 = [α 0 ,0]||[0,α 1 ], 查询它们对应的密文, 与步骤 (1) 一样, 求出以下值:

0
0
x (P 2 )⊕y (P 2 ) =α 0 ⊕ F 1R ([α 0 ,α 1 ]⊕k 1 )⊕ F 2L ([α 0 ⊕ F 1L ([α 0 ,α 1 ]⊕k 1 )⊕ F 1R ([α 0 ,α 1 ]⊕k 1 ),α 1 ⊕ F 1L ([α 0 ,α 1 ]⊕k 1 )]⊕k 2 )
3
3
⊕ F 2R ([α 0 ⊕ F 1L ([α 0 ,α 1 ]⊕k 1 )⊕ F 1R ([α 0 ,α 1 ]⊕k 1 ),α 1 ⊕ F 1L ([α 0 ,α 1 ]⊕k 1 )]⊕k 2 ),

0
0
x (P 3 )⊕y (P 3 ) =α 0 ⊕ F 1R ([α 0 ,α 1 ]⊕k 1 )⊕ F 2L ([ f 1L ([α 0 ,α 1 ]⊕k 1 )⊕ F 1R ([α 0 ,α 1 ]⊕k 1 ),α 0 ⊕α 1 ⊕ F 1L ([α 0 ,α 1 ]⊕k 1 )]⊕k 2 )
3 3
⊕ F 2R ([ f 1L ([α 0 ,α 1 ]⊕k 1 )⊕ F 1R ([α 0 ,α 1 ]⊕k 1 ),α 0 ⊕α 1 ⊕ F 1L ([α 0 ,α 1 ]⊕k 1 )]⊕k 2 ),
再异或相加得到:

0
0
0
0
x (P 2 )⊕y (P 2 )⊕ x (P 3 )⊕y (P 3 ) =F 2L ([α 0 ⊕ F 1L ([α 0 ,α 1 ]⊕k 1 )⊕ F 1R ([α 0 ,α 1 ]⊕k 1 ),α 1 ⊕ F 1L ([α 0 ,α 1 ]⊕k 1 )]⊕k 2 )
3
3
3
3
⊕ F 2R ([α 0 ⊕ F 1L ([α 0 ,α 1 ]⊕k 1 )⊕ F 1R ([α 0 ,α 1 ]⊕k 1 ),α 1 ⊕ F 1L ([α 0 ,α 1 ]⊕k 1 )]⊕k 2 )
⊕ F 2L ([F 1L ([α 0 ,α 1 ]⊕k 1 )⊕ F 1R ([α 0 ,α 1 ]⊕k 1 ),α 0 ⊕α 1 ⊕ F 1L ([α 0 ,α 1 ]⊕k 1 )]⊕k 2 )
⊕ F 2R ([F 1L ([α 0 ,α 1 ]⊕k 1 )⊕ F 1R ([α 0 ,α 1 ]⊕k 1 ),α 0 ⊕α 1 ⊕ F 1L ([α 0 ,α 1 ]⊕k 1 )]⊕k 2 ) (5)
(4) 同样设:

β 2 = [α 0 ⊕ f 1L ([α 0 ,α 1 ]⊕k 1 )⊕ f 1R ([α 0 ,α 1 ]⊕k 1 ),α 1 ⊕ f 1L ([α 0 ,α 1 ]⊕k 1 )]⊕k 2 ,

β 3 = [ f 1L ([α 0 ,α 1 ]⊕k 1 )⊕ f 1R ([α 0 ,α 1 ]⊕k 1 ),α 0 ⊕α 1 ⊕ f 1L ([α 0 ,α 1 ]⊕k 1 )]⊕k 2 ,
则公式 (5) 可以简写成:

0
0
0
0
x (P 2 )⊕y (P 2 )⊕ x (P 3 )⊕y (P 3 ) = F 2L (β 2 )⊕ F 2R (β 2 )⊕ F 2L (β 3 )⊕ F 2R (β 3 ) (6)
3 3 3 3
n
,
且 β 3 ⊕β 2 = [α 0 ,α 0 ]. 依然设 β 2 =: x x ∈ {0,1} , 根据公式 (6) 构造函数:

G (x) = F 2L (x)⊕ F 2R (x)⊕ F 2L (x⊕[α 0 ,α 0 ])⊕ F 2R (x⊕[α 0 ,α 0 ]) (7)
′
0 0 0 0 α 0 、 α 1 值, 则可通过 x 使
由于函数 F 2 公开已知, 且已知 x (P 2 )⊕y (P 2 )⊕ x (P 3 )⊕y (P 3 ) 和 Grover 算法搜索出
3
3
3
3
′ 0 0 0 0 β 2 值.
得 G (x) = x (P 2 )⊕y (P 2 )⊕ x (P 3 )⊕y (P 3 ), 即
3 3 3 3
(5) 得到 β 0 和 β 2 值后, 异或可得:

β 0 ⊕β 2 = [α 0 ⊕ F 1L ([α 0 ,α 1 ]⊕k 1 )⊕ F 1R ([α 0 ,α 1 ]⊕k 1 )⊕ F 1L (k 1 )⊕ F 1R (k 1 ),α 1 ⊕ F 1L ([α 0 ,α 1 ]⊕k 1 )⊕α 0 ⊕ F 1L (k 1 )].
令 k 1 =: x, 构造函数:

H(x) = [α 0 ⊕ F 1L ([α 0 ,α 1 ]⊕ x)⊕ F 1R ([α 0 ,α 1 ]⊕ x)⊕ F 1L (x)⊕ F 1R (x),α 1 ⊕ F 1L ([α 0 ,α 1 ]⊕ x)⊕α 0 ⊕ F 1L (x)] (8)
,
,
由于已知公开函数 F 1 β 0 ⊕β 2 α 0 和 α 1 值, 可通过 Grover 算法搜索出 x 满足 H(x) = β 0 ⊕β 2 , 即为 k 1 值.
(6) 获得 k 1 值, 可通过 β 0 求出 , 最后计算出 .
k 3
k 2
复杂度分析. 通过上述密钥恢复攻击过程可知, 在选择明文攻击环境下, 我们提出的攻击仅需 4 个明文
{P 0 ,P 1 ,P 2 ,P 3 } 及其对应的密文则可恢复密钥. 并且在第 (2)、(4)、(5) 步中利用 Grover 算法搜索解时所需时间分
n/2 n/2
别为 O(2 ), 所以总的时间复杂度也为 O(2 ). 此外, 数据复杂度仅为 O(1), 经典存储复杂度可忽略不计.

5 对 Misty 结构的密钥恢复攻击
本文针对 Lai-Massey 结构的新型量子密钥恢复攻击思想同样可以被应用到 Misty 结构上.