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

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

0 0 0 0 0
x 0 x 1 x 2 x d−2 x d−1
…
F 1 k 1

d−4 rounds
d−3
x 0 F d−2 k d−2 …

d−2 …
x 0 F d−1 k d−1
d−1 …
x 0 F d k d

d−4 rounds
2d−2 …
x 0 F 2d−3 k 2d−3

2d−1 …
x 0 F 2d−2 k 2d−2

d−2 rounds
3d−4 …
x 0 F 3d−3 k 3d−3
…
3d−3 3d−3 3d−3 3d−3 3d−3
x 0 x 1 x d−3 x d−2 x d−1
3d −3 轮 Type-1 型广义 Feistel-FK 结构
图 12

可根据公式 (22) 设函数:

0
0
G(P) = F d−1 (F d−2 (...F 1 (x )⊕ x ⊕k 1 ...)⊕ x 0 ⊕k d−2 )⊕ x 0 ⊕k d−1 ⊕k 2d−1 (23)
0 1 d−2 d−1
,
0
0
n
其中 P = (x , x ,..., x 0 , x 0 , x 0 ) P ∈ {0,1} 且 G(P) ∈ {0,1} n/d . 依据公式 (19)–(23), 我们提出以下针对 3d −3 轮
0 1 d−3 d−2 d−1
Type-1 型广义 Feistel-FK 结构的密钥恢复过程:
0
0
0
0
′
′
′
(1) 选择明文 P = (x , x ,..., x 0 , x 0 , x 0 ) 和 P = (x , x ,..., x 0 ,(x 0 ) , x 0 ) x ( 0 , (x 0 ) ), 查询其对应的密文.
0 1 d−3 d−2 d−1 0 1 d−3 d−2 d−1 d−2 d−2
根据公式 (19)–(23) 可求得:

0
0
′
G(P)⊕G(P ) =F d−1 (F d−2 (...F 1 (x )⊕ x ⊕k 1 ...)⊕ x 0 ⊕k d−2 )
0 1 d−2
0
0
′
⊕ F d−1 (F d−2 (...F 1 (x )⊕ x ⊕k 1 ...)⊕(x 0 ) ⊕k d−2 ).
0 1 d−2
,
0
0
0
0
′
(2) 设 β 1 = F d−2 (...F 1 (x )⊕ x ⊕k 1 ...)⊕ x 0 ⊕k d−2 β 2 = F d−2 (...F 1 (x )⊕ x ⊕k 1 ...)⊕(x 0 ) ⊕k d−2 , 则 β 1 ⊕β 2 = x 0
0 1 d−2 0 1 d−2 d−2
,
⊕(x 0 ) G(P)⊕G(P ) = F d−1 (β 1 )⊕ F d−1 (β 1 ⊕ x 0 ⊕(x 0 ) ) , 可利用 Grover 算法求出 β 1 值.
′
′
′
d−2 d−2 d−2
0
0
0
∗′
0
∗
∗
∗
′
(3) 选择明文 P = (x , x ,...,(x 0 d−3 ) , x 0 d−2 , x 0 d−1 ) 和 P = (x , x ,...,(x 0 d−3 ) ,(x 0 d−2 ) , x 0 d−1 ), 查询其对应的密文. 根据公
0
1
1
0
式 (19)–(23) 可求得:
0
0
∗′
∗
G(P )⊕G(P ) = F d−1 (F d−2 (F d−3 (...F 1 (x )⊕ x ⊕k 1 ...)⊕(x 0 d−3 ) ⊕k d−3 )⊕ x 0 d−2 ⊕k d−2 )
∗
0
1
0
0
′
⊕ F d−1 (F d−2 (F d−3 (...F 1 (x )⊕ x ⊕k 1 ...)⊕(x 0 d−3 ) ⊕k d−3 )⊕(x 0 d−2 ) ⊕k d−2 ).
∗
1
0
β 3 = F d−2 (F d−3 (...F 1 (x )⊕ x ⊕k 1 ...)⊕(x 0 ) ⊕k d−3 )⊕ x 0 ⊕k d−2 β 4 = F d−2 (F d−3 (...F 1 (x )⊕ x ⊕k 1 ...)⊕(x 0 ) ∗
,
0
0
0
0
∗
(4) 设 0 1 d−3 d−2 0 1 d−3
,
∗′
⊕k d−3 )⊕(x 0 ) ⊕k d−2 , 则 β 3 ⊕β 4 = x 0 ⊕(x 0 ) G(P )⊕G(P ) = F d−1 (β 3 )⊕ F d−1 (β 3 ⊕ x 0 ⊕(x 0 ) ), 可利用 Grover 算法
′
′
′
∗
d−2 d−2 d−2 d−2 d−2
求出 β 3 值.
(5) 已知 β 1 和 β 3 值, 异或后可得: