Consider a hash function H, which outputs the leading 80 bits of the SHA3-512 digest.Given two html files G.html and H.html, we want to find two files G1.html and H1.html such that• H(G1.html) = H(H1.html)• Semantic of G.html and G1.html are the same. That it, both ren- der the same content in browser. Similarly, semantic of H.html and H1.html are the same.The sizes of G.html and H.html are large. When divided into SHA3 blocks, each consists of around 215 blocks. The file folder include an example of G.html.(a) Give a practical algorithm that find G1.html and H1.html. Practical in the sense that it can be implemented and run in a typical high performance desktop.(b) Suppose the machine is able to compute hashes of 220 blocks in one second, estimate the time taken by you algorithm. You have to take into account housekeeping task if they are significant compare to the hash computation. In such cases, give a reasonable estimate of the time taken by the housekeeping1. Take special note that SHA3 is an iterative hash.
According to https://en.wikipedia.org/wiki/SHA-3, implementations of SHA3 take around 50 cycles per byte on single core. For blocksize of 32 bytes, seems reasonable to assume 220 blocks per second on a typical 3GHz machine.
