任何大小合理的 RSA 密钥都将被使用 Shor 算法的大小相当的量子计算机破解。如果您想抵抗量子计算机，无论密钥大小如何，都不要使用 RSA。

唯一幸存的 RSA 变体是Bernstein 的一些幻灯片，其中提到了 2^43 位 RSA 密钥，该密钥由 2^31 个素数组成，每个素数为 4096 位。这显然是荒谬的不切实际。

具体分析表明，与所有已知的量子攻击相比，具有 2^31 个 4096 位素数的 RSA 提供 > 2^100 的安全性。钥匙几乎适合硬盘驱动器。

如果您想要在量子计算机中幸存下来的非对称密码学，您应该寻找其他地方。例如，基于代码或格的密码学被认为对 QC 是安全的，同时具有合理的属性。pqcrypto.org对 QC 的影响以及哪些算法类可用作后量子密码学方案进行了合理的概述。

如果通用量子计算机可以扩大规模以可行地攻击任何适度密钥大小（例如，b=128 位）的 RSA，那么任何密钥长度的 RSA 都是不安全的（或者很快就会不安全，除非有一些主要的理论障碍允许构建这种规模的系统，但阻止构建更大的系统）。要攻击 1024 位 RSA，您需要一台 b=1024 量子位的量子计算机。然后，它应该能够通过使用 Shor 算法分解模数来打破 O(b^3) 中的 RSA。对于 b=4096 位 RSA，它只是适度扩大了量子系统（量子比特数增加了 4 倍），运行时间只差了 64 倍。与使用最佳次指数分解算法的 4096 位密钥为 100 000 000 000（即 10 ¹¹) 比 1024 位密钥强几倍。另请注意，对于密码系统的普通用户，1024 位 RSA 的加密/解密时间大约比 1024/4096 位 RSA 快 64 倍，这意味着 RSA 的经典用户不会获得更大的密钥大小与量子计算攻击者相比具有显着优势。

然而，能够运行 Shor 算法来分解大整数的量子计算机还有很长的路要走。Shor 算法在 2001 年发表的最好的算法将 15 分解为 3x5，而另一个小组花了十多年的时间才将 21 分解为 3x7（当前记录）。DWave 系统的量子退火系统与可以执行 Shor 算法的通用量子计算机相去甚远。他们只能解决一个特定的问题——Dwave 问题，并且没有显示出比优化的经典退火问题更快地解决这个问题。

但是，如果您担心量子计算，则必须从基于整数分解或离散对数（包括 RSA/DSA/El Gamal 甚至使用椭圆曲线）的 PKE 系统迁移出来，这些系统可能会受到 Shor 算法（或稍作修改的版本）的攻击。椭圆曲线）。

存在抗 Shor 算法的 PKE 类型，但它们似乎都没有广泛使用。

最有前途的密码系统之一是McEliece 密码系统，它比 RSA 更快，并且可以随着密钥大小快速增长安全性，但公钥通常约为 0.5 兆字节。

另一种是NTRUEncrypt，它具有合理的密钥大小和性能，但没有像 RSA 那样进行密码分析（并且已获得专利）。

请注意，虽然不能保证新的量子算法会出现并打破这些抗 Shor PKE，但这是意料之中的。你可以证明这些算法是基于 NP-hard 问题，所以如果它们被新的量子算法打破，这将是复杂性理论的重大突破（没有解决 P=NP 或 P!=NP 大，但接近） .

最后，我们应该注意对称加密和非对称加密在量子计算方面的区别。对于对称加密（例如，分组密码），Grover 算法允许在 O(sqrt(N)) 时间内破解复杂度为 O(N) 的对称密钥。这意味着一个 128 位的密钥，它需要 O(2 ¹²⁸ ) 时间来进行经典的暴力破解，而使用合适的量子计算机只需要 O(2 ^{64 ) 时间。}因此，在对称密钥大小和散列大小等上下文中，您应该将经典所需的长度加倍（即从 AES-128 迁移到 AES-256 以确保安全）。

CodesInChaos 提到的幻灯片详细介绍了一种进行多素数 RSA 加密（未广泛使用）的方法，以解决 RSA 与 Shor 算法相关的主要问题：如果 qbit 操作与位操作一样快，那么 Shor 算法可以对于任何给定的密钥大小，因子素数的加密速度与 RSA 一样快。

为了解决这个问题，DJB 解释的方法使用多素数 RSA 来实现更快的加密，同时使用更多的密钥材料。

还有多少？8 TB 为您提供与我们今天所拥有的大致相同级别的安全性。