至少有一个消息来源说，量子计算机在不久的将来将能够破解RSA。我不是安全专家，也不知道AES和AES之间的区别，但是这是否可能使我们无法破解这些现代加密机制呢？
MIT的新5 -atom量子计算机可能会使当今的加密变得过时
也许你们中的一些对此主题更为了解的人可以参与其中？
#1 楼
量子计算将改变加密游戏，但尚不清楚它将改变多少。目前尚不清楚，因为我们还不确定量子计算机可以解决什么样的问题。如前所述，RSA被量子计算大大削弱了，因为质数分解可以使用Shor算法在多项式时间内完成。但是，并不是所有的加密例程都相对于量子计算而言是弱函数。您可能听说过P（多项式时间），NP（不确定性多项式时间），只要给出正确答案，问题就可以解决。在多项式时间内检查）和NP-Complete（最难的NP问题）。大复合数的素数分解已知是一个NP问题，许多人认为它不是P问题。这意味着常规计算机很可能需要超多项式时间（像GNFS一样，最好是次指数时间）进行分解，而RSA加密取决于此。 NP-complete是一类要求更高的问题。 NP问题的任何实例都可以简化为NP完全问题的实例。 （即使NP问题是另一个NP完全问题，这也是正确的。）这意味着，如果您找到NP完全问题的多项式时间解，则每个NP问题都将具有多项式时间解决方案。如果使用经典计算机这样做，您将证明P = NP。
Quantum计算机具有其自己的复杂度等级。 BQP是一类可以由量子计算机在统计上解决的问题。众所周知，因式分解在BQP中，因为我们有Shor算法。未知的是BQP是否包含NP-complete。目前从理论上讲，它不是这样，这意味着即使使用量子计算机，仍有NP完全问题仍然需要数倍的时间，但数学家仍在努力解决该理论。
整数分解位于有趣的中间地带。我们知道它是BQP的一部分（因为我们找到了Shor算法）。我们也知道这是NP中的一个问题（它是NP，因为可以通过多项式乘以证明，只需将数字相乘即可证明因式分解）。我们还不知道它是P，NP-not-P还是NP-complete。没有人能够以另一种方式证明这一点。它实际上可能是一个P问题，可以用经典计算机在多项式时间内解决，因此对于加密而言非常弱。鉴于我们知道它在BQP中，这可能是一个NP完全问题，这意味着量子计算机可以在多项式时间内解决任何NP问题，这通常会对密码学造成重大打击。
许多即将出现的加密算法除了以质因子分解为根之外，还开始使用其他问题。尤其是，使用量子计算机很难解决基于晶格的一系列问题。如果所有NP问题都是BQP的一部分，这将无济于事，但直到现在我们仍在弄清楚这一细节。
事实证明，AES不受Shor算法的影响。 Grover的算法允许在O（2n / 2）时间而不是传统计算机所需的O（2n）时间中强制使用n位密钥。因此，可以通过功能强大的量子计算机在O（264）时间内强行使用128位AES密钥，该量子计算机可以执行128+量子位的Grover算法，运行2 ^ 64次。
¹以下是我明智和具有挑战性的评论员，我的措辞不准确。从技术上讲，NP问题是否需要指数时间是未知的。 NP的问题类别和P的问题类别可能相同。但是，大多数数学家认为P！= NP的可能性更大，这是因为到目前为止，它看起来还不是很像。如果我们想用博彩术语进行讨论，请看看您可以回答多少问题。如果您证明P和NP截然不同，则可以赢得一百万美元的Clay奖，并且可能因为如此聪明而获得了一份轻松的工作机会。如果您证明它们是相同的，我希望国家安全局愿意付出更多的代价，让您对发现保持沉默，而将论文交给他们的数学家。
如果您对量子计算和加密非常感兴趣，我强烈建议您阅读诸如P和NP之类的不同复杂度类。他们值得你花时间。
评论
“它永远不会结束。” -量子密钥分配如何？
–凯文
16 Mar 6 '16 at 4:38
尽管Shor的算法不影响AES，但Grover的算法肯定会影响。但是，可以通过使用AES-256而不是AES-128减轻这种情况。
– SEJPM
16 Mar 6 '16 at 10:53
上面的tl：dr是：我们认为，量子计算将使AES和其他对称算法的有效密钥长度减半。因此，将您的AES密钥长度加倍，就可以了。 （除非您需要保护数十年的高价值资产，否则AES-256可能就足够了。）另一方面，量子计算完全将RSA和椭圆曲线非对称算法搞砸了。我们认为还有其他算法可以，但是还不确定（尚未）。为将来准备更大的密钥做好准备。
–马丁·邦纳（Martin Bonner）支持莫妮卡（Monica）
16 Mar 7 '16 at 9:36
如果您有解决NP中问题的实用P算法，则其含义要比“密码中断”大得多。您可以写下的任何证明都容易找到。任何证明。大部分逻辑分为重言式（任何我们可以理解的问题）和不可访问的问题（其解决方案太复杂而我们无法理解的问题）。这包括构造性证明，因此涵盖了诸如“是否有一种算法可以解决X？”这样的问题：任何可以正确显示的算法都容易发现。 NSA不够丰富。
– ak牛
16-3-7在21:40
@Yakk Point首先请说明“大多数逻辑”具有相对简短的证明。第二点，谈论单个问题的复杂性毫无意义。 X具有简短证明的事实并不意味着该语言中的每个问题都具有简短证明。您可以说的是，如果语言L的每个成员X都有一个见证人W，可以在时间多项式上验证到W的长度，并且W的长度由X的长度以某个函数f（X）为边界，那么P = NP表示判定L在多项式p为O（f（X）* p（X））中。请注意，例如一阶逻辑没有这样的f。
–塔米尔
16 Mar 8 '16 at 11:06
#2 楼
破解其中任何一种算法都是不可能的。问题不在于是否可以用蛮力破解AES，而是要花多少时间以及是否可行。如果要使用普通计算机用蛮力破解AES， ，则需要您搜索2 ^ 128个键，最少需要2 ^ 128个操作。
另一方面，使用量子计算机和搜索算法（例如Grover算法），您将可以（2 ^ 128）^ 0.5个操作中的键数相同。
评论
据我所知，当您计算算法的复杂度时，您将根据需要执行的操作数和输入的大小来衡量它。不是计算能力。在密码术中通常会说，如果密钥破解需要花费2 ^ 90次以上的操作，那么密钥就是安全的。现在尝试使用上述算法破坏128位AES将需要您从计算中获得的数字。如果您尝试将其转换为2 ^ x格式，则会发现它小于2 ^ 90（可以通过减去2 ^ 90得出的数字来辨别）
– HSN
16-3-6在1:11
（2 ^ 128）^ 0.5 = 2 ^ 64，接近DES的密钥大小（2 ^ 56），因此不安全。现在您需要多少时间？由于存在很多变量，因此很难回答这个问题。您的计算能力，使用的暴力程序，使用的平台，使用的密码破解程序编写语言。在这里，我们没有考虑您将饼干设计为基于软件还是基于硬件。但是，考虑到1999年，具有56位密钥大小的DES在大约22个小时内就被破坏了！
– HSN
16-3-6在1:27
@BuvinJ（2 ^ 128）^ 0.5和2 ^（128 ^ 0.5）是非常不同的数字。
–霍布斯
16 Mar 6 '16 at 7:44
@Jason C当我第一次问时，这很有意义。现在，这种讽刺越来越明显！
– BuvinJ
16-3-7的3:42
@aroth您在AES-128上错了。 2 ^ 128比2 ^ 56需要更多的72次摩尔定律迭代，除非您已经将量子计算机算作现代硬件中的一员。
–克苏鲁
16 Mar 7 '16 at 9:02
#3 楼
这里必须要注意的是，量子计算机可用于实现安全协议，该协议要比仅使用传统计算所能实现的安全协议好得多。因此，真正的问题根源在于，并不是所有人都可以使用更先进的技术（在这种情况下，这是量子计算的假设情况）。评论
很好的真正的量子计算机可以维持量子相干的类型以分解大整数或在有限域（包括椭圆曲线）上做离散对数，除非任何人尚未公开（除非秘密的未发表的量子计算研究取得了长足进步-谈论数十年- -在发表研究之前）。
– jimbob博士
16-3-6在21:02
抱歉，我必须对此投票。 A）除了“量子密钥分发”之外，我不知道有任何提议的量子安全协议-您可以在答案中包含一些链接吗？ B）大型量子计算机估计耗资10亿美元，并且需要专门的核电站，因此真正的真正问题是，并不是每个人都有10亿美元用于加密，并且在后院拥有核电站。
–麦克·恩斯沃思（Mike Ounsworth）
16 Mar 10 '16 at 18:10
@MikeOunsworth即使QKD也与“量子计算机”无关，因为它不需要量子计算，而只需要量子物理学的性质（纠缠等）。甚至不需要一个量子位。
–森林
18年4月8日在22:38
#4 楼
不能。AES被认为是量子后加密技术，不会被量子计算所淘汰（抗QC）。考虑加密强度与计算强度成反比可能会有所帮助。
加密强度通常由密钥长度来衡量。通过加倍密钥长度，可以实现加密强度的指数级增长。例如，AES-256的指数强度要比AES-128的指数强度高。
当前的理解是，与传统计算相比，QC可以表示计算强度的指数级增长。这将使传统的加密强度降低一半。
因此，强加密将需要两倍的密钥长度才能抵消QC计算强度。
这是最坏的情况。如果QC强度只是指数级以下，则密钥长度的较小增加就足以抵消任何优势。
强加密的最小建议密钥长度应从90位增加到180位。 >
结果：在最坏的情况下，AES-256将从可笑的强度降低到可笑的强度，而AES-128将不再被视为强度。
请记住，这个惊人的结果只是通过将室温经典计算（CC）强度与过冷QC强度进行比较可以实现。
过冷CC设备也提高了计算强度。超导QC设备已经以接近零的开尔文（Kelvin）运行，这是通过物理手段提高计算强度的关键极限。 ，而现存的QC最多仅支持受约束的并行性。
评论
这与接受的答案有何不同？您似乎在说同样的话？
– schroeder♦
17年7月23日在21:32
接受的答案并不能确定性地回答问题，而只是引起猜测，没有给出结论。这实际上只是另一个问题，我都回答了。
–多米尼克·塞里萨诺（Dominic Cerisano）
17年7月23日在22:02
您说：当前的理解是，质量控制可以使经典密码的运行速度成指数增长。但这实际上只是外行的理解。在用于分解的最著名算法的情况下，量子算法比经典算法快几倍。但是对于许多其他类别的问题，您只能得到二次加速。那是巨大的区别。突破加密的二次加速意味着我们需要使其变得更强大。众所周知，指数加速将意味着加密技术的终结。
–卡巴斯德
17年7月23日在22:30
我坚持我的主张，即密钥长度加倍会增加加密强度，从而抵消计算强度的任何指数增长。因此，我必须说，您对“加密货币终结”的说法对外行来说似乎只是诡辩。我的答案涵盖了指数级加速的最坏情况，其中涵盖了二次加速。顺便说一句，我想你的意思是说超多项式，也涵盖了。
–多米尼克·塞里萨诺（Dominic Cerisano）
17年7月24日在0:49
如果使用经典计算机对密钥进行暴力破解需要搜索N个可能的密钥O（N）的工作量，那么使用Grover算法，则需要O（sqrt（N））的工作量。这是二次加速。指数加速将类似于从O（N）到O（lg N）或从O（2 ^ x）到O（x）。此外，当您删除带有批注的答案时，这很烦人，而随后几秒钟后重新发布相同的答案。这是您第四次发布相同的答案；您可以编辑答案-首选编辑，因为它会留下编辑和评论的历史记录。
– jimbob博士
17年7月24日在15:06
评论
如果我没有错误地阅读文献，那么量子计算机只能将“块长”（和密钥长度）“有效地”减少到标称值的一半。因此，我最近指出了一种简单的方法，可以将给定的分组密码加倍以抵消对手拥有可用量子计算机的潜在风险。参见s13.zetaboards.com/Crypto/topic/7504586/1/@ Mok-KongShen，你错了。 Shor的算法在多项式中分解因式分解，而不是指数形式的时间。
@ user1717828这就是为什么您使用椭圆曲线而不是素因数分解的原因。但这与AES无关。
@JDługosz椭圆曲线的强度来自离散对数问题，这在Shor的多重时间中也被打破。更不用说ECC的密钥长度短得多，这使得ECC比RSA更容易受到量子计算机的攻击。<br />
@JonasDralle您的评论是完全错误的。 AES不能通过量子计算机破解，它不使用质数（您正在考虑使用RSA）。 QKC（使用OTP）不需要量子计算机，尽管有“数学证明”，但许多实现还是被打破了。它也不能在很多方面代替经典密码。