分组密码算法和杂凑函数的Grover量子搜索分析研究

论文摘要

Grover量子搜索算法以其研究对象的普遍适用性受到了众多学者的关注,利用量子本身具有的并行性,Grover算法能够将搜索时间的复杂度降低为O （ N ）。目前对于Grover算法的研究较多集中在改进算法上,而针对密码学分析的专题研究很少,并且在经典计算机上对密码算法的分析多采用数学方法,在计算复杂度的优化上不够理想。基于量子搜索算法进行密码算法的分析研究不仅扩展了量子计算和量子算法的应用范围和应用价值,加深人们对量子算法应用中一些关键问题的理解,同时对关系到国家安全和重大商业利益的信息安全有着现实的意义。本文分别针对分组加密算法和杂凑函数建立了相应的量子搜索分析模型。该模型可作为Grover量子搜索中最重要的量子黑箱Oracle参与到Grover迭代中进行运算,最终搜索分组加密算法密钥或杂凑函数碰撞实例的时间复杂度均能得到O （ N ）的降低。在具体工作中,本文针对基本逻辑运算进行了量子线路的详细设计,并对其进行仿真实验,验证了线路的正确性。在对分组密码的分析上,本文结合了传统并行计算的方式,使密钥搜索的时间复杂度在二次加速的基础上得到进一步的提速。在杂凑函数的分析上,根据算法具有的扩散性,将搜索的时间复杂度基数集中到单个寄存器的长度上。同时,本文针对数据加密标准DES和MD5及SHA-256算法分别进行了量子线路的设计,可用于后续的仿真实验,也可作为量子计算机芯片集成设计的依据。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 课题研究背景及意义
• 1.2 课题研究现状
• 1.2.1 分组密码分析方法
• 1.2.2 杂凑函数碰撞分析方法
• 1.2.3 课题国内外研究现状
• 1.3 论文主要工作
• 1.4 论文结构
• 第二章 量子算法理论基础
• 2.1 量子计算
• 2.1.1 量子比特
• 2.1.2 量子寄存器
• 2.2 量子搜索算法
• 2.3 Grover 量子搜索算法
• 2.3.1 量子黑箱Oracle
• 2.3.2 Grover 算法的过程
• 2.3.3 Grover 算法的几何描述
• 2.3.4 与传统搜索算法的比较
• 2.4 小结
• 第三章 量子线路原理与设计
• 3.1 基本逻辑门
• 3.2 回退计算基本原理
• 3.2.1 回退计算目的
• 3.2.2 实现方法描述
• 3.3 基本逻辑运算的量子线路设计
• 3.3.1 与、与非和异或运算的量子线路
• 3.3.2 移位运算的量子线路
• 3.3.3 模N 加法运算的量子线路
• 3.4 仿真实验
• 3.4.1 实验环境
• 3.4.2 基本逻辑运算的仿真实验
• 3.5 小结
• 第四章 分组密码密钥的并行量子搜索分析
• 4.1 分组密码概述
• 4.2 并行量子密钥搜索方案
• 4.2.1 量子密钥搜索模型
• 4.2.2 并行量子搜索性能分析
• 4.3 DES 算法的量子线路设计
• 4.3.1 DES 算法的量子线路框架
• 4.3.2 置换盒的量子线路
• 4.3.3 选择扩展运算的量子线路
• 4.3.4 选择压缩函数的量子线路
• 4.4 仿真实验
• 4.4.1 条件相移运算的仿真实验
• 4.4.2 比较模块的仿真实验
• 4.5 小结
• 第五章 杂凑函数的量子碰撞线路设计
• 5.1 杂凑函数概述
• 5.1.1 MD5 杂凑函数
• 5.1.2 SHA-256 杂凑函数
• 5.2 杂凑函数的量子碰撞模型
• 5.3 MD5 的量子线路设计
• 5.3.1 MD5 算法的量子线路框架
• 5.3.2 MD5 单步运算的量子线路
• 5.3.3 MD5 基本函数的量子线路
• 5.4 SHA-256 的量子线路设计
• 5.4.1 SHA-256 算法的量子线路框架
• 5.4.2 SHA-256 单步运算的量子线路
• 5.4.3 SHA-256 基本函数的量子线路
• 5.5 小结
• 第六章 总结与展望
• 6.1 论文研究工作总结
• 6.2 进一步的工作展望
• 参考文献
• 致谢
• 攻读硕士学位期间发表的论文