量子计算如何威胁现代密码体系？怎么应对？

无论是微信聊天还是网上购物，密码都在保护着我们的财产与隐私安全。这种精巧而复杂的数学算法是现代信息社会的安全基石，但量子计算的迅猛发展正让这一切经受挑战。

密码

现代社会的安全基石

小到个人通讯，大到机要信息传输，都需要严格的密码保护。目前，常用的RSA加密算法基于一个简单的数论事实：即将两个大素数相乘十分容易，但是想要对其乘积进行质因数分解却极其困难，因此可以将乘积公开作为加密密钥。

例如在一套RSA算法下，给定一对3*5=15相关的公私密钥，选定其中一个作为私钥由用户自己保存，另一个密钥作为公钥公开。

当把3和5更换为2048位的素数A和B时，用C表示A和B的乘积。那么验证A乘以B是否等于C，是一件计算起来比较简单的事，即检验用户输入密钥正确性轻而易举；但是要从C倒推回A和B，却及其困难，单个经典计算机所需运算时间超过 10^14年，所以以此密钥进行的加密几乎无法被经典计算破解。

此外，ECC算法也是目前主流的非对称加密算法，通常被用于密匙协商和数字签名。其特点为加密复杂，基于椭圆曲线有限域进行运算，因而难以被针对整数域加密的常规算法破解。

相较于RSA算法，ECC算法优势是可以使用更短的密钥，得到与RSA算法相当或更高的安全性。

图片来自网络

基于这种极高破解难度带来的强大安全性，RSA和ECC算法成为了现代电子信息加密的基础。这两种算法被广泛应用于智能卡密钥、二代身份证、虚拟货币、匿名网络、数字证书和通信保密协议等硬件和软件领域中，对相关的金融、互联网等行业的信息安全极为关键。

量子计算

正严重威胁信息安全

在经典计算时代，这种精巧而复杂的数学算法能够抵抗绝大多数密码攻击。但量子计算以及相应量子算法的出现让RSA加密在源头上出现了危机。

Peter Shor提出了Shor算法。图片来自网络

量子计算基于量子叠加特性，“量子比特”可以同时是0和1，其计算效率远远高于经典计算机。

1994年，美国科学家Peter Shor提出了著名的Shor算法，在理论上展示了一个足够强大的量子计算机能将质因数分解的时间复杂性降到多项式时间内。

Shor算法的出现，意味着RSA加密在理论上已经不再安全。随着量子计算软硬件技术飞速发展，现代密码体系的崩溃也不再是理论上的风险。

密码量子破译

研究进展

• 1997年，Peter Shor进一步提出了基于量子计算的大数质因子分解算法可应用于质因子分解和离散对数问题，而椭圆曲线加密（ECC）算法的底层实质上也是一种离散对数问题（DLP）。这就使得另一种主流加密方案也出现了危机。

• 2016年，美国麻省理工学院与奥地利因斯布鲁克大学的研究者，第一次以可扩展的方式在量子计算机中实现了Shor算法。

• 2017年到2019年，瑞士皇家理工学院的Ekerå和Haståd先后发表了关于Shor算法的改进文章，提出了专注于DLP的改进量子算法。该算法大大降低了Shor算法的复杂度。

• 2019年12月，Ekerå与IBM合作发表了关于目前主流使用的最长的2048位RSA密码的量子破译算法理论评估文章，指出使用约2000万个噪声量子比特可以在8小时之内完成相关破译工作。

• 2021年3月，巴黎萨克雷大学和吉夫续尔伊凡特理论物理研究所的相关研究人员发表了关于使用13436个物理量子比特在177天内完成2048位RSA密码破译的理论文献。

• 2021年4月，本源量子公司与国内多家金融机构以及相关合作伙伴发起了量子破密算法的研究合作，并于近日取得重要进展，减少了运行算法所需的量子比特数量。

本源量子金融行业生态应用联盟

量子计算

破密原理

量子计算机如何破解RSA密码呢？我们以Shor算法破解RSA加密为案例进行讲解。

