从输出中查找哈希加密输入

Question

我有一个函数hash()，它将给定的字符串加密为整数

letters = 'weiojpknasdjhsuert'

def hash(string_input):
  h = 3

  for i in range(0, len(string_input)):
    h = h * 43 + letters.index(string_input[i])

  return h

所以如果我做print(hash('post'))，我的输出是：11231443

如果输入只能是来自letters的字符串，我如何找到我的输入需要是什么才能获得像1509979332193868这样的输出？循环体中有一个公式，但我不知道如何反转它

Answer 1

似乎因为43比你的字母表大，你可以把数学倒过来。我不知道如何证明没有哈希冲突，因此这可能有边缘情况。例如：

letters = 'weiojpknasdjhsuert'

def hash(string_input):
    h = 3

    for i in range(0, len(string_input)):
        h = h * 43 + letters.index(string_input[i])

    return h

n = hash('wepostjapansand')
print(n)
# 9533132150649729383107184

def rev(n):
    s = ''
    while n:
        l = n % 43  # going in reverse this is the index of the next letter
        n -= l      # now reverse the math...subtract that index
        n //= 43    # and divide by 43 to get the next n
        if n:
            s = letters[l] + s
    return s

print(rev(n))
# wepostjapansand

使用更合理的字母表，如小写ascii和空格，这似乎仍然可以：

from string import ascii_lowercase 

letters = ascii_lowercase + ' '

def hash(string_input):
    h = 3

    for i in range(0, len(string_input)):
        h = h * 43 + letters.index(string_input[i])

    return h

n = hash('this is some really long text to test how well this works')
print(n)
# 4415562436659212948343839746913950248717359454765313646276852138403823934037244869651587521298

def rev(n):
    s = ''
    # with more compact logic
    while n > 3:
        s = letters[n % 43] + s
        n = (n - (n % 43)) // 43
    return s

print(rev(n))
# this is some really long text to test how well this works

基本思想是，经过所有的数学运算，最后一个数字是：

prev * 43 + letter_index

这意味着您可以通过采用prev模数43恢复最终字母索引。然后减去它，再除以43（这与数学正好相反），然后再做一次，直到你的数字为零