哈希函数的周期性

Question

考虑简单的哈希函数：

HASH = INPUT % 4

。这个函数是周期性的，因为如果我们用序列号

0, 1, 2, 3, 4, 5, ...

调用它，生成的散列序列将具有四的周期性：

0, 1, 2, 3, 0, 1, 2, 3, 0, ...

。

我的问题是现代加密哈希函数（例如 SHA256）在这个意义上是否具有周期性？换句话说，是否存在一些整数

0 <= n

和

0 < k

使得

HASH(n + b) = HASH(n + b + ak)

对于

b

中的所有整数

[0, k - 1]

和所有正整数

a

？例如，序列

SHA256(0), SHA256(1), SHA256(2), SHA256(3), ...

在某个点之后会是周期性的吗？

Answer 1

绝对不是。如果是这样的话，找到碰撞就很简单了。加密哈希函数的强度由找到 Hash(a) == Hash(b) 的难度来定义。理想情况下，您需要找到 Hash(b) 的所有值才能找到冲突，如果 Hash 有很多位，则这是不可行的。

Answer 2

虽然哈希函数在数学意义上不是周期性的，但可以创建和操纵哈希行为，以预测哈希将遵循什么值，例如截断它。这就是 Floyd 的循环查找 (rho) 算法的用武之地。通过使用相同的散列重复散列一个值，您最终将创建一个周期约为散列大小 n 的平方根的循环。当前哈希值的问题是它们太大，并且这些计算需要太多时间才能找到，它们是不可行的。所以 SHA(1) SHA(2) 等不会是周期性的，但如果你执行 SHA(fn)、SHA(SHA(fn) 等，你确实可以找到提到的周期性。