7. Suppose Bob has the public key (n, e) = (21733, 691). You areEve, and you have intercepted the ciphertext C = 21012. On a whim,you decide to check whether C and n are relatively prime, and toyour delight, you discover that they are not! Show how you can usethis to recover the plaintext M.
Note: The chance that M (or equivalently C) is not relativelyprime to the modulus n is1/p + 1 /q? 1/pq , and when p, q are bothlarger than 100 digits long, this probability is less than 10^?99!So although this is a vulnerability that one should be aware of, inpractice it doesn’t cause issues very often.
