最强密码也被轻易击穿？量子计算引发加密算法的新革命

近期，来自Google的Craig Gidney和瑞典斯德哥尔摩皇家理工学院的Martin Ekera的最新研究成果表明，量子计算正在以更快的速度赶上当今加密标准。他们用2000万量子比特在短短8小时内就击溃了2048位的RSA加密。

破解2048位RSA有什么值得大惊小怪的

RSA加密是一种被普遍使用于加密和数字签名的非对称加密算法，其最大的特点是基于当前的计算体系将其破解所需的时间成本将会高的吓人。RSA的破解难度与其秘钥位数息息相关，位数越长其破解难度也成指数倍增加。而要想破解2048位的RSA秘钥，即使是使用当前最先进的超级计算机也要80年时间。

破解难点何在

RSA是基于加密是基于乘法过程的，它在加密过程中将质数相乘很容易执行，但反过来对这个很大的数字进行因式分解（解密过程）则异常困难。比如，将两个数字相乘很简单：593 乘以 829 等于 491,597。但是想要算出 491,597 是由哪两个质数相乘得到则非常困难。当数字的越来越大，其解码也越来与困难。经过研究计算机科学家认为冯诺依曼体系结构的经典计算机几乎不可能分解出大于 2048 位的质因子，而 2048 位是 RSA 加密最常用的基础形式，这就保证了RSA加密的安全性。

理论突破

其实1994年，美国数学家Peter Shor提出了量子质因数分解算法，其证明了量子计算机能做出离散对数，而且速度远胜传统计算机，而这正是破解RSA密码的关键所在。因为量子不像半导体只能记录0与1，可以同时表示多种状态。如果把半导体比喻成一个腰鼓，量子电脑就像一个威风锣鼓队，一次运算可以处理多种不同状况。因此，一个40位的量子电脑，就能在很短时间内解开1024位传统计算机花上数十年解决的问题。但受限于当时的量子技术能力，这个算法并不能立刻对破解RSA这类算法做出突出贡献。就像霍华德斯塔克发明的新元素只有到钢铁侠手中才能被合成出来。Shor的算法其实已经证明，只要有一个功能足够强大的量子计算机便终有突破RSA的一天。

量子计算攻坚战

而这样的研究则立马引起了正在使用RSA及其类似加密算法的银行和军方的重视，虽然当时认为造出这样的量子计算机还要几十年，但是RSA这类算法的结局也已经注定。这将对现有加密体系造成颠覆性的影响。自此之后，量子计算机的能力一直在增强。2012年，物理学家们用一台四量子位量子计算机来分解 143。2014 年，他们使用了类似的设备来分解出了 56153。

也许用不了太久，量子计算机很快就能超越最好的经典计算机。然而如同很多小说主角的成长过程一样，很快大型量子计算机就遇到了一个重要发展瓶颈——噪声。目前处理噪声的最佳方法是使用纠错码，但是纠错码需要大量额外量子位。这将大大增加量子计算机解码 2048 位RSA秘钥所需的资源。2015年，研究人员估算，要完成这项工作需要一台有10 亿个量子位的量子计算机才能完成。而当今最先进的量子计算机只有70位，这简直是一个巨大的鸿沟。

银行和军方会很开心，又能“苟住”一段时间了

当今突破，用智不用力

而Gidney 和 Ekera 近期的研究成果则为我们提供了另一条突破的路径。他们的研究使幂模运算变的更有效率，这个算法是将数字提高到某个幂然后除以另一个数，找到余数的过程。而这个过程正是Shor的算法中计算量最大的运算过程。Gidney 和 Ekera 找到了多种方法来对其进行优化，如渐近等效乘法、量子比特编码优化，从而显著地减少了运行算法所需的资源。研究证明了有 2000 万个量子位的量子计算机只需要 8 个小时就可以完成2048位RSA的解码计算。这已经使得分解2048位RSA所需的量子位下降了近两个数量级。”

任重而道远

对于现在人类的技术能力而言，2000万量子位的计算机虽然仍是个遥不可及的目标，但作者表示：“目前仍有很多方法可以继续优化当前的算法，研究还在继续。”也许要不了多久，此算法所需的量子资源将和快速发展的量子计算机在某一个“中间值”会师。到那时人类现有的各种加密手段将渐渐全部失效，我们将不得不发展全新的属于量子时代的全系加密技术。而令人兴奋的是，对我们绝大多数人来讲，我们有生之年也许就能看到像《变形金刚》中那种高信息密度的计算和存储方式。

文中图片来源于网络。