Birthday collision attack implementation

Implement the given algorithm in C/C++ or Python to search for collisions in a toy example of a cryptographic hash function with n-but output where n are the first n bits of the SHA-1 message digest. Specifically, write the program which searches for collisions in the first 4,8,12,16... bits of the SHA-1 digest. Work with the hex representation of the digest. Search for a pair of SHA-1 digests with the first 1,2,3... symbols (in hex) being the same. Stop at the number of bits which takes a long time (over 15 mins).

For each output length, count the timing which the birthday attack takes.

Algorithm for finding collisions in constant space input: H: M->{0,1)n Output: Distinct x, x, st. H(x)-H(x) for i = 1, 2, , N do: x = H(x) x' = H(H(x)) if x = x' break x'=x, x=x0 for j 1 to i do: if H(x) -H(x) return x,x' and halt else x- H(x), x' - H(x') Algorithm for finding collisions in constant space input: H: M->{0,1)n Output: Distinct x, x, st. H(x)-H(x) for i = 1, 2, , N do: x = H(x) x' = H(H(x)) if x = x' break x'=x, x=x0 for j 1 to i do: if H(x) -H(x) return x,x' and halt else x- H(x), x' - H(x')