RSA加密的核心环节是由两个质数相乘得到大数的过程，正向简单而逆向极其困难。因此，如何由给定大数分解得到两个质因数是破解RSA加密的关键。

1994年Peter Shor提出了一种破解思路，将原质因数分解问题切换为量子计算机便于求解的离散对数问题。

Shor算法将原本的质因数分解问题通过欧拉定理转换成了一个对于幂运算后求模运算过程的求逆，并最终等价于对模指运算的周期求解问题，该问题的求解难度几乎是指数级的，而量子计算机则可以发挥其强大的计算性能以多项式时间完成指数级困难问题求解。简而言之，Shor算法基于相关数学知识可以将质因数分解问题转换为模指逆元求解问题。

密码量子破译

本源取得新成果

本源量子近期在密码量子破译研发上取得重要进展，可以在运算时节约更多的量子比特数。

同时为了更好地进行算法展示，让公众更多地了解密码量子破译带来的便利，本源量子还在自主研发的量子计算云平台上上线了一款shor算法演示应用，这也是全球首款Shor量子算法破解密码的演示应用。

演示应用地址:

https://qcloud.originqc.com.cn/application

本源量子云 信息安全应用

今年4月，本源量子公司与国内多家金融机构以及相关合作伙伴发起了密码量子破译算法的研究合作。

本源量子统合现有量子破密算法的理论研究成果，依靠量子硬件、量子测控系统和量子软件全栈式的先进研发体系，对相关量子算法进行改进优化，开发出基于独有的改进型量子模数算术组件的RSA及ECC量子破密方案，减少了运行算法所需的量子比特数量，相关成果较微软在2020年的同类成果具有一定优势。

本源量子相关人员表示：“该成果可理解为节约了量子比特，打个比方，以前用50个量子比特做成的事情，现在只需要用40个量子比特。这就大大节约了运算成本。”

演示应用基于改进的Shor量子破密算法，通过数据化对比经典算法、提供互动展示和扩展学习资料的形式，以RSA和ECC两大主流密码为对象，深入浅出地向广大量子计算爱好者阐述了量子计算在密码破解领域的应用情况。

经典算法与量子算法对比

量子计算时代

信息如何安全

利用Shor算法打造“杀手级”应用需要依赖可扩展的大规模量子计算机，由于硬件限制，此前这种算法并没有在工程上使用。但随着量子计算算法和硬件的快速突破，参考所谓“量子摩尔定律”，RSA和ECC加密算法将在未来10年内宣告失效。

现代社会如何应对这种挑战？构建自主可控的量子计算机是主要途径。

本源悟源超导量子计算机

其实，量子计算并非站在密码学的对立面，无论在密码设计还是密码破译领域，量子计算都可以起到一定的辅助作用。研究人员可以通过量子计算机强大的并行计算能力、独特的组合优化求解能力等特性解决传统算法不擅长的问题。

同时，科学家们还计划发展专用型量子计算用于其他密码部件设计及公钥密码分析的潜能及拓展。

而针对抗量子密码的研究也在进行当中，美国国家标准技术研究所（NIST）计划于2022年发布抗量子计算加密标准。

可见，研发实用型的量子计算机是实现Shor算法和维护未来信息安全的关键。在这条关乎信息安全乃至国家安全的赛道上，我们不容有失。

参考资料：

新智元.《科学》重磅论文:量子计算核心突破，密码或成摆设.

https://mp.weixin.qq.com/s/1h9bwU9e0mRIhOaxAwqM0w

王潮,姚皓南,王宝楠,胡风,张焕国,纪祥敏.量子计算密码攻击进展.计算机学报,2020

光子盒.最新研究:只需1.3万个量子比特，即可破解2048位RSA加密.

https://mp.weixin.qq.com/s/yedpnPQMmNBfpZEo857tFA

kaspersky daily.量子计算机和加密技术.

https://www.kaspersky.com.cn/blog/quantum-computing-vs-data-encryption/11721/

文 / 李进、刘焱

（为保证知识传播完整，本文部分内容参考网络，如有侵权，请联系删除）