Decrypt all RSA ciphertexts if you can break 1% of them I was given a cryptography question during an interview the other day. 

Imagine you are given an efficient algorithm which for a given RSA public key (n,e) is able to decrypt 1% of the messages encrypted with that key. 

1% means that the algorithm will deterministically decrypt 1% of all possible ciphertexts on the first call, and will never decrypt the other 99% of all possible ciphertexts with any number of invocations. 

Figure out an algorithm that uses this one and can decrypt any message. Any ideas?
The attacker wants to find $m = c^d$ but doesn't know $d$, but they can find $m'=(c')^d$ for a significant fraction of random $c^\prime$s. Assume that $\mathrm{GCD}(c, n)=1$.

The attacker chooses a random $r$ with $\mathrm{GCD}(r, n)=1$ and computes a new ciphertext $c^\prime$:

$c^\prime = c \cdot r^e$

This ciphertext is uniformly distributed among all ciphertexts with $\mathrm{GCD}(c^\prime, n)=1$. So the attacker has a 1% chance that they can compute the corresponding message $m^\prime$. If it doesn't work, the attacker simply chooses a new $r$.

Relate $m'$ to existing variables:

$m^\prime = (c^\prime)^d  = c^d \cdot r^{e \cdot d} = c^d \cdot r = m \cdot r$

Solve for $m$:

$m = m' \cdot r^{-1}$

$r^{-1}$ can be efficiently computed using the extended Euclidean algorithm. This means that an attacker who can break a significant fraction of messages can break all of them.

We assumed that GCD(c, n)=1. If it's not, that GCD is a factor of $n$. In the two-prime RSA case this is a complete break. In multi-prime RSA divide out that factor and you're back to the GCD(c, n)=1 case.