Find a hash encryption input from an output [closed]-CodePudding

I have this function hash() that encrypts a given string to an integer.

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

So if I do print(hash('post')), my output is: 11231443

How can I find what my input needs to be to get an output like 1509979332193868 if the input can only be a string from letters? There is a formula inside the loop body but I couldn't figure out how to reverse it.

CodePudding user response：

It seem like since 43 is larger than your alphabet, you can just reverse the math. I don't know how to prove there are no hash collisions, so this may have edge cases. For example:

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

With a more reasonable alphabet, like lowercase ascii and a space, this still seem to be okay:

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

The basic idea is that after all the math, the last number is:

prev * 43   letter_index

This means you can recover the final letter index by taking the prev modulus 43. Then subtract that and divide by 43 (which is just the reverse of the math) and do it again until your number is zero.