#!/usr/bin/python3 import sys if sys.version_info < (3,): print("Use Python 3 to run this code") exit(1) import hashlib, random sha256 = hashlib.new('sha256') # Change this to something lower for experiments but make sure to put it back to 48 afterwards # Must be a multiple of 4 hashlen = 48 # A hash function: # The input is an integer. # The output is a 'hash_len' bit string, encoded in hex (8 bytes) def H(number:int) -> str: hash = sha256.copy() hash.update(str(number).encode('ascii')) return hash.hexdigest()[0:hashlen//4] assert H(123) != H(1230) assert len(H(1))*4 == hashlen # This is not the right solution. Too slow. # On my computer: # hashlen | time # 16 | 0.1 sec # 24 | 45 sec # 32 | 7 hours # 48 | estimate: 52 years # 64 | estimate: 3.4 million years # Of course, this is highly unoptimized code. The same algorithm would run muuuch faster # if implemented well def find_collision_slow(): while True: x1 = random.randint(0,2**(hashlen*2)) x2 = random.randint(0,2**(hashlen*2)) h1 = H(x1) h2 = H(x2) if h1==h2 and x1!=x2: return (x1,x2) # Commented out because it's too slow. You can try it out using smaller values of hashlen # (x1,x2) = find_collision_slow() # print (x1,x2) # assert x1 != x2 # assert H(x1) == H(x2) # Collision finding using birthday attack # Returns a pair (x1,x2) such that H(x1)=H(x2) # My code, quite unoptimized (using off-the-shelf python datastructes) takes the following time: # hashlen | time # 16 | <0.1 sec # 24 | <0.1 sec # 32 | 0.5 sec # 48 | 72 sec # 64 | 7min 20sec def find_collision(): return (1,2) # Put your code here (x1,x2) = find_collision() print (x1,x2) assert x1 != x2 assert H(x1) == H(x2)