37

在我读过的关于公钥密码学的解释中，据说通过将两个非常大的素数相乘可以得出一些大数。由于分解大素数的乘积几乎不可能非常耗时，因此您有安全性。

这似乎是一个可以用彩虹表轻松解决的问题。如果您知道所用素数的大致大小并且知道其中有 2 个，您可以快速构建一个彩虹表。这将是一个非常大的表，但它可以完成并且任务可以跨硬件并行化。

为什么彩虹表不是基于乘以大素数来击败公钥加密的有效方法？

免责声明：显然，数以万计的疯狂智能安全意识的人并不是碰巧错过了几十年我在一个下午想到的东西。我认为我误解了这一点，因为我正在阅读简化的外行解释（例如：如果使用超过 2 个数字），但我还不够了解，不知道我的知识差距在哪里。

编辑：我知道“彩虹表”与在查找表中使用预先计算的哈希值有关，但上面听起来像是彩虹表攻击，所以我在这里使用这个术语。

编辑2：如答案中所述，没有办法只存储所有素数，更不用说它们的所有产品了。

  • 这个网站说大约有这么多 512 位素数： ((2^511) * 1) / (512 log(2)) = 4.35 × 10 151
  • 太阳的质量是 2 × 10 30 kg 或 2 × 10 33 g
  • 每克太阳有2.17 × 10 124 个素数。
  • 数量。可以容纳 1 KB 的 512 位数字：1 kb = 1024 字节 = 8192 位 / 512 = 16
  • 可以容纳 1 TB：16*1024*1024*1024 = 1.72 × 10 10
  • 拍字节：16*1024*1024*1024*1024 = 1.72 × 10 13
  • 艾字节：16*1024*1024*1024*1024*1024 = 1.72 × 10 16

即使 1 艾字节重 1 克，我们也远未达到能够将所有这些数字放入具有太阳质量的硬盘驱动器所需的 2.17 × 10 124

4

3 回答 3

33

来自我最喜欢的一本书，布鲁斯·施奈尔的《应用密码学》

“如果有人创建了一个所有素数的数据库，他就不能使用该数据库来破解公钥算法吗？是的，但他做不到。如果你可以在一个重量为 1 的驱动器上存储 1 GB 的信息克，那么仅包含 512 位素数的列表就会变得如此重，以至于它会超过钱德拉塞卡极限并坍缩成一个黑洞……所以无论如何你都无法检索数据”

换句话说，这是不可能的或不可行的，或两者兼而有之。

于 2010-07-16T18:32:34.360 回答
10

RSA 和 Diffie-Hellman 中使用的素数通常约为 2 512。相比之下，已知宇宙中只有大约2256个原子。这意味着 2 512足够大，可以为宇宙中的每个原子分配 2 256个唯一编号。

根本没有办法存储/计算那么多数据。

顺便说一句，我假设您的意思是“一个大的素数表”——彩虹表是专门为散列量身定做的，在这里没有真正的意义。

于 2010-07-16T18:14:46.037 回答
2

我认为主要问题是为某些算法预先生成的彩虹表使用了一个相当“小”的范围（通常在 128 位范围内）。这通常不会覆盖整个范围，但会加速蛮力过程。它们通常会消耗一些 TB 的空间。

在素数分解中，素数要大得多（对于安全的 RSA，建议使用 2048 位）。所以彩虹表不会“非常大”，但不可能存储在任何地方（使用数百万 TB 的空间）。

此外，彩虹表使用散列链也进一步加快了不能用于​​素数的过程（维基百科有一个很好的解释）。

于 2010-07-16T18:14:04.667 回答