寻找Hash值相同的字符串

Python的哈希值算法

在32位系统中，Python的哈希值算法可以用下面的程序表示：

def str_hash(s):
    if not s:
        return 0 # empty
    value = ord(s[0]) << 7
    for char in s:
        value = c_mul(1000003, value) ^ ord(char)
    value = value ^ len(s)
    if value == -1:
        value = -2
    return value

其中c_mul()是C语言的32位整数乘法，由于Python的整数乘法不会溢出，因此需要用下面的程序模拟C语言的32位乘法：

def c_mul(a, b):
    return eval(hex((long(a) * b) & 0xFFFFFFFFL)[:-1])

或者使用NumPy中的int32整数进行乘法运算：

import numpy as np
def c_mul(a, b):
    return int(np.int32(a) * np.int32(b))

让我们验证一下str_hash()的结果：

>>> hash("abcd"), str_hash("abcd")
(1540938112, 1540938112)
>>> hash("12345"), str_hash("12345")
(-274697348, -274697348)

可以看到str_hash()的结果和内置的hash()相同。

c_mul()的逆运算

为了计算哈希值相同的字符串，需要从某个指定的哈希值出发，做hash()的逆运算。逆运算中最困难的是c_mul()。即假设“r = c_mul(1000003, n)”，已知r，求n。换句话说就是找到一个n，使其满足下面的等式，其中k为整数：

n(r) * 1000003 = k * 0x100000000 + r

显然我们只需要找到r为1时对应的n(1)，就可以通过r*n(1)计算出n(r)了。

用穷举法可以很快找到n(1)：

>>> k = np.arange(1000003, dtype=np.int64) ❶
>>> k *= 0x100000000
>>> k += 1
>>> k %= 1000003
>>> np.where(k==0) ❷
(array([470729]),)
>>> (470729*0x100000000+1)%1000003
0L
>>> (470729*0x100000000+1)//1000003 ❸
2021759595L
>>>

❶注意需要使用64位整数，防止k*0x100000000运算溢出。❷找到k*0x100000000+1除以1000003的余数为0的k值。再把这个k值代入公式计算出n(1)为2021759595。即r = c_mul(1000003, n)的逆运算为n = c_mul(2021759595, r)。

除了使用穷举法，还可以用下面的程序计算：

def invert_mult(a, b):
    g1, g2 = 0, 1
    while a!=0:
        d, m = b//a, b%a
        g1 = g1 - d*g2
        a, b = m, a
        g1, g2 = g2, g1
    return g1

下面是invert_mult()的用法：

>>> invert_mult(1000003, 0x100000000)
2021759595L

迭代法的工作原理

为了理解这段迭代法的工作原理，我们用SymPy编写一个迭代程序：

from sympy import *
n, k = symbols("n,k", integer=True)
a = symbols("a", integer=True)
g1 = n
g2 = k

a = S(1000003)
b = S(0x100000000)

while a!=0:
    print "%s*(%s) == %s*(%s) + 1" % (a, g1, b, g2)
    d, m = b//a, b%a
    g1 = g1 - d*g2
    b = m
    a, b = b, a
    g1, g2 = g2, g1

程序的输出为：

1000003*(n) == 4294967296*(k) + 1 ❶
954414*(k) == 1000003*(-4294*k + n) + 1 ❷
45589*(-4294*k + n) == 954414*(4295*k - n) + 1
42634*(4295*k - n) == 45589*(-90194*k + 21*n) + 1
2955*(-90194*k + 21*n) == 42634*(94489*k - 22*n) + 1
1264*(94489*k - 22*n) == 2955*(-1413040*k + 329*n) + 1
427*(-1413040*k + 329*n) == 1264*(2920569*k - 680*n) + 1
410*(2920569*k - 680*n) == 427*(-7254178*k + 1689*n) + 1
17*(-7254178*k + 1689*n) == 410*(10174747*k - 2369*n) + 1
2*(10174747*k - 2369*n) == 17*(-251448106*k + 58545*n) + 1
1*(-251448106*k + 58545*n) == 2*(2021759595*k - 470729*n) + 1 ❸

