RSA / EC对抗QC攻击的优势

Question

我们知道，RSA和ECC算法都很容易受到攻击，使用未来的量子计算(QC)。然而，选择一种算法比另一种算法有什么好处吗？

例如: RSA的密钥大小是否可能比ECC使用的短密钥大小更大，可能在所需的qbit或qbit配置量方面有优势？这种优势在实践中是否重要？

Answer 1

在这个问题上，这绝不是一个全面的答案，但也许这是一个好的开始。

(特定) ECC的

Shor算法Proos和Zalka的纸比较了Shor算法对某些椭圆曲线群的整数分解和离散对数的实现(特别是那些在素数有限域上的)。 如果n是组的位长(来自6.3节)： RSA | ECC -----+--------+----------+-----+--------+--------- n | qubits | time | n | qubits | time -----+--------+----------+-----+--------+--------- 1024 | 2048 | 4.3*10^9 | 163 | 1000 | 1.6*10^9 2048 | 4098 | 34*10^9 | 224 | 1300 | 4*10^9 3072 | 6144 | 120*10^9 | 256 | 1500 | 6*10^9 RSA需要大约2n量子位，而ECC大约需要6n (对于较小的n)。同样，RSA需要~4n^3门，而ECC只需要~360n^3。 ECC在传统上比RSA困难，允许更小的密钥大小和更高效的计算。从数量上说，ECC仍然比RSA困难，但不那么困难，这就导致了椭圆曲线离散对数在整数因式分解上的“量子优势”。 比较RSA-3072和ECC-256，他们发现量子计算机需要大约4\times大小，并且与ECC相比，破解RSA需要花费大约20\times的时间。 请记住，这项工作是从2008年开始的，并且只与素数域上的曲线相关。

在实践中

显然，根据fgrieu给出的链接，量子位数中的4倍并不是“更具有量子抵抗力”。量子计算很可能更有效地打破了GF上的ECC (2^m)。

由于这两个问题的相似之处，我无法想象量子位配置会在一个方向或另一个方向产生很大影响。

然而，这都是我的猜测。

384位密钥和3072位密钥的量子密码分析之间的差距不太可能足以作为密码策略的基础。

无论如何，我对上述引文的解释是，两者之间并无实际差别。在那个时候，两者都应该被认为是完全崩溃的。