为什么这个unhash函数不能反转这个哈希？

Question

我写了一个用于密码和密钥生成的散列函数,但很快意识到能够反转散列是非常有价值的,所以我写了一个相反的函数,但是,它起作用了.我不明白为什么这个DOESNT工作.

function hash64(n:uint):uint
{
    n = (~n) + (n << 21);
    n = n ^ (n >> 24);
    n = (n + (n << 3)) + (n << 8);
    n = n ^(n >> 14);
    n = (n + (n << 2)) + (n << 4);
    n = n ^ (n >> 28);
    n = n + (n << 31);
    return n;
}

function unhash64(n:uint):uint
{
    n = (~n) - (n >> 21);
    n = n ^ (n << 24);
    n = (n - (n >> 3)) - (n >> 8);
    n = n ^ (n << 14);
    n = (n - (n >> 2)) - (n >> 4);
    n = n ^ (n << 28);
    n = n - (n >> 31);
    return n;
}

馈送1000时的输出:

Hashed from 1000:           1221775646
Unhash output:              1963490760

Answer 1

第一个明显的问题是它没有及时反映出来.这有时工作(如果操作顺序摆在首位没有关系),但一般的反y = f(g(x))是x = g?¹(f?¹(y)).f最后应用,因此必须首先撤消.比较一下:如果你先穿上袜子然后穿上你的鞋子,你应该先脱掉鞋子然后脱掉袜子.

此外,许多反转开始都是错误的.例如,
m = n ^ (n >> 24)is 的倒数和is n = m ^ (m >> 24)的倒数m = (n + (n << 2)) + (n << 4)是n = m * 0x3cf3cf3d(它是模乘法逆).它并不像换档翻转的方向那么简单.

没有经过测试,但这些都是正确顺序的反转:

n = n * 0x80000001;
n = n ^ (n >> 28);
n = n * 0x3cf3cf3d;
n = n ^ (n >> 14) ^ (n >> 28);
n = n * 0x1c03dd39;
n = n ^ (n >> 24);
n = (n + 1) * 0xffdfffff;