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

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

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

9 总 结
近年来, 针对分组密码结构的量子攻击研究, 主要是在 Q2 模型下提出基于 Simon 算法的量子区分器, 并利用
Grover Meets Simon 方法拓展更多轮数. 但是对于更有实际意义的 Q1 模型, 分析分组密码结构的一些缺陷, 再辅
以量子算法来加速计算, 从而实现密钥恢复攻击的研究相对较少. 本文提出的低数据密钥恢复攻击方法可以有效
评估分组密码结构在 Q1 模型的安全性. 针对 3 轮 Lai-Massey 结构, 相比于其他量子攻击, 本文的方法不仅仅需
O(1) 数据, 而且属于 Q1 模型, 在复杂度乘积 (时间×数据×经典存储×量子比特) 评估上降低了 n2 n/4 因子. 针对 6
轮 Misty 结构, 本文的方法依然保留着低数据复杂度的优势, 尤其是 6 轮 Misty L/R-FK 结构, 在复杂度乘积评估上
降低了 2 n/2 因子. 对于 9 轮 3 分支 Type-1 型广义 Feistel 结构, 与其他量子攻击在复杂度乘积评估上保持一致, 本
文的方法依然保留着低数据复杂度的优势且属于选择明文攻击. 此外, 本文也给出了针对类 SMS4 广义 Feistel 结
构和类 MARS 广义 Feistel 结构的低数据密钥恢复攻击方法.
References:
[1] Feistel H. Cryptography and computer privacy. Scientific American, 1973, 228(5): 15–23. [doi: 10.1038/scientificamerican0573-15]
[2] Even S, Mansour Y. A construction of a cipher from a single pseudorandom permutation. Journal of Cryptology, 1997, 10(3): 151–161.
[doi: 10.1007/s001459900025]
[3] Lai X J, Massey JL. A proposal for a new block encryption standard. In: Proc. of the 1990 Workshop on the Theory and Application of
Cryptographic Techniques. Aarhus: Springer, 1990. 389–404. [doi: 10.1007/3-540-46877-3_35]
[4] Matsui M. New block encryption algorithm MISTY. In: Proc. of the 4th Int’l Workshop on Fast Software Encryption. Haifa: Springer,
1997. 54–68. [doi: 10.1007/BFb0052334]
[5] Zheng YL, Matsumoto T, Imai H. On the construction of block ciphers provably secure and not relying on any unproved hypotheses. In:
Brassard G, ed. Advances in Cryptology—CRYPTO 1989. New York: Springer, 1990. 461–480. [doi: 10.1007/0-387-34805-0_42]