下载掌阅APP，畅读海量书库
立即打开
当今信息安全领域广泛使用的公钥密码体制主要都是基于经典计算机“难以求解”的数学问题所设计构造的。例如，RSA基于大整数分解问题，Diffie-Hellman和ElGamal基于离散对数问题，ECC基于椭圆曲线离散对数问题。具体来说，在经典计算范式（Classic Computing Paradigm）下，RSA、Diffie-Hellman和ECC等密码算法所依赖的底层数学问题是足够困难而无法在指数时间 O （ n 2 n ）内求解的 [14] ，其中 n 代表被分解的整数或离散对数的参数。一旦上述数学问题可以在一个合理的时间复杂度（如多项式时间）下求解，则该解决方案就可以用来破解相关的密码算法并还原出密钥和原始加密信息。
1994年，贝尔实验室的数学家Peter Shor首次论述了通过使用能执行量子算法的量子计算机，可以在多项式时间 O （ n 2 ）内求解大整数分解问题 [15] 。在对Shor提出的量子算法进行改进后，同样可以有效求解（椭圆曲线）离散对数问题。Shor的研究发现迅速掀起了世界范围内量子计算机和量子算法的研究浪潮：一方面，诸如Grover搜索算法、基于量子傅里叶变换和基于量子遍历的量子算法层出不穷，显著缩短了传统公钥密码体制所依赖数学问题的求解时间 [16] ；另一方面，大量的研究工作朝着设计出实际可行的、可执行量子算法的、拥有强大算力的量子计算机这一目标而不断向前推进。据专业人士估计，破解2048位强度的RSA密钥可能需要当今最快的超级计算机耗费80年以上，而运行Shor算法的量子计算机只需要不到8h就可以完成。2008年，中国科学技术大学潘建伟教授领导的研究团队率先在光量子计算机上实现了量子分解算法。2015年，全球第一家量子计算公司D-Wave宣布开发出了一种1000量子比特（Qubit）的新型处理器。2017年，IBM公司宣布推出全球首个商用的量子计算服务。量子计算机和量子算法的快速发展，对现有公钥密码体制造成了巨大冲击。在量子计算机面前，传统公钥密码体制通过增加密钥长度和改变参数来抵御安全攻击的方式不再有效。2019年10月23日， Natrue 上刊登了Google公司关于实现“量子霸权”（Quantum Supremacy）的论文 [17] ，介绍了Google公司量子硬件首席科学家John Martinis所在团队设计的具有53量子比特的Sycamore处理器（即“悬铃木”），可在200s内完成IBM超级计算机Summit需要花费1万年才能完成的计算任务。2020年12月4日，中国科学技术大学宣布潘建伟院士所在团队成功构建了76个光子量子比特（Photonic Qubit）的量子计算原型机“九章”，只需200s即可求解5000万个样本的高斯玻色取样，而超级计算机“富岳”完成相同计算需要6亿年。“九章”这一研究成果在 Science 上同步发表 [18] ，牢固确立了我国在国际量子计算研究领域中的第一方阵地位。在经典计算机中，使用了由电平（电压）表征的比特（bit）来对信息进行存储，且比特值只能为0或1中的一个。而在量子计算机中，量子计算所使用的量子比特则不再是一个简单的0或1了。1量子比特是1个展开的二维空间，其遵循量子力学的规律，可同时为0和1。这是一种被称为“叠加态”（Superposition）的属性。同理，如果拥有2量子比特，就可以同时具备4（2 2 ）个计算状态；如果拥有333量子比特，将会具备2 333 ，即1.7 × 10 100 个计算状态，这比宇宙中原子数目的总和还要多。在这种特性下，量子比特的计算状态会随着量子比特的数量增加而呈“指数级”增长，使量子计算机在探索一个问题时，可能拥有众多解决方案，以实现高速并行求解。
虽然目前量子计算机还远未达到商用阶段，但埃森哲公司（Accenture）的技术分析报告 [19] 指出：根据学术界的共识，在2028年之前，量子计算机将具备足够大的规模来实施Shor算法并能攻破当前所使用的传统公钥密码体制。随着研究人员在增加量子比特寿命方面不断取得重大研究进展 [20] ，上述情形可能在2026年就会发生。可以看到，Google公司在2019年所设计的“悬铃木”实际上只能在-273.12℃这一超低温环境下正常运行。我国于2020年提出的“九章”却可以整体运行在正常的室温环境下。这也反映了量子计算机技术一直都在突飞猛进。尽管在理论上真正实现了一个通用容错的量子计算机需要100万量子比特，且每量子比特的操控精度要求为99.8%以上，但我国相关研究团队和Google公司均制订了相似的研究计划：预计在未来5年实现1000量子比特的原型机。这样就能比经典计算机更快求解一些实际的密码学应用，并且在未来10年完成100万量子比特这一极具挑战性的研究目标，初步实现商用量子计算机。
在实际可用的量子计算机面前，传统公钥密码体制所基于的数学难题将可在多项式时间内被轻易求解，进而依赖传统公钥密码体制而构建的信息安全系统及各种应用将面临严峻的安全攻击，甚至是被完全破解的潜在威胁。企业和组织必须确保在未来量子计算机的攻击下，使用传统加密方案加密的敏感数据仍然能保持多年内不可被解密。量子计算机的迅猛发展在给信息安全领域带来威胁的同时，也点燃了研究能抵御量子计算攻击的密码算法的火花。对于对称密码体制，以最常使用的AES-128加密算法为例，破解AES-128最有效的方法是使用暴力破解来搜索并找到正确的密钥。由于量子计算机在执行Grover搜索算法后可明显加速对AES-128的暴力破解，因此研究者认为应当加倍AES-128所使用的密钥长度来实现量子计算机下128位的安全级别，即使用AES-256来替代常用的AES-128即可。对于传统公钥密码体制，由于量子计算机在执行Shor算法后可在多项式时间内对其完成求解，增加密钥长度并不能抵御量子计算攻击，因此研究者开始研究由不受量子计算攻击影响的数学问题来构建新型公钥密码算法，以在未来全面取代传统公钥密码体制 [21] 。