为什么在后量子世界中ECC比RSA更易受攻击？

Question

请原谅，如果这应该是在密码子，但有时答案有非常数学，我宁愿有一个答案是轻一点的数学。

我当时正在观看RSA 2013年的密码专家小组，在“关于33分钟”上，他们提到，在后量子世界中，ECC比RSA更易受攻击。有人能解释为什么在后量子世界中ECC更容易受到RSA的攻击吗？

Answer 1

当前构建量子计算机的挑战是聚集足够多的“量子比特”，在量子级别上纠缠足够长的时间。要打破1024位RSA模数，你需要一台量子计算机，它是(2048)量子位数的两倍.要打破具有“相似强度”的160位椭圆曲线(对于经典计算机而言)，你需要六倍于此(或960量子位)。这并不是说椭圆曲线在本质上是弱的，相反，对于相同的“大小”，它们似乎仍然比RSA强一些。相反，当考虑经典计算机与量子计算机时，给定大小的强度比并不相同。

Answer 2

对于使用量子计算机的攻击者来说，限制因素是他们可以保持足够长的纠缠时间来执行计算的量子位数。破解RSA密钥所需的量子位为2·估计值，而ECC约为6·位，但RSA密钥通常要长得多，因此它们最终占用更多的量子位；低端约为3倍(2048 vs 224)，高端约为10倍(4096 vs 384)，请注意。

下面是一个非常简化的表，比较破解公用密钥长度所需的粗略量子位数：

|           RSA       |           ECC       |
| Key Length | qubits | Key Length | qubits |
|------------|--------|------------|--------|
| 1024       | 2048   | 163        | 1000   |
| 2048       | 4096   | 224        | 1300   |
| 3072       | 6144   | 256        | 1500   |
| 4096       | 8192   | 383        | 2300   |
| 15360      | 30720  | 512        | 3000   |

在过去的20年里，我们还没有想出如何用几个量子位数来构建一台成熟的量子计算机。因此，为了比较一台量子计算机破解RSA密钥和“等效”ECC密钥所需的时间，我们基本上必须假设制造商会以一种可以放大的方式计算出退相干。然后，这就变成了一个问题，即这种缩放发生的速度有多快。

假设线性增长率( 2048个RSA对224 ECC结束时低，4096 RS对384 ECC在高端) RSA以500量子位/年获得5-10年加成，以1K量子位/年计算3~5年，2K量子位/年~1.5~3年。

如果我们假设增长率为指数，那么一旦我们能够破解224位ECC密钥(最弱的公共ECC密钥)，我们就会有一代人的时间来破解4096位RSA密钥(最强的公共RSA密钥)。以摩尔定律(~2年)的速度，RSA得到了~2年的奖金。虽然DWAVE的绝热量子计算机对这些类型的问题没有用，但它们是大约每四年增加一倍的量子位数。

因此，两者之间的差距实际上是相对较小的:2-5年以上的时间到制造业的突破。

注4096位RSA和383 ECC在对称密钥强度方面不能直接比较。4096位RSA密钥大致等效于142位对称密钥，而383位ECC密钥等效于192对称密钥。我将它们直接放在上面，因为它们是最大的、共同支持的密钥大小。