哈希函数违反了一些原图像属性

Question

假设 H(xy) = H(x) * H(y) 。显然违反了原像属性。我们如何找到 x, y 使得 H(x) = H(y) mod (2^k)

Answer 1

2^k是一个很特殊的模数。你可以证明如下加强版的欧拉定理：

假设x是任意正整数。那么 x^phi(2^k) (mod 2^k) 等于 0 或 1，当且仅当 x 是奇数时才为 1。

证明：

如果x是奇数，则gcd(x,2^k) = 1，因此根据欧拉定理x^phi(2^k) (mod 2^k) = 1。

假设 x 是偶数。如果 x = 0，则结果为真，因此假设 x > 0。写 x = (2^s)*y，其中 y 是奇数，s > 0。请注意

phi(2^k)` = 2^(k-1)

但是，

x^phi(2^k) = (2^s*y)^phi(2^k)
           = (2^s)^phi(2^k) * y^phi(2^k)
           = 2^(s*phi(2^k)) * y^phi(2^k)
           = 2^(s*2^(k-1)) * y^phi(2^k)
           = 0 * y^phi(2^k) = 0 (mod 2^k)

最后一行是因为 s*2^(k-1) >= k 因此 2^(s*2^(k-1)) 是 2^k 的倍数。

请注意，如果 x 是偶数，那么您实际上有 x^k = 0 (mod 2^k)，因此提高 x 的 phi(2^k) 次方对于除了最小的 k.

鉴于这个引理，现在很容易看出存在不同的 x、y 与 H(x) = H(y) = 0 或 H(x) = H(y) = 1。好像是作业，就交给你了。

哈希函数违反了一些原图像属性

Hash functions violating some pre image properties

hash

cryptography

hash-collision