SU CTF 2014 – Rolling Hash Write up
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?
Well, the point is 10**30 is a very large number and calculating the modulus has no effect on output. also 256 is a power of 2.
Given code calculates ASCII code for each character of input and multiplies it in 256 ** (l-i-1) that makes their bits shift (8*k) then adds all results together. So representation of 1317748575983887541099 in binary contains concatenated binary codes of flag in reverse order. I used this site to convert this number to binary.
chars = [ 0b01000111, 0b01101111, 0b01101111, 0b01100100, 0b00100000, 0b01001100, 0b01110100, 0b00000000, 0b00000000, ] flag = '' for ch in chars: flag = flag + chr(ch) print flag
Well, that site failed in last bits and this code outputs ‘Good Lt’ but it’s very easy to guess that flag was Good Luck
EDIT: a better solution for the last step mentioned in comments:
flag = '' number = 1317748575983887541099 p = number while p > 0: flag = chr(p%256) + flag p = p / 256 print flag