Assume there exists a polynomial-time algorithm A that given an RSA public key (N, e)

Problem 6.4, 15 points. Assume there exists a polynomial-time algorithm A that given an RSA public key (N, e) can invert 1% of all ciphertexts CE Zy for plain RSA encryption scheme. That is, given (N, e) and C = M mod N it can efficiently compute M if C happens to be in a "weak" 1% fraction of all ciphertexts. Show that then there exists an algorithm that given (N, e) inverts every ciphertext C E Zy with probability more than 1/2, and is usually efficient (runs in expected polynomial time). Hint. Use the multiplicative property of RSA: for every public key (N, e) and M1, M2 E ZN, Me . ME = (M1 . M2) ( mod N)