量子之矛—后量子计算时代你的系统还安全吗？

Google在今年的3月份，推出一款72个量子比特的通用量子计算机Bristlecone，实现了1%的错误率，性能超越了IBM去年11月份发布的 50位量子比特的量子计算机。这一成果引起人们广泛的热议和讨论，按此速度的发展，量子计算机的计算能力将大大得到提升。对于人工智能（AI）领域来说，这是一大福音；而对于网络与信息安全领域来说，却是一个不折不扣的坏消息。举一个直观的例子：破解一个RSA密码系统，用当前最大、最好超级计算机需要花1025 年（而宇宙的年龄为1.38×1010 年），但用一个具有足够量子比特的量子计算机进行破解，在不到1秒内即可完成。众所周知，RSA公钥加密系统广泛应用于电子政务、电子银行、电子交易和操作系统等。曾经认为十分安全的加密系统在量子计算机面前，却似乎不堪一击。

量子计算机真的可以实现吗？量子时代的到来，你的系统还安全吗？如果不安全，有什么好的防范措施？带着这些问题，我们一一进行解读和介绍。建议阅读用时5-8分钟。

一、 什么是量子计算机？

在介绍量子计算机前，先明确量子计算 (Quantum Computation) 这个概念。所谓量子计算，就是利用量子态的叠加性和纠缠性（传送门：转变思维，打开量子的大门）进行信息的运算和处理，其最显著优势在于“操作的并行性”，即对N个叠加态的量子信息进行一次变换，相当于对N个量子信息同时进行操作。

而什么是量子计算机（Quantum Computer）呢？所谓量子计算机，它是指具有量子计算能力的物理设备。不同于传统计算机，量子计算机用来存储数据的对象是量子比特；不同于传统计算机，量子计算机用使用量子逻辑门进行信息操作，如对单个量子操作的逻辑门：泡利-X门，泡利-Y门，泡利-Z门和Hadamard门等；对两个量子操作的双量子逻辑门：受控非门CNOT，受控互换门SWAP等等。

这些量子的逻辑门的操作可以看做一种矩阵变换，即乘以幺正矩阵（可看做正交矩阵从实数域推广到复数域）的过程。图1以Hadamard门为例，表述了对量子态∣0〉的形象操作过程。

图 1量子门的操作示意图

由图可知，Hadamard门可以将一个量子态变成两个量子态的叠加状态。形象地说，猫生的状态通过Hadamard门转换成生和死的叠加态（概率为状态幅度的平方，概率各为50%）。这种性质十分有用，是实现并行计算基础，可以将N个输入数据转换成一个叠加的量子态，一次量子计算操作，相当于进行了N个数据操作，即实现了N次的并行，后文提到的量子算法正是利用这些量子逻辑门的变换特性。其他量子逻辑门的幺正矩阵有所不同，但操作也类似，这里不做赘述。

此外，量子计算机用使用的量子逻辑门是可逆的；而传统计算机的逻辑门一般是不可逆的。前者操作后产生的能量耗散，而后者进行幺正矩阵变换可实现可逆计算，它几乎不会产生额外的热量，从而解决能耗上的问题。与传统的计算机相同的是，量子计算机的理论模型仍然是图灵机。不同的是，量子计算目前并没有操作系统，代替用量子算法进行控制，这决定了目前的量子计算机并不是通用的计算机，而属于某种量子算法的专用计算机。量子计算机和传统计算机的比较结果如表1所示。

表1 量子计算机VS 传统计算机

量子计算机的工作原理流程如图2所示。它主要的过程如下：

(1) 选择合适的量子算法，将待解决问题编程为适应量子计算的问题。

(2) 将输入的经典数据制备为量子叠加态。

(3) 在量子计算机中，通过量子算法的操作步骤，将输入的量子态进行多次幺正操作 ，最终得到量子末态。

(4) 对量子末态进行特殊的测量，得到经典的输出结果。

图2量子计算机工作原理流程图[1]

