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

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

(x ,y ) (x ,y ), 并查询其对应的密文, 根据公式 (13)、(14) 计算出:
1
2
1
1
,
(1) 选择明文
0 0 0 0

1
1
1
1
1
G(x ,y ) = F 3 (F 1 (x ⊕k 1 )⊕ F 2 (F 1 (x ⊕k 1 )⊕y ⊕k 2 )⊕k 3 ),
0 0 0 0 0
2
1
1
1
2
G(x ,y ) = F 3 (F 1 (x ⊕k 1 )⊕ F 2 (F 1 (x ⊕k 1 )⊕y ⊕k 2 )⊕k 3 ).
0
0
0
0
0
( 2 ) 设 β 1 = F 1 (x ⊕k 1 )⊕ F 2 (F 1 (x ⊕k 1 )⊕y ⊕k 2 )⊕k 3 β 2 = F 1 (x ⊕k 1 )⊕ F 2 (F 1 (x ⊕k 1 )⊕y ⊕k 2 )⊕k 3 , 则 G(x ,y ) =
1
2
1
1
1
1
1
1
,

0 0 0 0 0 0 0 0
F 3 (β 1 ) G(x ,y ) = F 3 (β 2 ) , 利用 Grover 算法求出 β 1 和 β 2 值.
1
2
,
0 0
1 1 1 2 1 1
(3) 将 β 1 和 β 2 异或后可得 β 1 ⊕β 2 = F 2 (F 1 (x ⊕k 1 )⊕y ⊕k 2 )⊕ F 2 (F 1 (x ⊕k 1 )⊕y ⊕k 2 ), 设 δ 1 = F 1 (x ⊕k 1 )⊕y ⊕k 2 ,
0
0
0
0
0
0
2
1 2 δ 1 ⊕δ 2 = y ⊕y . 可利用 1 2
1
δ 2 = F 1 (x ⊕k 1 )⊕y ⊕k 2 , 则 0 0 Grover 算法求 β 1 ⊕β 2 = F 2 (δ 1 )⊕ F 2 (δ 1 ⊕y ⊕y ) 中未知量 .
δ 1
0
0
0
0
2
2
,
1
2
(4) 选择明文 (x ,y ) (x ,y ), 并查询其对应的密文, 计算出:
0 0 0 0
G(x ,y ) = F 3 (F 1 (x ⊕k 1 )⊕ F 2 (F 1 (x ⊕k 1 )⊕y ⊕k 2 )⊕k 3 ),
1
2
2
1
2
0 0 0 0 0
2
2
2
2
G(x ,y ) = F 3 (F 1 (x ⊕k 1 )⊕ F 2 (F 1 (x ⊕k 1 )⊕y ⊕k 2 )⊕k 3 ).
2
0 0 0 0 0
2 2 1 , 2 2 2 2 1
(5) 设 β 3 =F 1 (x ⊕k 1 )⊕ F 2 (F 1 (x ⊕k 1 )⊕y ⊕k 2 )⊕k 3 β 4 =F 1 (x ⊕k 1 )⊕ F 2 (F 1 (x ⊕k 1 )⊕y ⊕k 2 )⊕k 3 , 则 G(x ,y )=F 3 (β 3 ),
0
0
0
0
0
0
0
0
G(x ,y ) = F 3 (β 4 ), 利用 Grover 算法求出 β 3 和 β 4 值.
2
2
0 0
2 1 2 2 2 1
(6) 将 β 3 和 β 4 异或后可得 β 3 ⊕β 4 = F 2 (F 1 (x ⊕k 1 )⊕y ⊕k 2 )⊕ F 2 (F 1 (x ⊕k 1 )⊕y ⊕k 2 ), 设 δ 3 = F 1 (x ⊕k 1 )⊕y ⊕k 2 ,
0 0 0 0 0 0
1
2 2 δ 3 ⊕δ 4 = y ⊕y . 可利用 1 2
2
δ 4 = F 1 (x ⊕k 1 )⊕y ⊕k 2 , 则 Grover 算法求 β 3 ⊕β 4 = F 2 (δ 3 )⊕ F 2 (δ 3 ⊕y ⊕y ) 中未知量 .
δ 3
0 0 0 0 0 0
1
2
(7) 将得到的 δ 1 和 δ 3 异或后可得 δ 1 ⊕δ 2 = F 1 (x ⊕k 1 )⊕ F 1 (x ⊕k 1 ). 再利用 Grover 算法求出其中的未知量 k 1 .
0
0
k 2 k 3 和 .
(8) 恢复出轮密钥 k 1 后, 可依次求出轮密钥 , k 4
复杂度分析. 在对 4 轮 Misty R-KF 结构的密钥恢复攻击过程中, 我们仅需选择 4 个明密文对, 且在步骤 (2)、
(3)、 (5)–(8) 中利用 Grover 算法搜索未知量, 每一个未知量的规模为 2 , 所以每一步的时间复杂度都分别为
n/2
n/4 n/4
O(2 ). 综上, 该密钥恢复攻击的总体时间复杂度为 O(2 ), 数据复杂度为 O(1) 且经典存储复杂度可忽略不计.
若在 4 轮 Misty R-KF 结构上再增加 r −4 轮, 则可先穷举轮密钥 k 5 k r , 再重复以上步骤恢复其他轮密钥, 并
–
O(2 n/4+(r−4)n/2 O(1) 且经典存储复杂度可忽略
用明密文验证正确性. 则整体时间复杂度为 ), 数据复杂度依然仅为
不计.

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

k 1 k 2 k 3 k 4 k 5
y 1 y 2 y 3 y 4
y 5
y 0
x 0 F 1 F 2 F 3 F 4 F 5 x 5
x 1 x 4
x 2 x 3
图 11 5 轮 Misty R-FK 结构

根据 Misty R-KF y 5 异或后可得:
结构的加密过程, 得到密文 (x 5 ,y 5 ), 并将左半部分 x 5 和右半部分
(15)
x 5 ⊕y 5 = F 4 (x 3 )⊕k 5
对右半部分密文 y 5 经过函数 F 5 的逆可以求得:

−1
x 4 = F (y 5 ) = y 3 ⊕ F 4 (x 3 )⊕k 4 (16)
5
将公式 (15)、(16) 异或后可得:

−1
F (y 5 )⊕ x 5 ⊕y 5 = y 3 ⊕k 5 ⊕k 4 (17)
5
其中, y 3 = F 3 (F 1 (x 0 )⊕ F 2 (F 1 (x 0 )⊕y 0 ⊕k 1 )⊕k 2 ). 可设函数:

(18)
G(x,y) = F 3 (F 1 (x)⊕ F 2 (F 1 (x)⊕y⊕k 1 )⊕k 2 )⊕k 4 ⊕k 5