Rolling Hash

Task:

flag="*********"
def RabinKarpRollingHash( str, a, n ):
        result = 0
        l = len(str)
        for i in range(0, l):
                result += ord(str[i]) * a ** (l - i - 1) % n
        print "result = ", result


RabinKarpRollingHash(flag, 256, 10**30)

output is 
1317748575983887541099 
What is the flag?

Solution:

Let take a closer look at hash function. It takes every character in given string, convert it to int and multiply it by power of 'a' modulo 'n'. But look at call of this hash:

RabinKarpRollingHash(flag, 256, 10**30)

a = 256, and it means that each multyplying by 'a' is equivalent of simple left-shifting. If input string is short enough we can just forget about 'n' and try to restore flag, using this code:

hashed_flag = 1317748575983887541099
result = ""
while hashed_flag > 0:
	byte = hashed_flag&0xff
	result += chr(byte)
	hashed_flag = hashed_flag - byte
	hashed_flag = hashed_flag >> 8

print result[::-1]

Flag: Good Luck