迄今为止，科学家用来尝试实现量子计算机的硬件系统有许多种，包括液态核磁共振、离子阱、线性光学、超导、半导体量子点等。其中，超导和半导体量子点由于可集成度高，容错性好等优点，目前被认为是实现量子计算机的两种可能方案。

加拿大量子计算公司D-Wave于2011年5月11日正式发布了全球第一款商用型量子计算机“D-Wave One”。随后，一些信息科技公司和高校纷纷研究和开发量子计算机。IBM在2017年11月份发布的 50位量子比特的量子计算机；Google在2018年3月份宣布研制出72比特量子计算机，提高了量子比特数量，提高计算能力。

需要说明的是，多个比特的量子计算在现实的环境中实现起来十分困难。因为它要求所有的量子比特都持续处于一种“相干态”，而这种特殊状态通常仅能维持几百毫秒，随着量子比特的数量以及与环境相互作用的可能性增加，这个挑战将变得越来越大。因此，实际的量子计算过程中非常容易发生量子比特错误。量子编码的目的正是为了纠错。由于量子的不可克隆原理和存在多种量子态的原因，传统的编码理论不再适用。它成为实现多个量子的计算机亟待解决的一大难点。IBM的50比特和Google的72比特指的是逻辑比特的数量，而一个逻辑比特它会由多个物理的量子比特编码而成。

二、量子算法—量子计算机的灵魂

可以说，没有量子算法就没有高并行的量子计算机。量子算法控制量子计算机的具体计算步骤。在量子算法的研究中，出现了两个里程碑式的算法：Shor算法和Grove算法，它们对传统密码算法产生较大的影响。

1Shor算法—分解大整数，破解RSA

大整数素因子分解难题指的是：将两个大的质因子p1,p2相乘容易，N =p1×p2，但将它们相乘的结果N分解为两个素因子十分困难。经典算法求解该问题时计算复杂度会随着问题的规模指数增长，目前最有效的传统求解方法复杂度为O (exp[n1/3 (log n)2/3])，其中n表示N的位数。众所周知，RSA公钥密码正是基于这样的一个数学难题。

1994年，应用数学家Shor 提出了一个实用的量子算法，通常称为Shor算法。它的出现使得大整数分解问题在量子计算机中在多项式时间内解决成为可能，它计算复杂度仅为 O (n2(log n)(log log n))。显然，相比经典算法，Shor算法相当于进行了指数加速。算法主要思想是将整数质因子分解问题转化为求解量子傅里叶变换的周期，将多个输入制备为量子态叠加，进行并行处理和操作，从而到到了量子加速的目的。

在实际应用中， 2001年，IBM公司的研究小组首次在开发的核磁共振 (Nuclear magnetic resonance，NMR) 量子计算机中使用Shor算法，成功将15分解成3×5，这一成果引起业界广泛的关注和讨论。理论上，一旦更多量子比特的量子计算机研究成功，对于1000位大整数，采用 Shor算法可以在不到1秒内即可进行素因子分解，而采用传统计算机分解需要1025年。由此可见在量子计算机面前，现有的公开密钥 RSA体系不再安全。

2Grover算法—对称密码安全性减半

搜索问题指的是从N个未分类的元素中寻找出某个特定的元素。对于该问题，经典算法逐个地进行搜寻，直到找到满足的元素为止，平均需要N /2，时间复杂度为O (N )。

1996年，计算机科学家Grover在提出一个量子搜索算法，通常称为Grover算法。采用该量子算法进行搜索仅需π/4×√N次次，复杂度为O (√N )。相比传统算法，它进行了二次加速，再次体现了量子计算并行带来的高效优势。举一个直观的例子，若要从有着100万个号码的电话本中找出某个人的号码。经典方法是逐个地进行搜索，平均需要搜索50万次才能找到正确的号码。而采用Grover的量子算法，它会首先将100万个号码制备为量子叠加态。然后在制备的量子叠加态上通过反复执行量子操作的迭代，每一次迭代，它将放大正确的态（寻找的电话号码）的概率，同时减少非正确的态的概率。当进行π/4×√100×104 ≈785次后，正确态的概率接近于1，此时去测量，可以正确态的结果，从而得到查找的电话号码。

