葱一根 - one sat on Nostr: 为什么对称密码和哈希是抗量子的 ...
为什么对称密码和哈希是抗量子的
在我们继续之前，我想特别讨论一下为什么对称密码和哈希是抗量子的。现代数字密码学处理的保护位的大小，这使得经典的暴力破解攻击不平凡的完成。没有足够的计算能力来破解现代密码算法生成和使用的密钥。这是真的，即使我们得到了一个令人难以置信的加速比从量子计算机（即使使用格罗弗的算法），即使与量子力学的令人难以置信的属性。
例如，量子计算机可以利用叠加原理一次性生成所有可能的答案，但这并不意味着量子计算机可以直接挑出正确的答案，然后交给经典世界。对于一个特定的答案，量子计算机可以生成数万亿个答案，必须有一种方法从这些答案中挑选出正确的答案。这就是量子算法的荣耀。这些算法使用量子特性，本质上是“捷径”--蛮力的数学，使我们能够用较少的猜测找到正确的答案，或者从数万亿的答案中找到正确的答案。
肖尔的算法帮助量子计算机分解大型素数方程，因为它包含数学逻辑，可以比使用简单的暴力方法更快地找到解决方案，并从许多猜测中找到正确答案。量子计算机能够破解大多数传统公钥密码的部分原因是，公钥密码所依赖的数学有一个量子计算机和算法可以利用的“弱点”。肖尔的高明之处在于，他能够创造出一种更快的数学解决方案，而这种情况只有在量子计算机的帮助下才有可能发生。
但并不是所有的问题都具有对量子解过于敏感的特性。传统的对称密码和散列都是如此。Grover的算法使用平方根时间缩减，将对称密码的保护减少一半。这在保护方面是一个显著的减少，但不是致命的（如果时间减少是多项式、二次或阶乘）。任何攻击这些类型密码学的量子计算机都可能比经典计算机快得多，但密钥位的数量仍然是如此之大，以至于“快得多”不会显著削弱这些密码或散列的保护能力。
一般来说，人们认为，只要将传统对称密钥和散列的密钥大小增加一倍，就可以在可预见的将来保持量子安全，除非发现一些新的、不可预见的、相关的量子破缺。所以简单地从AES-128和SHA-256AES-256和SHA-512被认为是解决这些问题的长期解决方案，您现在就应该这样做。关于这个主题的更多阅读，请考虑以下优秀的论文：https://arxiv.org/pdf/1804.00200.pdf.
附注：并不是所有的密码学家都认为所有针对散列的攻击都是使用量子计算机来改进的。一些最聪明的密码学家认为，量子计算机在某些形式的散列攻击（即碰撞发现）方面实际上比经典计算机更差。见https://cr.yp.to/hash/collisioncost-20090517.pdf一个很好的例子。
附注：不是所有的哈希都是量子安全的。使用Grover的算法，一些较弱的散列可以更快地被打破。但SHA-2、SHA-3和其他现代散列算法在使用适当的密钥或散列大小时，被认为是强大和安全的，可以抵御已知的未来量子攻击。
仍然是理论
重要的是要记住，在量子霸权实现之前（许多供应商说最快将在2019年实现），所有担心的密码破解大多是理论上的。肖尔的算法已经在量子计算机上得到了验证。和预测的一样。但到目前为止，在量子计算机上使用 Shor 算法的最大因子素数方程是 7 × 3 = 21 ，这可以很容易地由一个孩子解决。你的智能手机比大多数量子计算机有更多的原始计算能力。
注意：最大素数因子的肖尔算法是超小的，但有远远大于素数方程因子的量子计算机不使用肖尔的算法。见https://crypto.stackexchange.com/questions/59795/largest-integer-factored-by-shors-algorithm.虽然一旦创造出足够稳定的量子位元，让肖尔算法可以攻击更大的素数，其他的纪录应该很快就会下降。作为一个额外的说明，请记住，肖尔算法只是一个地板（或天花板，取决于你如何看待它）所需的量子位。它创建于1994年，世界上已经有很多其他的算法，声称肖尔算法已经过时。
但量子力学和量子计算的整体一直是一个理论开始，然后进入现实世界的循环。量子力学在20世纪30年代被爱因斯坦毫无疑问地证明之前，已经理论化了几十年。量子计算机的第一个模型在1985年由大卫·多伊奇（David Deutsch）理论化，随后在1998年出现第一个工作的量子计算机。肖尔的算法在1994年理论化，然后在2001年由IBM在量子计算机上证明。量子计算机正一比特一比特地增长。量子比特的稳定性和纠错能力日益增强。现在，我们有几家拥有各种量子计算机的供应商，他们对量子优势即将到来充满信心。一旦达到量子霸权，打破传统密码学也不会落后太多。第四章，“量子密码何时破解？”将涵盖什么时候量子计算机将打破最传统的密码。
总结
本章涵盖了量子计算如何能够打破传统公钥加密的大多数形式。首先讨论了密码学的基础知识，特别关注当今大多数公钥加密方案是如何提供保护的。然后，我们探讨了量子计算机如何打破这种保护，以及哪种类型的密码学极易受到量子破解的影响。第四章将要讨论量子计算机的理论攻击何时可能成为现实。
在我们继续之前，我想特别讨论一下为什么对称密码和哈希是抗量子的。现代数字密码学处理的保护位的大小，这使得经典的暴力破解攻击不平凡的完成。没有足够的计算能力来破解现代密码算法生成和使用的密钥。这是真的，即使我们得到了一个令人难以置信的加速比从量子计算机（即使使用格罗弗的算法），即使与量子力学的令人难以置信的属性。
例如，量子计算机可以利用叠加原理一次性生成所有可能的答案，但这并不意味着量子计算机可以直接挑出正确的答案，然后交给经典世界。对于一个特定的答案，量子计算机可以生成数万亿个答案，必须有一种方法从这些答案中挑选出正确的答案。这就是量子算法的荣耀。这些算法使用量子特性，本质上是“捷径”--蛮力的数学，使我们能够用较少的猜测找到正确的答案，或者从数万亿的答案中找到正确的答案。
肖尔的算法帮助量子计算机分解大型素数方程，因为它包含数学逻辑，可以比使用简单的暴力方法更快地找到解决方案，并从许多猜测中找到正确答案。量子计算机能够破解大多数传统公钥密码的部分原因是，公钥密码所依赖的数学有一个量子计算机和算法可以利用的“弱点”。肖尔的高明之处在于，他能够创造出一种更快的数学解决方案，而这种情况只有在量子计算机的帮助下才有可能发生。
但并不是所有的问题都具有对量子解过于敏感的特性。传统的对称密码和散列都是如此。Grover的算法使用平方根时间缩减，将对称密码的保护减少一半。这在保护方面是一个显著的减少，但不是致命的（如果时间减少是多项式、二次或阶乘）。任何攻击这些类型密码学的量子计算机都可能比经典计算机快得多，但密钥位的数量仍然是如此之大，以至于“快得多”不会显著削弱这些密码或散列的保护能力。
一般来说，人们认为，只要将传统对称密钥和散列的密钥大小增加一倍，就可以在可预见的将来保持量子安全，除非发现一些新的、不可预见的、相关的量子破缺。所以简单地从AES-128和SHA-256AES-256和SHA-512被认为是解决这些问题的长期解决方案，您现在就应该这样做。关于这个主题的更多阅读，请考虑以下优秀的论文：https://arxiv.org/pdf/1804.00200.pdf.
附注：并不是所有的密码学家都认为所有针对散列的攻击都是使用量子计算机来改进的。一些最聪明的密码学家认为，量子计算机在某些形式的散列攻击（即碰撞发现）方面实际上比经典计算机更差。见https://cr.yp.to/hash/collisioncost-20090517.pdf一个很好的例子。
附注：不是所有的哈希都是量子安全的。使用Grover的算法，一些较弱的散列可以更快地被打破。但SHA-2、SHA-3和其他现代散列算法在使用适当的密钥或散列大小时，被认为是强大和安全的，可以抵御已知的未来量子攻击。
仍然是理论
重要的是要记住，在量子霸权实现之前（许多供应商说最快将在2019年实现），所有担心的密码破解大多是理论上的。肖尔的算法已经在量子计算机上得到了验证。和预测的一样。但到目前为止，在量子计算机上使用 Shor 算法的最大因子素数方程是 7 × 3 = 21 ，这可以很容易地由一个孩子解决。你的智能手机比大多数量子计算机有更多的原始计算能力。
注意：最大素数因子的肖尔算法是超小的，但有远远大于素数方程因子的量子计算机不使用肖尔的算法。见https://crypto.stackexchange.com/questions/59795/largest-integer-factored-by-shors-algorithm.虽然一旦创造出足够稳定的量子位元，让肖尔算法可以攻击更大的素数，其他的纪录应该很快就会下降。作为一个额外的说明，请记住，肖尔算法只是一个地板（或天花板，取决于你如何看待它）所需的量子位。它创建于1994年，世界上已经有很多其他的算法，声称肖尔算法已经过时。
但量子力学和量子计算的整体一直是一个理论开始，然后进入现实世界的循环。量子力学在20世纪30年代被爱因斯坦毫无疑问地证明之前，已经理论化了几十年。量子计算机的第一个模型在1985年由大卫·多伊奇（David Deutsch）理论化，随后在1998年出现第一个工作的量子计算机。肖尔的算法在1994年理论化，然后在2001年由IBM在量子计算机上证明。量子计算机正一比特一比特地增长。量子比特的稳定性和纠错能力日益增强。现在，我们有几家拥有各种量子计算机的供应商，他们对量子优势即将到来充满信心。一旦达到量子霸权，打破传统密码学也不会落后太多。第四章，“量子密码何时破解？”将涵盖什么时候量子计算机将打破最传统的密码。
总结
本章涵盖了量子计算如何能够打破传统公钥加密的大多数形式。首先讨论了密码学的基础知识，特别关注当今大多数公钥加密方案是如何提供保护的。然后，我们探讨了量子计算机如何打破这种保护，以及哪种类型的密码学极易受到量子破解的影响。第四章将要讨论量子计算机的理论攻击何时可能成为现实。