可逆哈希函数？

Question

我需要一个可逆的哈希函数（显然，输入的大小会比输出小很多），它能把输入映射到一个看起来随机的输出。简单来说，我想把像“123”这样的数字转换成一个更大的数字，比如“9874362483910978”，但这个转换不能保持比较关系，也就是说，不能总是这样：如果 x1 大于 x2，那么 f(x1) 也一定大于 f(x2)（但也不能总是相反）。

我这样做的目的是想找到一种方法，把小数字转换成看起来更大、更随机的数字。其实这些数字不一定要真随机（实际上，它们需要是确定性的，也就是说相同的输入总是对应相同的输出），但它们看起来必须要“随机”（至少在转换成字符串时是这样，所以简单的位移方法就不行，因为相似的数字会有相似的高位）。

另外，计算和反转的速度快一点当然是个加分项，但不是必须的。

我不知道我表达得是否清楚，或者这样的算法是否存在，但我会很感激任何帮助！

Answer 1

你所问的其实就是加密。块密码的基本工作模式叫做ECB，它会把一个输入块转换成一个大小相同的输出块。你可以把输入和输出的块看作是数字。

举个例子，AES是一种128位的块密码，所以它会把一个128位的输入数字转换成一个128位的输出数字。如果128位对你来说足够用了，你只需要把你的输入数字填充到128位，然后用AES对这个单一的块进行转换，最后把输出格式化成一个128位的数字。

如果128位太大了，你可以使用64位的块密码，比如3DES、IDEA或Blowfish。

不过，ECB模式被认为是比较弱的，这种弱点正是你所提到的要求（也就是映射必须是“确定性的”）。这是个弱点，因为一旦攻击者发现123这个数字映射到了9874362483910978，从此以后每当她看到后面的数字，就知道原来的明文是123。攻击者可以进行频率分析，或者建立一个已知明文和密文对的字典。

Answer 2

还有一个简单的解决方案是使用乘法逆元（可以看看Eri Clippert的博客）：

我们展示了如何从任意两个互质的正整数x和m中计算出第三个正整数y，使得(x * y) % m == 1，因此对于任何正整数z都有(x * z * y) % m == z % m。也就是说，总是存在一个“乘法逆元”，它可以“撤销”与x相乘后在m下的结果。

我们取一个大数字，比如4000000000，以及一个大的互质数字，比如387420489：

def rhash(n):
    return n * 387420489 % 4000000000

>>> rhash(12)
649045868

我们首先用modinv计算乘法逆元，结果是3513180409：

>>> 3513180409 * 387420489 % 4000000000
1

现在，我们可以定义这个逆元：

def un_rhash(h):
    return h * 3513180409 % 4000000000

>>> un_rhash(649045868)  # un_rhash(rhash(12))
12

注意：这个方法计算速度快，适用于最大到4000000000的数字，如果需要处理更大的数字，请选择一个足够大的数字（以及另一个互质的数字）。

---

你可能想用十六进制来处理（以便打包整数）：

def rhash(n):
    return "%08x" % (n * 387420489 % 4000000000)

>>> rhash(12)
'26afa76c'

def un_rhash(h):
    return int(h, 16) * 3513180409 % 4000000000

>>> un_rhash('26afa76c')  # un_rhash(rhash(12))
12

如果你选择一个相对较大的互质数，那么结果看起来会很随机，不会有顺序，并且计算速度也很快。

Answer 3

根据问题，之前提供的答案似乎都不是特别有用。我也遇到了同样的问题，需要一个简单的、可逆的哈希值，但并不是出于安全考虑，所以我决定使用位移的方法。这种方法简单、快速，而且不需要了解布尔数学、加密算法或其他需要认真思考的东西。

最简单的方法可能就是把一半的位向左移动，另一半的位向右移动：

def hash(n):
  return ((0x0000FFFF & n)<<16) + ((0xFFFF0000 & n)>>16)

这种方法是可逆的，也就是说，hash(hash(n)) = n，并且会产生一些非顺序的配对 {n,m}，其中 n < m，且 hash(m) < hash(n)。

如果你想要一个看起来更不顺序的实现，可以考虑将位的顺序进行交错重排，比如从 [msb,z,...,a,lsb] 改为 [msb,lsb,z,a,...] 或 [lsb,msb,a,z,...]，或者任何其他你觉得能让数字序列看起来不那么顺序的重排，甚至可以在上面加一个 XOR 操作来进一步打乱顺序。

（上面的函数适用于32位以内的数字，较大的数字肯定会导致冲突，需要更多的位掩码来避免问题。不过，32位通常对于任何非安全的用户标识符来说是足够的。）

另外，可以看看 Andy Hayden 提供的关于 乘法逆元 的答案。