def small_hash_colision(M_bits, T_bits):
M_bits: int -- dimension of the message space
T_bits: int -- dimension of the hash space
{(bytes, bytes, bytes)} -- message1, message2, hash
{(b'', b'', b'')} -- if no collision found
num_samples = 1 * isqrt(N)
num_samples += num_samples//5 + 1 # num_samples = 1.2 * isqrt(N) + 1
print(f'Making a list of {num_samples} hashes')
print(f'Probability of finding a collision is {same_birthday(num_samples, N)}')
for i in range(num_samples):
m = random.getrandbits(M_bits) # Get random message
#m = random.randint(0, M_bits-1)
t = small_hash(m, T_bits) # Hash it
for i in range(len(t_list)):
for j in range(i+1, len(t_list)):
if t_list[i] == t_list[j]:
print('Collision found!')
return m_list[i], m_list[j], t_list[i]
print('Collision not found :(')