Answer the first question: Question 8.20 (about Construction 8.81 being a collision reisistent hash function). Everything else provided after is background knowledge.

8.20 Let GenRSA be as in Section 8.2.4. Prove that if the RSA problem is hard relative to GenRSA then Construction 8.81 is a fixed-length collision- resistant hashfunction. CONSTRUCTION 8.81 Define (Gen, H) as follows: . Gen: on input 1", run GenRSA(1") to obtain N, e, d, and select (N, e, y . H: if s = N, e, y, then Hs maps inputs in {0, 1}3m to outputs in Zx. Let f(a mod N] and fiymod N] y Z* . The key is s : defe def '(x) For a 3n-bit long string x -1. ..r3n, define def cs 8.21 Consider the following generalization of Construction 8.78: 8.20 Let GenRSA be as in Section 8.2.4. Prove that if the RSA problem is hard relative to GenRSA then Construction 8.81 is a fixed-length collision- resistant hashfunction. CONSTRUCTION 8.81 Define (Gen, H) as follows: . Gen: on input 1", run GenRSA(1") to obtain N, e, d, and select (N, e, y . H: if s = N, e, y, then Hs maps inputs in {0, 1}3m to outputs in Zx. Let f(a mod N] and fiymod N] y Z* . The key is s : defe def '(x) For a 3n-bit long string x -1. ..r3n, define def cs 8.21 Consider the following generalization of Construction 8.78