Collision$-$Resistant Hashing from RSA $(25$pts$)$ Let N $=$ pq be an RSA modulus and take e in N to be a prime that is also relatively prime to $\backslash$phi $($N$).$ Let u $ $$ Z$$ N$,$ and define the hash function HN$,$e$,$u : Z$$ N $\backslash$times $\{0,...,$e $1\}->$ Z$$ N where HN$,$e$,$u$($x$,$y$)=$ xeuy in Z$$ N$.$ In this problem, we will show that under the RSA assumption, HN$,$e$,$u defined above is collision resistant. Namely, suppose there is an efficient adversary A that takes as input $($N$,$e$,$u$)$ and outputs $($x$1,$y$1)=($x$2,$y$2)$ such that HN$,$e$,$u$($x$1,$y$1)=$ HN$,$e$,$u$($x$2,$y$2).$ We will use A to construct an efficient adversary B that takes as input $($N$,$e$,$u$)$ where u $ $$ Z$$ N and outputs x such that xe $=$ u in Z$$ N$.($a$)(10$pts$)$ Show that using algorithm A defined above, algorithm B can efficiently compute a in ZN and b in Z such that ae $=$ ub $($mod N$)$ and $0=|$b$|<$ e$.$ Remember to argue why any inverses you compute will exist. $($b$)(15$pts$)$ Usetheabove relation to show how B can efficiently compute x in ZN suchthat xe $=$ u$.$ Note that B does not know the factorization of N$,$ so B cannot compute b$1($mod $\backslash$phi $($N$)).$ Hint: What is gcd$($b$,$e$)?$