# 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?

• Do we have a duplicate of this question? I thought I already read an equivalent question, but couldn't find it. – CodesInChaos Dec 12 '14 at 12:15
• I didn't mean your cross-post, but some older question. – CodesInChaos Dec 12 '14 at 12:34
• @CodesInChaos I was thinking the same thing when I saw this. I remember answering a similar question, but can't find it. – mikeazo Dec 16 '14 at 12:45

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.

• Why can't the attacker simply add a character to the end of the message? There's a 1% chance that the new message will be decipherable. If not, continue adding characters. For each added character, the probability of success increases: after $n$ tries the probability is $1 - (0.99)^n$, and the attacker can add hundreds of thousands of characters per second. – Elliot Gorokhovsky Mar 18 '15 at 2:16