量子计算从概念走入现实，公钥加密是否岌岌可危

原文链接：点击打开链接

摘要： 量子计算，梦幻概念走进现实，那如果走向商业化呢？ 量子计算的概念起源于20世纪80年代，量子物理学蓬勃发展引发了量子计算的概念。利用量子物理学来重构计算机系统，思考量子算法的理念不仅在当时，在今天听起来也像是某种梦幻。

量子计算，梦幻概念走进现实，那如果走向商业化呢？

量子计算的概念起源于20世纪80年代，量子物理学蓬勃发展引发了量子计算的概念。利用量子物理学来重构计算机系统，思考量子算法的理念不仅在当时，在今天听起来也像是某种梦幻。越来越多的科学研究结果之下，美国 NIST 研究机构自去年起设立的量子阻抗计划也在持续推进中。量子计算从概念走入现实，强大计算能力甚至可以突破互联网时代的安全防护，未来时代的安全是否是岌岌可危的呢？

本文整合分析了量子计算的重要概念，详细讲述其对于公开密钥加密 RSA 的威胁、以及美国 NIST 机构提出的量子阻抗计划如何应对这种远在未来的威胁。

从薛定谔的猫到量子计算

在量子力学理论中，微观粒子有时会显示出波的性质，有时又会显示出粒子的性质，在不同条件下分别表现出波动或粒子的性质，这种称为 波粒二象性 的量子行为是微观粒子的基本属性之一。

经典的双缝干涉实验：我们窥探到量子世界的奥秘

微观粒子一旦遭到 观测，量子状态会由某种状态坍缩成特定的状态，观察者也会得到一个观测值。当然，这种变化特征可以用一个微分方程薛定谔方程来描述。但这种量子的“一观测就坍塌”的特点，还是和宏观世界的常识违背。

而关于这一点，我们平常最常看到的通俗例子就是薛定谔那只“不死不活”的猫，例子中将微观粒子的特征衍生至宏观物体上，以诠释量子力学与正常物理常识的违背。

 

薛定谔的猫：死去活来

普通计算机使用一个比特（bit）中 0 与1的两种状态存储数据，通过高电压和低电压两种状态控制半导体及集成电路记录及运算信息；而量子计算机的存储单位，量子比特（qubit）虽然也可具有两个逻辑态 0 和 1 ，但与经典计算机的不同点则在于它可以实现多个状态的 相干叠加态 。所以，制造出来的量子计算机就可以通过控制原子或小分子的状态，记录和运算信息，存储和运算能力都能超越经典计算机。

举例来说，一个量子比特的状态可以表现成 ，其中（因为是复数，需要取模平方）。也就是说，它的状态并非简单的非黑即白，而是一定概率的 0 态和一定概率的 1 态。

那么如果是 k 个量子比特，即会有 2k 个的叠加态（0 至 2k-1），能描述个复数，远远大于传统计算机中 k 个比特所能描述的  个整数。

所以说，在经典世界中我们不可能叠加 001 态和 100 态，因为这两个状态的电压叠加之后，我们无法区分原来的态，而只能得到一个全新的 101 态。然而，在量子世界之中多种状态的叠加可以区分处理，一个操作可以同时对叠加态中的所有态进行处理，因此如果找到行之有效的对应算法，就像进行并行运算一样，可以显著降低时间成本。

凭借量子计算机的力量，快速傅立叶变换（FFT）的复杂度可以降低到 O(log2(n)) 这么快，由于我们只需要利用 log(n)  个量子比特就可以描述 n 维向量了，所以当因数分解的复杂度迅速降低后，RSA 加密就会失效了。当然，如果需要在现实生活中看到或者运用量子计算的能力，一方面需要量子算法，另一方面则也需要物理层面实现的量子计算机。

量子计算对公钥加密的威胁

我们对于一项技术有一点了解的时候，通常对于这项技术在未来获得商业可行性的时间上知之甚少， “这项技术是什么” 指的是量子计算所蕴含的强大计算能力。 而 “什么时候实现” 目前普遍认为，会是在未来 15 到 30 年的一段时间内。 

去年，来自 Google 和 NASA 的科学家们认为，D-Wave 量子技术可以提供比当前传统技术快1亿倍的计算能力。（尽管 D-wave 不是通用型量子计算机，而只是一台用于 量子退火特定算法 的量子计算机。）但未来的量子计算机的算力依旧能够超越想象，轻松打破当前的公钥密码系统。

那么面对飞速发展的技术，我们不得不思考现在的量子加密问题：如果现行的加密技术可以被破解，我们应该如何 考虑改进 当前的公钥加密？

1994 年 Peter Shor 的因数分解量子算法

1980 年量子计算理论提出后的十年间，在实践上曾遭遇过一段时间的沉寂。直到 1994 年，彼得·肖尔（Peter Shor）才开发了量子算法来确定大素数。Shor算法可以非常高效地进行大数因子分解，而这一点恰恰是目前多数行业所用的公钥 RSA 系统的安全依靠。

