哈希生日悖论

Question

因此，我正在研究计算3个随机素数（小于2^8）的2^4集合的哈希值。然后继续选择一组3个合成数（小于2^8），直到有一组{c1, c2, c3}的散列值与之前的一个散列（主要散列值）匹配，该集合将被称为{p1,p2,p3}。

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

任何帮助将不胜感激。

Answer 1

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

未说明的是散列值的范围。

生日攻击是基于这样一个事实，即由于散列值的范围是有限的，所以尝试散列3个数字的所有组合的蛮力方法可能会产生与有效散列值的一些冲突实际尝试所有可能的组合之前。然而，在这种情况下，尝试3个数字的所有组合仅需要16777216个循环，因此可以使用完整的强力方法。

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

使用全部3个数字集检查冲突< 2^8将需要2^24 = 16777216个循环，根据哈希算法不应该花太长的时间。