彩虹表作为大素数因子的解决方案

Question

在我已经阅读过关于公钥加密的解释中,据说通过将2个极大的素数相乘来得出一些大数.由于对大质量产品进行分解几乎不可能耗费时间,因此您具有安全性.

这似乎是一个可以通过彩虹表轻易解决的问题.如果您知道所使用的素数的大致大小并且知道其中有2个,您可以快速构建彩虹表.它是一个强大的表,但它可以完成,任务可以跨硬件并行化.

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

免责声明:显然,数以万计的疯狂智能安全意识的人不会错过几十年我在下午想到的事情.我认为我误解了这一点,因为我正在阅读简化的外行解释(例如:如果使用超过2个数字),但我还不知道我的知识差距在哪里.

编辑:我知道"彩虹表"涉及在查找表中使用预先计算的哈希,但上面的声音听起来像彩虹表攻击所以我在这里使用这个术语.

---

编辑2:如答案中所述,没有办法存储所有素数,更不用说它们的所有产品.

• 这个网站说有这么多512位素数:((2 ^ 511)*1)/(512 log(2))= 4.35×10 ¹⁵¹
• 太阳的质量为2×10 ³⁰ kg或2×10 ³³ g
• 这是每克太阳2.17×10 ¹²⁴素数.
• 数量.512位数可以适合千字节:1 kb = 1024字节= 8192位/ 512 = 16
• 这可以适合太字节:16*1024*1024*1024 = 1.72×10 ¹⁰
• Petabyte:16*1024*1024*1024*1024 = 1.72×10 ¹³
  
• Exabyte:16*1024*1024*1024*1024*1024 = 1.72×10 ¹⁶

即使1 exabyte重1克,我们也无法达到2.17×10 ¹²⁴所需的能够将所有这些数字装入带有太阳质量的硬盘中

Answer 1

从我最喜欢的书之一,布鲁斯施奈尔的应用密码学

"如果有人创建了所有素数的数据库,他是否能够使用该数据库来破解公钥算法？是的,但是他不能这样做.如果你可以在一个称重的驱动器上存储1千兆字节的信息克,那么只有512位素数的列表会非常重,以至于它会超过Chandrasekhar限制并崩溃成一个黑洞......所以你无论如何都无法检索数据"

换句话说,它是不可能的或不可行的,或两者兼而有之.

Answer 2

RSA和Diffie-Hellman中使用的素数通常约为2 ⁵¹².相比之下,已知宇宙中只有大约2 ^256个原子.这意味着2 ⁵¹²足够大,可以为宇宙中的每个原子分配2 ^256个唯一数字.

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

顺便说一句,我认为你的意思是"一张大型的素数表" - 彩虹表专门为哈希量身定制,在这里没有任何实际意义.