基于Grover量子搜索算法的MD5碰撞攻击模型  

MD5 Collision Attack Model Based on Grover’s Quantum Search Algorithm

作　　者：张兴兰[1] 李登祥 ZHANG Xinglan;LI Dengxiang(School of Computer Science,Beijing University of Technology,Beijing 100124,China)

机构地区：[1]北京工业大学计算机学院,北京100124

出　　处：《信息网络安全》2024年第8期1210-1219,共10页Netinfo Security

基　　金：国家自然科学基金[62202017]。

摘　　要：量子计算天然的并行性使其在密码学领域具有巨大潜力,而在信息安全领域,Hash函数的安全性至关重要。因此,后量子密码学概念的提出使得Hash函数在后量子时代的研究价值凸显。文章提出了一种基于Grover量子搜索算法的MD5碰撞攻击模型,运用模差分分析法,通过对输入的量子叠加态进行约束搜索以找到满足碰撞条件的目标态,再根据差分构造出与之相碰撞的消息。此外,文章探讨了量子搜索算法中的迭代过程及其关键操作,设计了相应的Oracle黑盒的量子线路,并对其进行性能分析,结果表明,与经典算法相比,该模型显著降低了攻击的计算复杂度,为后量子密码时期Hash函数的研究提供了新的思路和方法,也为防御此类攻击提供了有益参考。Quantum computing’s inherent parallelism underscores its immense potential in cryptography and in information security,where Hash function security stands paramount.Consequently,the emergence of post-quantum cryptography underscores the importance of Hash functions research in this new era.This paoper proposed an MD5 collision attack model based on Grover’s quantum search algorithm.This model applied modular difference analysis to constrain input quantum superposition states.The goal was to seek the target state meeting collision criteria.Upon finding it,this paper constructed a colliding message based on the identified difference.Moreover,this paper delved into the iterative procedures and pivotal operations of quantum search algorithms. This paper also crafted tailored Oracle black box quantum circuits, and assessed the performance of these circuits to evaluate their effectiveness. Findings reveal that this model drastically cuts down on computational intricacies during attacks. It presents novel perspectives and approaches for the research of Hash functions in the post-quantum cryptography era. It also provides useful reference for defending against such attacks.

关 键 词：量子计算 碰撞攻击 GROVER量子搜索算法 MD5算法 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]