基于量子计算的Hash碰撞安全性研究

论文摘要

Hash函数作为数字签名的基石，不仅用于检测网络通信信息是否被篡改，而且是保障电子签名、身份认证等多种密码系统安全的关键技术，有着十分重要的作用，目前Hash函数的安全性分析均采用经典计算数学的方法，无法评估其对抗量子计算攻击的能力，因此寻求新的量子计算分析的方法，开展量子密码Hash函数的安全性研究十分必要。随着量子信息技术的不断发展，量子计算技术的研究也在不断进步，基于量子算法进行密码算法的分析研究不仅扩展了量子计算和量子算法的应用范围和应用价值，加深人们对量子算法中一些关键问题的理解，同时对关系到国家安全和重大商业利益的信息安全有着现实的意义。论文着重研究了基于Grover搜索算法与量子计数的Hash函数量子碰撞问题。在具体工作中，本文指出已有的Hash碰撞量子模型中没有考虑Hash碰撞个数未知问题的不足，引入量子计数算法解决了此问题，提出了基于原Grover算法的搜索碰撞模型，又在此基础上，针对搜索空间多碰撞的特点，根据解密度将搜索空间划分提出了改进的量子搜索碰撞模型，并对基于原Grover算法的搜索碰撞模型和改进的量子搜索碰撞模型进行了性能分析，同时本文在已有基本逻辑运算量子线路的基础上，采用自底向上的方法逐层详细设计了迭代型定制函数SHA-1算法和BLAKE算法的量子弱碰撞攻击线路，用于Hash函数量子弱碰撞攻击的Oracle线路设计，也可作为量子计算机芯片集成设计的依据。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究背景及意义
• 1.2 课题研究现状
• 1.2.1 Hash 函数的发展现状
• 1.2.2 课题国内外研究现状
• 1.3 论文主要工作
• 1.4 论文结构
• 第二章 量子计算与 Hash 函数概述
• 2.1 量子计算
• 2.1.1 量子比特
• 2.1.2 量子并行性
• 2.2 量子线路
• 2.2.1 基本逻辑门
• 2.2.2 量子退计算
• 2.3 量子算法
• 2.3.1 Grover 搜索算法
• 2.3.2 量子计数算法
• 2.4 Hash 函数
• 2.4.1 SHA-1Hash 函数
• 2.4.2 BLAKE Hash 函数
• 2.5 本章小结
• 第三章 Hash 函数的量子线路设计
• 3.1 量子基本逻辑线路
• 3.1.1 与、异或运算的量子线路
• 3.1.2 移位运算的量子线路
• 3.1.3 加法、模 N 加法运算的量子线路
• 3.2 SHA-1 的量子线路设计
• 3.2.1 SHA-1 算法的量子线路框架
• 3.2.2 SHA-1 单步运算的量子线路
• 3.2.3 SHA-1 基本函数的量子线路
• 3.3 BLAKE 函数的量子线路设计
• 3.3.1 BLAKE 算法的量子线路框架
• 3.3.2 BLAKE 轮函数的量子置换表
• 3.3.3 BLAKE 基本函数的量子线路
• 3.4 本章小结
• 第四章 Hash 碰撞量子模型的改进
• 4.1 已有 Hash 碰撞的量子模型
• 4.1.1 Hash 碰撞概述
• 4.1.2 已有 Hash 碰撞的量子模型
• 4.2 多目标量子搜索分析
• 4.2.1 Grover 算法的唯一解
• 4.2.2 Grover 算法的多解性
• 4.3 改进的 Hash 碰撞搜索模型
• 4.3.1 量子计数的引入
• 4.3.2 基于原 Grover 搜索算法的碰撞模型
• 4.3.3 改进的量子搜索碰撞模型
• 4.4 本章小结
• 第五章 Hash 量子碰撞模型的安全性评估
• 5.1 量子计数的性能分析
• 5.1.1 量子计数估计值的精确度
• 5.1.2 量子计数的时间复杂度
• 5.2 Grover 搜索算法的性能
• 5.2.1 Grover 算法的迭代次数
• 5.2.2 Grover 算法的成功概率
• 5.3 量子模型的性能分析
• 5.3.1 基于原 Grover 算法的碰撞模型的性能
• 5.3.2 改进的量子搜索碰撞模型的性能
• 5.3.3 与经典 Hash 碰撞攻击算法的比较
• 5.4 本章小结
• 第六章 总结与展望
• 6.1 论文研究工作总结
• 6.2 进一步的工作展望
• 参考文献
• 致谢
• 攻读硕士学位期间发表（录用）的论文