未来的量子计算机将在8小时内破解2048位RSA加密
黑谷量子2020-05-15 16:26
来源：黑谷量子 资料来源：（Matthew Griffin）
作者：776
我们所有重要的通信和数据都经过加密，强大的量子计算机将能够破解几乎所有信息。
毫无疑问，许多人担心量子计算机将能够破解全球最流行的加密技术中的70％以上，使它们变得无用和过时，并将他们保护的敏感数据暴露给任何想要读取的人。
但是，主要的加密技术是使用所谓的“活板门”数学函数对数据进行加密的技术，这些函数可以在一个方向上轻松地工作，而在另一个方向上却不行。这使加密数据变得容易，但是在没有特殊帮助的情况下很难解码。
这些加密系统从未被吹捧为不可破坏的，但是它们的安全性是基于大量的时间，在某些情况下，数十亿个“ B”年，经典的计算机才能完成工作并破坏它们。
简而言之，现代加密方法经过专门设计，因此解码它们将花费很长时间，而它们实际上是坚不可摧的。但是量子计算机彻底改变了这种想法。
这些机器的功能是传统计算机的数亿倍，因此，它们可以轻松破解这些代码。对于今天依赖加密的人提出了一个关键问题–量子计算机何时会强大到足以破解这些代码？因为在该日期之后，受此加密形式保护的任何数据都将变得不安全。
今天，由于在Google的圣巴巴拉分校的Craig Gidney和在瑞典的KTH皇家技术学院的 MartinEker的帮助下，这种思想需要再次进行根本性的修改
这些家伙为量子计算机找到了一种更有效的方式来执行密码破解计算，从而将所需的资源减少了几个数量级。
因此，这些机器比任何人所怀疑的都更加接近现实，对于那些依靠加密来保护信息的人来说，这可能是一个主要问题。
因此，结果对于政府，军事和安全组织，银行以及需要保护数据25年或更长时间的任何其他人来说，都是令人不舒服的结果，这也就不足为奇了。
首先介绍一些背景。早在1994年，美国数学家彼得·索尔（Peter Shor）发现了一种量子算法，其性能优于经典算法。Shor的算法会考虑大量因素，是破解基于陷门的代码的过程中的关键要素。
活板门功能基于乘法过程，该过程易于在一个方向上执行，但在反向操作上则困难得多。例如，将两个数字相乘是微不足道的：593乘以829是491,597。但是很难从数字491,597开始并确定必须将两个质数相乘才能产生它。
随着数字的增加，它变得越来越困难。确实，计算机科学家认为，经典计算机几乎不可能分解长度超过2048位的数字，而这是最常用的RSA加密形式的基础。
索尔（Shor）表明，功能强大的量子计算机可以轻松实现这一目标，结果在安全行业引起了冲击波。
从那时起，量子计算机的功能不断增强。2012年，物理学家使用四量子位量子计算机分解了143因子。然后在2014年，他们使用了类似的设备分解了56,153因子。
不难想象，以这种速度发展，量子计算机应该很快就能胜过最好的经典计算机。
不是这样 事实证明，量子分解在实践中比原本可以预期的要难得多。原因是对于大型量子计算机，噪声已成为一个重大问题。目前解决噪声的最佳方法是使用纠错码，而纠错码本身需要大量额外的量子位。
考虑到这一点，将大大增加分解2048位数字所需的资源。2015年，研究人员估计，量子计算机需要十亿个量子位才能可靠地完成这项工作。这大大超过了当今最先进的量子计算机的70量子位。
在此基础上，安全专家可能已经能够证明量子计算机将2048位RSA加密的消息破坏几十年的想法是正确的。
现在，吉德尼（Gidney）和埃克洛（Eker）展示了量子计算机如何仅用2000万量子位就能进行计算，他们还表明，这样的设备只需花费惊人的八小时即可完成完整的计算并将其破解。
他们说：“ [结果]，最坏情况的估计是需要多少个量子位来分解2048位RSA整数，这下降了将近两个数量级。”
他们的方法侧重于执行称为模幂的数学过程的更有效方法。这是在将数字提高到一定幂后再除以另一个数字的过程，以找到余数。
此过程是Shor算法中计算上最昂贵的操作。但是Gidney和Eker已经找到了各种优化方法，大大减少了运行算法所需的资源。
这项有趣的工作应该对任何存储未来信息的人产生重要影响。如今，一台2000万量子比特的量子计算机无疑是一个遥不可及的梦想，
但是实际上，随着量子计算机遵循类似于摩尔定律（称为罗斯定律）的发展模式，这并不是人们所希望的那样遥远。
此外，这些专家应该问自己的真正问题是，在他们希望保护信息的25年之内是否可以使用这种设备。如果他们认为是这样，那么他们需要一种新的加密形式，例如NIST已经提出的加密形式，现在他们需要它。
值得庆幸的是，尽管有这样的消息，但是对于像你我这样的普通人来说，风险却很小。大多数人使用2048位加密或类似的方法来执行诸如通过Internet发送信用卡详细信息之类的任务，因此，如果今天记录这些交易并在25年内中断，则几乎不会丢失。
但是对于政府来说，还有很多事情要解决，而且已经有未经证实的报道称
有人正在存储大量加密数据，因为他们知道尽快而不是稍后就能破坏数据。
他们今天发送的消息-例如在使馆或军方之间-可能在20年后仍然很重要，因此值得保密。而且，如果这些消息仍通过2048位RSA加密或类似方法发送，则这些组织应该开始迅速地感到担忧。
参考： arxiv.org/abs/1905.09749 ：如何在8小时内使用2000万个噪声Qubit分解2048位RSA整数
黑谷量子
声 明：
1、本文内容出于提供更多信息以实现学习、交流、科研之目的，不用于商业用途。
2、本文部分内容为黑谷量子原创，转载请联系授权，无授权不得转载。
3、本文部分内容来自于其它媒体的报道，均已注明出处，但并不代表对其观点赞同或对其真实性负责。如涉及来源或版权问题，请权利人持有效权属证明与我们联系，我们将及时更正、删除。
举报/反馈
0
0
收藏
分享
