|量客江湖系列01|破RSA大盗——Peter Shor

编  辑:王嘉雯    审 校:王新文

(全文约3000字,预计阅读用时8分钟)

20世纪80年代,物理学家们首次提出量子计算机的构思时,听起来十分乐观,但只能通过文字的方式来呈现。
后来在1995年,也就是25年前的上个月,应用数学家Peter Shor发表了一篇论文,改变了当时的一切。
图1|Peter Shor(来源:TQD)
Peter Shor的论文
Shor的论文展示了量子计算机是如何克服一个关键问题的。这些机器将以量子比特的形式处理信息,量子比特是普通比特的量子版本,可以同时处理0和1。
但众所周知,量子态易受到噪音的影响,从而导致信息丢失。他的纠错技术(用于检测噪声引起的错误)展示了如何使量子信息更加可靠。
图2|Peter Shor在1995年发表的论文(来源:美国物理学会)
Shor目前在剑桥的麻省理工学院工作,同时,他也是一位出版过诗集的诗人。
早在1994年,他就发现了如何使用量子计算机的模型进行计算,这让物理学界和计算机科学界感到震惊。
他提出了一个算法——质因数分解算法,可以让量子计算机以闪电般的速度将整数分解成质因数。今天的大多数互联网流量是基于大质数的加密技术保护的。破解这些代码十分困难,因为经典计算机在分解大型整数时很慢。
图3|Peter Shor在1994年发表的论文(来源:电气电子工程师学会)
量子计算机现在已经成为现实,尽管它们还不足以计算两位数以上的数字。但量子计算机威胁互联网加密只是时间问题。
访谈内容
《自然》杂志采访了Shor,询问了关于他的工作所带来的影响——以及互联网安全的发展趋势。
1. 在你的质因数分解算法出现之前,量子计算机纯粹就是为了满足理论层面的好奇心吗?
我的论文的确使人们明白,这些机器可以做一些有用的事情。
计算机科学家Daniel Simon,在我得出我的结论之前,他就解决了一个他提出的问题,该问题表明量子计算机(比普通计算机)快得多。
但是即使采用Simon的算法,也无法得知这些机器是否可以发挥它们的用处。
2. 在宣布了你的质因数分解算法后,人们的反应如何?
起初,我只得到了一个不完整的结果。后来,在1994年4月,我在贝尔实验室做了一个关于这个选题的报告。
消息传得非常快,那个周末,计算机科学家Umesh Vazirani就给我打了电话说,“我听说你可以在量子计算机上进行质因数分解,告诉我你是怎么做到的。”
图4|Umesh Vazirani(来源:伯克利工程学院)
那时,我其实还没有真正解决质因数分解的问题。但很神奇的是,报告结束的五天内,我的结果在人们的奔走相告中,变成了质因数分解成功。而在这五天里,我也确实解决了分解的问题,于是我就可以告诉Umesh我是怎么做到的了。
当时人们都在向我索要我还未完成的论文,所以我只能把粗稿拿给他们看了。
3. 但是仍有许多专家认为,量子计算机会在完成计算之前就丢失信息是吗?
其中一个反对意见是,在量子力学中,如果你测量一个系统,你会不可避免地干扰到它。
我演示了如何在不测量计算的情况下测量误差——然后你就可以修正误差,而不破坏计算。
在我1995年发表了关于纠错的论文之后,一些怀疑论者也确信量子计算是可行的。
4. 纠错依赖于“物理”和“逻辑”量子比特,这两者间的区别是?
当你写下一个量子计算机的算法时,你会假设量子比特是无噪声的。这些无噪声的量子比特就是逻辑量子比特,而我们的量子计算机中不存在没有噪声的量子比特。
事实上,如果我们试图在没有噪声干预的环境下,运行我们的算法。那错误的发生,是不可避免的。
物理量子比特是量子计算机中的含噪声的量子比特之一。为了在运行我们的算法时,不出现任何错误,我们需要使用物理量子比特对逻辑量子比特进行编码,这其中会用到量子纠错代码。
图5|量子比特(来源:medium)
而我们所知道的最好的方法,是有相当大的开销的,此方法为每个逻辑量子比特都提供了诸多物理量子比特。
要计算出这项技术还需要多少量子比特是相当复杂的。如果你想用表面码(目前最佳选项)来建造一台量子计算机,那么每一个逻辑量子比特,大约需要100个物理量子比特来支持,甚至更多。
5. 在2019年,谷歌展示了其“量子优势”——即54个量子比特的量子计算机,它可以解决一个在经典计算机上耗时冗长的问题,你的反应是什么?
这绝对是一个里程碑。它表明,量子计算机可以比经典计算机做得更好——至少在以人为主导因素的问题上。
即便谷歌做了一些宣传活动,但毋庸置疑的是,这台量子计算机的确让人印象深刻。
在它能创造出奇迹之前,还需要一些完善工作。另外,初创公司IonQ制造的量子计算机,在某种程度上可能比谷歌和IBM的都要好(参阅:IonQ发布QV400万超强量子计算机)。
6. 当量子计算机可以分解大质数时,它们就可以破解无处不在的互联网加密系统“ RSA”,这点你如何看待?
是的,但是第一个破解RSA的人,要么是NSA(美国国家安全局),要么是一些其他大型机构。
一开始,这些计算机运行会非常缓慢。如果你有一台每小时只能破解一个RSA密钥的计算机,那你肯定将其用于破解国家级别安全风险的信息。
比起用量子计算机阅读普通大众的电子邮件,美国国家安全局有更重要的事情可以做——他们将阅读中国大使的电子邮件,哈哈。
7. 有没有一种加密系统可以取代RSA,而且在量子计算机时代也是安全的——即“后量子加密”?
我认为我们会有可以代替RSA的后量子密码系统
但RSA不是当下最重要的问题,当务之急是,还有其他方法可以破坏互联网的安全,比如编程不良的软件、病毒,会将信息发送给一些恶意玩家。
我认为用安全的后量子密码体制,来取代RSA的最大障碍,是我们的不懈努力及编程时间。我认为这是我们知道如何去做的事情,只是我们是否能及时做到还是未知数。
图6|RSA算法(来源:Exabeam)
8. 会不会出现让我们措手不及的风险呢?
会的。为了修复2000年出现的错误(千年虫),人们付出了巨大的努力。
而人们需要付出更大的努力,才能切换到后量子时代。但如果我们等得太久,那就太迟了。
参考链接:
[1]https://www.nature.com/articles/d41586-020-03068-9
[2]https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.R2493
[3]https://ieeexplore.ieee.org/document/365700
[4]https://link.springer.com/article/10.1007/s00283-020-10022-0
[5]https://www.nature.com/articles/d41586-019-02936-3
[6]https://www.nature.com/articles/d41586-019-03213-z

声明:此文出于传递更多信息之目的。若有来源标注错误或侵权,请作者持权属证明与我们联系,我们将及时更正、删除


延 伸 阅 读
01    全球十大量子初创公司介绍:IonQ
02    IonQ揭幕新量子数据中心和神秘加盟者
03    霍尼韦尔发布新一代量子计算机H1
04    半导体双量子比特保真度达99.99%
05    抗得住量子计算机攻击的算法
06    用于表征大型量子计算机噪声的算法
(0)

相关推荐