Explanation for the Python class: x$1$ and x$2$ are messages: x$1=$ "Bob sends $10$ to Oscar's account" x$2=$ "Bob sends$1000$ to Oscar's account" For x$1$ and x$2,$ Oscar wants to create two messages m$1$ and m$2$ that satisfy the following properties: $1)$ hash$($m$1)==$ hash$($m$2)($the implemented hash function below, called $"$h$")2)$ Semantic meaning of original messages x$1$ and x$2$ must be preserved. In other words, m$1$ and m$2$ should look like x$1$ and x$2,$ respectively. Hint: You can create such messages by appending invisible characters $($spaces and tab$)$ to the original messages. $($This is what I have been attempting to do$)3)$ The collision search must be effective. According to the argument of birthday attack, the number of messages you need to generate until the first collision found is O$(2^($n$/2)),$ where n is the number of hash output bits. The output bits I am testing with are $40$ and $50.($The expected outputs are listed below$).$ Expected Output: $==$ elapsed time in seconds: $4\mathrm{.}381968021392822$ Bob sends $10$ to Oscar's account $($Whitespace $/$ tabs following with a period after them$)$ Bob sends$1000$ to Oscar's account $($whitespace and tabs following with a period after them$)$ True $==$ Given $/$ already completed portion of the Class $($is not to be edited or changed!$)$: import time class Collision: $\_\_$slots$\_\_=["$H$1","$H$2",$ "output$\_$bits", "modulus", "hash$\_$func"$]$ def $\_\_$init$\_\_($self$,$ output$\_$bits, hash$\_$func$)$: self.H$1=$ self.H$2=$ self.output$\_$bits $=$ output$\_$bits self.modulus $=$ pow$(2,$ output$\_$bits$)$ self.hash$\_$func$=$ hash$\_$func def h$($self$,$ x$)$: return self.hash$\_$func$($x$)$

My code:

import time

class Collision:

$\_\_$slots$\_\_=["$H$1","$H$2",$ "output$\_$bits", "modulus", "hash$\_$func"$]$

def $\_\_$init$\_\_($self$,$ output$\_$bits, hash$\_$func$)$:

self.H$1=\{\}$

self.H$2=\{\}$

self.output$\_$bits $=$ output$\_$bits

self.modulus $=$ pow$(2,$ output$\_$bits$)$

self.hash$\_$func$=$ hash$\_$func

def h$($self$,$ x$)$:

return self.hash$\_$func$($x$)\%$ self.modulus

def search$($self$,$ x$1,$ x$2,$ depth$=40)$:

hash$1=$ self.h$($x$1)$

hash$2=$ self.h$($x$2)$

if hash$1==$ hash$2$:

return x$1,$ x$2$

if depth $>0$:

# Recurse on x$1+""$ and x$2+""$

collision $=$ self.search$($x$1+"",$ x$2+"",$ depth $-1)$

if collision:

return collision

# Recurse on x$1+"\backslash$t$"$ and x$2+"\backslash$t$"$

return self.search$($x$1+"\backslash$t$",$ x$2+"\backslash$t$",$ depth $-1)$

# If depth limit reached

return None

def confirmCollision$($self$,$ m$1,$ m$2)$:

hash$1=$ self.h$($m$1)$

hash$2=$ self.h$($m$2)$

return hash$1==$ hash$2$ and hash$1$ in self.H$1$ and hash$2$ in self.H$2$

def main$()$:

output$\_$bits $=40$ # try $10$ or $20$ first

x$1=$ "Bob sends $$10$ to Oscar's account"

x$2=$ "Bob sends $$1000$ to Oscar's account"

collision $=$ Collision$($output$\_$bits, hash$)$ # Python hash funciton is used, though any hash functions should work

start $=$ time.time$()$

result $=$ collision.search$($x$1,$ x$2)$

end $=$ time.time$()$

if result:

m$1,$ m$2=$ result

print$("$elapsed time in seconds:", end $-$ start$)$

print$($m$1,".")$

print$($m$2,".")$

print$($collision$.$confirmCollision$($m$1,$ m$2))$

else:

print$("$No collision found within the depth limit$.")$

if $\_\_$name$\_\_=="\_\_$main$\_\_"$:

main$()$

The only thing that can be modified is search and main in order to complete the collision search with a depth of $40,$ it should take around $5$ seconds to complete