量子计算是指以光子、电子、原子等微观粒子为信息载体,基于量子力学规律进行的信息处理过程,其基本规律包括量子态相干性、量子态纠缠性、量子态叠加性、量子不可克隆原理等。
量子计算基于微观粒子的量子态叠加效应,可以对所有的状态进行并行计算。例如,一个4比特的量子寄存器可同时表达0-15的所有16个数值,针对该寄存器的操作会同时作用到所有16个数值上。表面看来,这种指数级的并行处理能力能对任何计算困难问题进行暴力搜索求解。但量子计算的输出结果是叠加态,很难从中获取真正答案。目前只有秀尔算法能基于量子傅立叶变换提取出函数周期,可以破解现代公钥密码依赖的因子分解问题与离散对数问题,对于其他无法归结成周期问题的困难问题,目前还不能得到多项式复杂度的求解算法。
需要特别指出的是,虽然加拿大的量子计算机制造公司D-Wave已经制造并出售了一系列量子计算机,然而其制造的量子计算机并不能运行秀尔算法,因此不会给基于因子分解与离散对数的密码算法构成直接威胁。
量子技术除了可以用强大的并行计算能力攻击传统的密码算法之外,其独特的物理特性也能用来设计新的密码算法和密码协议,学术界称之为量子密码。当前量子密码仅有量子密钥分配协议的研究相对来说成熟,其他协议与算法还在研究中。
最典型的量子密钥分配协议是1984年提出的BB84协议,该协议基于单光子实现通信双方的密钥协商。由海森堡测不准原理,窃听者的任何测量动作都会对通信系统产生无法逆转的于扰。
因此,任何非法的窃听均会被合法的收发双方发现,因而保证了密钥分配协议的安全性。
量子计算提升了密码分析能力,但也加速了密码创新能力。基于量子计算构建完善的密码学体系是密码学发展的趋势之一。
