量子时代，加密算法如何应对威胁？

编者按：我们能安全地使用互联网，其实并不是一件易事，有这样一群人一直在默默守护我们——加密算法工程师。微软杰出工程师、微软研究院安全与加密组负责人Brian LaMacchia博士就是他们中的一员，他带领研究团队用最新的算法来保障我们的网络信息安全。在这篇访谈中，他将带领我们一窥加密算法的奥秘，告诉我们量子计算将对加密算法产生怎样的威胁，我们又该如何应对这些挑战。本文编译自微软研究院播客“Cryptography for the post-quantum world with Dr. Brian LaMacchia”。

微软杰出工程师、微软研究院安全与加密组负责人Brian LaMacchia

采访音频

密码学的历史十分悠久，甚至可以追溯到古代，我们知道古罗马人就已经开始简单的凯撒密码来传递信息。到了二十世纪，密码学被越来越多地用于保护无线电等无线通讯，其中最著名的要数二战期间德国的Enigma加密机。而现在，密码学已经被广泛应用到我们生活的方方面面。

加密算法面临的新威胁

在大多数人的眼中，计算机算法都是固定不变的。如果一个人被告知“算法像食品一样有保质期”，他多半会觉得难以置信。事实上，所有的加密算法的安全性都会随时间的推移而减弱或遭到破坏。

加密算法的安全性之所以会慢慢降低，是因为时间越长，人们掌握的破解方式就会越多，拥有的用来破解的计算能力也会越强大。而作为密码学核心的数论在学术上也会获得某些突破，进而产生新的算法。因此，我们今天所依赖的加密算法，未来都将不得不加以改变。

作为安全加密的研究者，我们要通过尝试预测攻击者的动作，来确保加密算法的安全。有时候我们确实能够预感到情况的变化，比如当学术界发布相关进展时，我们会知道是时候更新算法了。但大多数情况下，我们并不能确切预知现在大家通用的加密算法什么时候会遭到破坏。

所以我们通常采取的方法是，自己来担任黑客的角色，尝试攻击自己的算法。由于我们的代码都是公开的，黑客能够轻易获取除了密钥之外的所有相关的算法和程序信息。所以我们将自己的角色切换成黑客，看看能否利用这些攻击者能够获得的信息推断出密钥，破解我们的算法，并估算这些方法的成本，评估这些破解方法是否切实可行。

而在量子时代，情况将发生变化。

量子计算是一种完全不同的计算模型。1994年，量子计算取得了一个关键性的突破，在AT＆T的贝尔实验室，Peter Shor提出了一种量子分解算法，证明了如果有一台足够大的量子计算机，就可以用多项式时间算法来分解因子，使得量子计算机很容易破解目前广泛使用的密码。虽然直到今天，我们也没有造出真正的大型量子计算机，但Peter Shor的研究从理论上证明，一个全新的基本计算模型的出现极有可能颠覆我们已知的所有假定。

因此，从信息加密的角度来看，量子计算给我们带来的影响将是双面的，它既能为计算能力带来大幅度的飞跃，也会促成更强力的攻击手段，加快网络攻击者破解加密算法的速度。这对我们提出了更大的挑战，网络安全面临的威胁会更加严峻，也意味着我们今天依赖的很多系统都必须升级，算法都必须更换，而作为互联网的数亿使用者，我们日常使用的每一个密码都需要频繁地更换。

这场技术革命的影响更体现在它的影响范围之大。人们在互联网上的活动越来越多，也越来越频繁。移动办公、社交网络、银行账户……几乎每一个现代人的生活都离不开加密服务，人们的隐私意识、对网络安全的诉求也都在日渐提高。

当然，量子计算带来的这些威胁的前提是——“如果我们有一台足够大的量子计算机”，那么多大的量子计算机才“足够大”，能彻底地变革我们现在的计算世界？在去年发表在《Asiacrypt》的一篇论文中，我们试图对这一问题进行预测，我们认为量子计算机至少要达到1000个量子比特才会给我们带来灾难性的影响，而未来可能会达到10000个量子比特的量级。而当量子计算机“足够大”的那一天，我们的加密算法就要直面量子计算机带来的威胁了。

推动抗量子算法的国际标准化

我的团队以及世界各地的许多同行，都正在开展广泛的产研合作、国际合作，寻找抵抗量子算法攻击的解决方法。目前的解决方案大多采用传统算法的形式，无需量子计算机，在传统计算机、笔记本电脑甚至手机上都可以运行。但在量子计算机真正出现以前，这些算法的防御效果都还只是未知数。

为了应对量子算法对未来的信息加密带来的挑战，美国国家标准与技术研究院（US National Institutes of Standards and Technology, NIST）正在与学术界、产业界共同开展抗量子算法的研发与标准化工作。学术界和产业界的研究者将各自研发的抗量子计算算法以及开源代码提交给NIST。这些算法在速度、大小和其它性能指标上拥有不同的优缺点，几年后，那些“抗量子特性”最强的新加密算法将获得认证，作为联邦信息处理标准（FIPS）颁布施行。

美国的标准化工作将成为制定抗量子算法国际标准的开端。我们希望全世界共同参与，贡献自己的专业知识和分析能力，最后就强大、无害、安全的算法达成一致，实现国际通用的互操作性。

建立这一通用标准需要我们共同努力，以便在量子时代真正到来的那一天，我们已经做好了新加密算法的准备。

紧锣密鼓地迎接挑战

事实上，量子计算留给我们的准备时间已经不充裕了。这是一个非常现实的问题，对于我们现在传输、存储的信息，几十年后量子计算机将能够轻而易举地破解它们。而且随着数据存储和数据记录的成本越来越低，我们通过公共网络发送的隐私数据都可以被一一记录，成为日后量子算法攻击的对象。那些长期储存的数据和信息将面临尤其大的威胁。

我的团队预测，我们要在大约2030年完成对互联网加密算法的升级，在这剩下的十几年中，还有很多任务亟待我们去解决。我们要抓紧时间研究新算法，并对它们进行分析、测试和评估，推动国际通用标准的建立；我们要设计原型、部署测试，让算法适配现有的基础架构，对我们所有的产品和服务进行升级，应对所有可能的安全漏洞。

另外，我们现在就必须将加密灵活性（cryptographic agility）作为软件架构原则之一——软件的加密方法不能仅仅固定为一种或者少数几种加密算法，而应该可以被方便地重新配置使用其它的加密算法，从而防止某种加密算法的突然失效。

因此，我认为对量子时代加密算法的研究时间紧迫，虽然现在要研究的其它安全议题很多，但我们仍然要重视抗量子算法的发展，加快研发和投入使用的进程。但是，我们也不应该把所有希望全都寄托在抗量子算法上，毕竟这些算法没有经受过长期的检验。

在量子计算机出现前后的过渡期，最安全、合理方案是混合方案——现有最佳经典算法与抗量子算法的组合，既使用经历过去数十年积淀和检验的最有效的经典算法，又新增了针对量子算法的一些新的保护措施。

了解更多后量子时代的加密算法研究项目，请访问：

https://www.microsoft.com/en-us/research/project/post-quantum-cryptography/

你也许还想看：

感谢你关注“微软研究院AI头条”，我们期待你的留言和投稿，共建交流平台。来稿请寄：[e-mail]。