256位加密什么时候可以被暴力破解?

信息安全 加密 蛮力 量子计算
2021-08-15 22:34:31

假设量子计算继续改进并继续像这样执行:

... 量子计算机在几分钟内完成 25 亿年的任务

是否有理由期望 256 位加密在未来的某个时候可能会被暴力破解?如果是这样,什么时候可以估计(最好来自大型科​​技公司、安全公司、学术界或政府组织)?可能开始发生?

笔记

  • 显然,估计将是极其困难的,并且可能在很大程度上取决于一些关键假设(即使那样它也可能预测的更早或晚发生),但尽管这样的预测很困难,但一些经验法则(例如摩尔定律) ) 鉴于此类预测的难度,其表现相当不错。

  • 由于美国政府认为 256 位加密足够安全,在足够长的时间内(被美国以外的任何人)破坏以保护美国的安全利益(最后一段),我们可以假设它还有很长的路要走。

背景:

2个回答

很可能永远不会

在目前已知的量子算法中,Grover 算法是最直接影响对称密码的算法。本质上,对于经典计算机可以在时间 N 内暴力破解的密码,量子计算机可以在 N 的时间平方根内暴力破解它。这意味着 256 位密码(最多需要 O(2 256 ) 复杂性来暴力破解经典计算机)可以在量子计算机上以 O(2 128 ) 的速度进行暴力破解。

即使是 128 位密钥的暴力破解也受到物理定律的限制。正如这个出色的答案所解释的那样,暴力破解 128 位密钥所需的能量非常大(连续 10 年世界上的所有资源,仅用于破解一个密钥)。因此,在没有任何其他重大突破的情况下,暴力破解 256 位密钥是毫无疑问的。事实上,格罗弗的算法已被证明是最优的,因此任何进一步的突破都极不可能。

您没有解释 256 位加密的名称,它可以是 AES、ChaCha20、RSA 加密、DLog 或...

肖尔算法

如果我们假设您的意思是 RSA 的 256 位密钥安全性近似为 15560 位模数,那么Peter Shor 的算法将破坏 RSA 加密,在keylength.com上可以找到一个表密钥,其中有多种方法。

Shor 的算法也会破坏 ECC 中的DLog,因此 ECDHE 和 Ed25519 等 ECC 签名将消失。

下表来自;

在此处输入图像描述

Grover 算法

Grover对非结构化数据的算法搜索是渐近最优的,并且具有复杂度 Ω(√n)。使用 AES-256 将使√n. 这里有一个有趣的问题,而且大多没有被讨论过;设置和设置的运行成本。甚至 AES-128 的中断对于 Grovers 的方法也并不实用。

Grover 对 AES-128 的攻击是 2 64次,但是这需要大约 2 64次连续的 AES 评估。这可能无法在合理的时间内实现。用类似的论点,我们可以说 AES-192 和 AES-256 肯定是无法实现的。

下表来自;

在此处输入图像描述

可以运行k 并行 Grover 算法,该算法只会加速√k加速k或二次加速,这是与DES 所做的经典并行搜索的另一个区别

因此,我们可以说 Grover 的攻击即使对 AES-128 也不是实际的攻击。攻击时间仍然是二次的,并且所需的门不实用,对于 AES-128 ,它可以在2 86左右

因此,我们可以说 Grover 的算法评估了经典密码方案针对量子攻击的安全参数。有更多的密码方案可以抵抗量子攻击,NIST 已经有了目前处于第三阶段的后量子密码学项目

对于 AES-128,还有更实际的攻击,例如多目标攻击和包含缓存攻击的侧信道攻击。

如果你想安全使用 AES-256!