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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2025,36(7):3321−3338 [doi: 10.13328/j.cnki.jos.007218] [CSTR: 32375.14.jos.007218] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
分组密码结构的低数据量子密钥恢复攻击

许垠松 1 , 罗宜元 2 , 董晓阳 3 , 袁 征 4

1
(北京邮电大学 网络空间安全学院, 北京 100876)
2
(惠州学院 计算机科学与工程学院, 广东 惠州 516007)
(清华大学 高等研究院, 北京 100190)
3
4
(北京电子科技学院, 北京 100070)
通信作者: 罗宜元, E-mail: luoyy@hzu.edu.cn
摘 要: 在 Q1 量子模型下, 针对 Lai-Massey 结构、Misty 结构、Type-1 型广义 Feistel 结构、类 SMS4 广义
Feistel 结构和类 MARS 广义 Feistel 结构, 提出了低数据量子密钥恢复攻击. 该攻击仅需选择常数项级别规模的明
密文, 通过分析分组密码结构的加密过程, 利用 Grover 算法对某些中间态进行搜索计算, 从而恢复密钥. 且该攻击
属于 Q1 模型, 相比于 Q2 模型, 无需量子叠加查询, 更具有实际意义. 对于 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 结构的低数据量子密钥恢复攻击, 补充了其在 Q1 模型下的安全性评估.
关键词: Lai-Massey 结构; Misty 结构; Type-1 型广义 Feistel 结构; 类 SMS4 广义 Feistel 结构; 类 MARS 广义
Feistel 结构; 密钥恢复攻击
中图法分类号: TP309

中文引用格式: 许垠松, 罗宜元, 董晓阳, 袁征. 分组密码结构的低数据量子密钥恢复攻击. 软件学报, 2025, 36(7): 3321–3338. http://
www.jos.org.cn/1000-9825/7218.htm
英文引用格式: Xu YS, Luo YY, Dong XY, Yuan Z. Low-data Quantum Key-recovery Attack on Block Cipher Structures. Ruan Jian
Xue Bao/Journal of Software, 2025, 36(7): 3321–3338 (in Chinese). http://www.jos.org.cn/1000-9825/7218.htm

Low-data Quantum Key-recovery Attack on Block Cipher Structures
3
1
2
XU Yin-Song , LUO Yi-Yuan , DONG Xiao-Yang , YUAN Zheng 4
1
(School of Cyberspace Security, Beijing University of Posts and Telecommunications, Beijing 100876, China)
2
(School of Computer Science and Engineering, Huizhou University, Huizhou 516007, China)
3
(Institute for Advanced Study, Tsinghua University, Beijing 100190, China)
4
(Beijing Electronic Science and Technology Institute, Beijing 100070, China)
Abstract: In the Q1 model, this paper proposes a low-data quantum key-recovery attack against Lai-Massey structures, Misty structures,
Type-1 generalized Feistel structures, SMS4-like generalized Feistel structures and MARS-like generalized Feistel structures. This attack
only needs to select constant-sized plain-ciphertexts, analyze the encryption process of block cipher structures, and recover the key by
searching and calculating some intermediate states and round keys using Grover’s algorithm. This attack belongs to the Q1 model, which

* 基金项目: 国家自然科学基金 (62072207); 广东省基础与应用基础研究基金 (2022A1515140090); 北京邮电大学博士创新基金
(CX2022140)
收稿时间: 2023-08-04; 修改时间: 2024-04-03; 采用时间: 2024-04-24; jos 在线出版时间: 2024-09-30
CNKI 网络首发时间: 2024-10-08