其中❶为原始的公式(4294967296就是0x100000000)，从❶可以推出❷，这是把4294967296分解为：d*1000003+m(其中d=4294，m=954414)的形式，然后整理得到的。接下来的算式都是将较大的乘数用“d*较小乘数+m”的形式表示，直到❸较小的乘数变为1。

对于❸，可以列出下面的两个方程：

a = 2021759595*k - 470729*n
-251448106*k + 58545*n = 2*a+1

解这个方程组得到：

k = 1000003*a + 470729
n = 4294967296*a + 2021759595

但将a=0代入上面的解中即可求出k和n。

搜索

让我们再回顾一下前面介绍的哈希值运算函数：

def str_hash(s):
    if not s:
        return 0 # empty
    value = ord(s[0]) << 7
    for char in s:
        value = c_mul(1000003, value) ^ ord(char) ❶
    value = value ^ len(s) ❷
    if value == -1:
        value = -2
    return value

假设要搜索的字符串由大小写字母和数字(CHARS)构成。我们要找到所有长度为8、哈希值为8的字符串。根据哈希值计算程序可知，❷如果最终得到的value为0，那么字符串的哈希值就为8。

我们从value=0往前逆推，即在❶中等号左侧的value为0，求出CHARS中的每一个字符char对应的value值，使得c_mul(1000003, value) ^ ord(char)为0。然后对于每个value值再重复上述操作。

由于每一个字符都有62种选择，因此这样的搜索很快就会产生组合爆炸。为了尽可能加快运算速度，减小搜索的深度，我们使用一个字典缓存所有长度为4的字符串的哈希值。

import string
import itertools

CHARS = string.ascii_letters + string.digits
PREV_N = 4

hash_dict = {}
for c in itertools.product(*(CHARS,)*PREV_N): ❶
    s = "".join(c)
    hash_dict[hash(s)^PREV_N] = s ❷

❶使用itertools.product()产生有CHARS中所4个字符的组合，❷调用hash()计算字符串的哈希值，注意需要与字符串的长度进行异或，得到每个字符串对应的value的值。这个字典非常大，大约需要占据1G的内存，如果读者的电脑内存不够用，请将PREV_N改为3，不过这样会极大降低搜索的速度。

下面是搜索的程序，我们用NumPy的乘法和异或运算加快计算速度。

results = []
CHARS_ORD = np.array([ord(c) for c in CHARS], np.int32) ❶
magic_num = np.int32(2021759595)                        ❷

def search_h(h, n, s):
    if n == PREV_N:
        if h in hash_dict:                             ❸
            results.append(hash_dict[h] + s)
            if len(results) % 1000 == 0:
                print len(results)
        return
    h2_array = h ^ CHARS_ORD                            ❹
    np.multiply(h2_array, magic_num, out=h2_array)     ❺
    for i, h2 in enumerate(h2_array):
        search_h(h2, n-1, CHARS[i] + s)                 ❻

search_h(np.int32(0), 8, "")
print len(results)
print set(hash(s) for s in results)                     ❼

❶将字符串中的字符转换成32为整数。❷是前面介绍的c_mul()逆运算的乘数。在search_h()中，s是当前已经完成逆运算的字符串，h为这个字符串对应的逆推的value值，n为距离目标长度的差。❸当只剩下PREV_N个字符没有运算时，可以直接从hash_dict中寻找。❹使用NumPy的异或操作符一次运算所有62字符与h的异或结果。❺c_mul()的逆运算。❻最后，对h2_array中的每个值递归调用serach_h()，进行下一次逆推运算。

在我的计算机上，只用了25秒的时间就找到了50972个哈希值为8的字符串，最后通过❼验证这些字符串的哈希值的确是都为8的。下面是results中的头10个字符串：

['GA8Mfaaa', 'e4R5Blaa', 'Y92RLlaa', 'sCvEytaa', 'ydDspvaa',
'ofLCCCaa', 'uemC0Daa', 'CbgFKKaa', 'd0XRbNaa', 'hUzU9Saa']

请读者使用本程序计算出的10000个字符串作为字典的键值，测试字典的存取速度有何变化。