暴力穷举对称密码 (如DES/AES等) 的正确密钥，可以看做一个搜索过程。假设AES的密钥长度为128位，破解该密码使用普通的穷举方法需要大约2128次；而使用Grover算法，却只需大约264次。由此看来，对称密码的安全性在Grover算法下，可以看做其密钥长度减半。

三、应对措施—抗量子密码体制

量子计算的快速发展，对当前广泛成熟使用的经典密码算法，特别是非对称密码算法（如RSA和ECC等）产生了极大的威胁和挑战，表2列出对三种不同密码算法的影响，下面进行解释和说明[3]：

(1) 所有基于整数分解和离散对数上的非对称密码体制都是不安全的。如RSA、EEC算法，它们在多项式时间内可以破解。那么当前主流的公钥加密、数字签名算法将不再安全。

(2) 分组密码和序列密码的安全性将降低为原来密钥长度的1/2。为了抵抗这种攻击，对称加密算法通过增加密钥长度（2倍密钥长度）即可。

(3) Hash 算法的安全性降低为原来的2/3。

表2 量子计算对传统密码的影响

为了抵抗量子计算的攻击，人们提出抗量子密码体制，也称为后量子密码体制(Post-Quantum Cryptography)，即在量子计算机出现之后仍然安全的密码体制。它主要包含基于 Hash的密码体制、基于编码的密码体制、基于格的密码体制和基于多变量的密码体制。具体抗量子密码体制类型及典型算法如表3所示。

表3抗量子密码体制及其具体算法

目前，美国和欧洲正在大力对其投入研究，并快速推动其实用化。2015 年8月，美国国家安全局 NSA 宣布将当前美国政府所使用的“密码算法 B 套件”进行安全性升级，用于2015年至抗量子密码算法标准正式发布的空窗期，并最终过渡到抗量子密码算法。2016 年秋到2017年11月，NIST面向全球公开征集抗量子密码算法，计划进行 3~5年的密码分析工作，预计在 2022年到2023年，完成抗量子密码标准算法起草并发布。

四、总结

目前的量子计算机仍然存在诸多问题，如现实中难以达到理想的条件（操作环境无法达到绝对零摄氏度或存在量子噪声），量子态的操作十分脆弱，通常只能维持几百毫秒，错误难以避免。另外，由于量子不可克隆的特性，导致传统的纠错编码不再适用，这限制量子比特数量的快速增加。然而，量子理论和量子计算机快速的发展表明未来实现高性能的、完整的量子计算机成为可能。量子计算时代的到来，势必对传统密码造成了强大的冲击。特别是RSA和ECC为代表公钥密码，这将直接威胁到PKI（公钥基础设施）体系的根基。不仅你的计算机系统不再安全，你的每一封电子邮件也许可以轻易解密，甚至你的电子网银的金钱将很容易被窃取。为了应对这种威胁与冲击，我们需要做到的是未雨绸缪，提前设计和研究出安全性更高可以抵抗量子计算攻击的密码算法——抗量子密码体制。

如果您想对量子信息技术有进一步的了解，欢迎查看原文，阅读我们的报告《漫谈量子信息技术：量子通信与量子计算》。

参考文献：

[1] 郭光灿，张昊，王琴. 量子信息技术发展概况[J]. 南京邮电大学学报(自然科学版), 2017, 37(3):1-14.

[2] 韩永建. 量子计算原理及研究进展[J]. 科技导报, 2017, 35(23): 70-75.

[3] 刘文瑞. 抗量子计算攻击密码体制发展分析[J]. 通信技术，2017, 50(5): 1054-1059.

内容编辑：物联网安全实验室 陈磊 责任编辑：肖晴