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