正常计算机对数 N 进行因数分解，运算时间随输入长度指数增长，而采用Shor算法则可以在不到一秒的时间内实现 1000 位数字的因数分解，但由于缺乏量子计算机，该算法对密码系统的影响在当时并不被认为是一个急需解决的问题。

然而今天，量子计算的发展让我们更接近这个问题的答案。如果量子计算在未来15年内在商业上逐渐变得可行，那么加密技术就会重新面临这个难题：受到目前世界上最受欢迎的公钥密码系统 RSA 保护的数据将会变得可读，也就是说量子计算机面前，RSA 体系几乎是透明的！如果商业化过程还要更久的时间，如需要近30年的话，那么我们可能还有时间来思考和解决这个问题。

可能失效的密码与可能抵御量子攻击的密码

当然，现在已经陆续有各种 理论假设 提出——如何设计一款无法被量子攻破的安全加密方法？目前提出的方案。已有如基于网格的密码，基于编码的密码，和基于多变量算式的密码等等，学术研究正在迅速跟进，弥补技术发展带来的新突破。

问题的关键在于开发和测试一款全新加密技术所需要的时间究竟会需要多长，其次在于如何将全新的可抵御量子攻击的密码应用到现有的基础设施之上。

这项密码技术上的全新解决方案主要还是为尽快建立量子安全的公钥密码系统。对于对称密钥密码系统来说，它们面临的危险还不是那么紧迫：对称密钥密码系统可以通过使用较大的密钥来解决这个问题，如 AES 和 Triple DES 等对称算法，可以使用哈希函数得到较长的输出。

2016 年 NIST 的量子阻抗计划

而在去年，美国国家标准技术研究所（NIST）宣布了一项新的计划来开发 量子阻抗公钥密码术。

他们回顾了过去大约四十年的加密体系，某些数学问题的“难度”被用作大多数公共密钥加密方案的基本假设。

公开密钥密码体制是现代密码学的基石，而现在量子计算的发展改变了我们传统意义上对于问题的 “难度” 的定义。因此，我们自1980s以来所有运用公钥加密的系统需要改成能够 应对量子攻击 的密码系统。

接着，NIST 继续分析了目前量子计算的 发展状态 ，发现量子计算的出现打破的是过去密码学对于问题 “难度” 的定义，对于常规计算机而言较为困难或棘手的数学问题的复杂度在量子计算机看来不值一提，因此直接导致 1980s 后部署的公钥加密是可被量子攻击的不安全加密手段。

如果大规模量子计算机今后能够普及，那么将能够打破目前正在使用的许多公钥密码系统，并将严重影响互联网及各地数字通信的保密性和完整性。

他们提出应当将这部分密码系统替换成可抵御量子攻击的量子阻抗密码。而鉴于一种密码系统理念从理论走向可行应用，再到最终成为通用标准的这条漫漫长路所需要花费的时间，还需要考虑很多事情的周全。

- 现行的公开密钥密码体制 肯定是要替换 的

- 新的密码系统成为通用标准会花费 很久 的时间

- 同时需要做到 向后保证安全

- 当今 时代 和20世纪80年代 不同（网络、电子支付）

- 需要能够进行安稳而平滑的 过渡

这个量子阻抗计划具体想要实施的步骤还是分为两大块，一块是接受提案，寻找到对于量子计算机而言也足够难的问题，在这些困难问题中识别哪些可以运用在公钥系统中的( lattice based 之类）。但由于每个种类的方案都提出特定的难题（既有理论，也有实用方案），还是需要同步进行很多分析，还会面临许多挑战。

我们可以看到 NIST 还是制定了非常细致的项目计划，收集提案、组织会议、进行议题的推进和学术分享。

NIST 计划在 2016 年秋季开始接受建议书的提交，最终截止期限为 2017 年 11 月 30 日。根据计划，他们预计将会持续 3 – 5 年的项目分析阶段，而在完成分析后的 2 年时间后推出量子阻抗公钥密码的标准草案。 NIST 的计划已经在 2016 年 12 月 15 日开始接受建议提交。目前该计划仍处于公开征求、评估和标准化量子阻抗公钥密码算法的过程中，该过程将持续到今年的 11 月 30 日。完整的细节可以在征集投标书公告中看到。

现阶段的大型量子计算机何时建成的问题还不明确答案，许多科学家也认为通用型量子计算机的建立会是重大的工程挑战。甚至有工程师预测，在未来二十年的时间内，才能建立能够打破目前公钥模式的量子计算机。但从历史上看，仍然需要近二十年的实践才能真正部署更先进的现代公钥密码基础设施。

因此，无论我们是否能够估计量子计算时代到达的确切时间，我们现在都必须开始准备我们的信息安全系统，以抵御量子计算攻击。