php - 哈希生日悖论

Question

因此，我正在编写一段代码，用于计算2^43 个随机素数（小于 2^8）的哈希值。然后继续选择 3 个合数的集合（小于 2^8），直到有一组 的{c1, c2, c3}哈希值与之前的哈希值（质数）匹配，该集合称为{p1,p2,p3}.

据我了解，生日攻击基本上是找到两个提供相同结果的函数。所以我会创建2个函数？一个用于质数，然后另一个用于复合？这样做的最佳方法是什么？我认为 PHP 作为语言。

任何帮助将不胜感激。

Answer 1

我认为前提是寻找一组任意 3 个数字 < 2^8，它们使​​用相同的哈希函数产生与一组 3 个素数相同的哈希值。

未说明哈希值的范围。

生日攻击基于这样一个事实，即由于哈希值的范围是有限的，因此尝试对 3 个 < 2^8 的所有组合进行哈希的蛮力方法很可能在实际尝试所有之前就与有效的哈希值产生一些冲突可能的组合。但是，在这种情况下，尝试 3 个数字 < 2^8 的所有组合只需要 16777216 个循环，因此可以使用完整的蛮力方法。

该程序可以创建所有可能的哈希值的直方图。由于只有 54 个素数 < 2^8，因此为所有有效输入（3 个素数）生成直方图需要 54^3 = 157464 个循环。

使用所有 < 2^8 的 3 个数字的集合检查冲突将需要 2^24 = 16777216 个循环，这不应该花费太长时间，具体取决于散列算法。