# Get RSA PlainText without Knowing Private Key

If I have an algorithm,RSA-Crack(), that, for a given RSA public key (n,e), is able to decrypt 1% of the messages encrypted with that key (without knowledge of the corresponding private key).Can there be an efficient algorithm that uses RSA-Crack() as a building block, and can decrypt any message - without knowing the private key.

Now, I know that I can use the factoring algorithm to devise the value of p & q from N (that is a part of the public key), after which I can use the Euler function to generate the new decryption exponent (e) and all. But my main criteria is how do I use RSA-Crack() as a Building Block to decrypting the message.

-
 Textbook RSA or padded RSA? – mikeazo♦ Dec 5 '12 at 13:28 Textbook RSA... – proctr Dec 5 '12 at 13:39 Can we get your RSA-Crack? ;-) – Paŭlo Ebermann♦ Dec 5 '12 at 22:33

## 1 Answer

A message is encrypted with RSA as follows:

$c_1 = m_1^e \bmod{n}$

If I throw this message at your function RSA-Crack(), there is a $0.01$ probability that the function will return the plaintext $m_1$.

To increase this probability, we can use the malleability of textbook RSA (this is also known as the homomorphic property of textbook RSA). Given $c_1$, compute $c_2 = c_1\cdot 2^e\bmod{n} = (m_1\cdot 2)^e \bmod{n}$. There is again a $0.01$ probability that $c_2$ can be broken by your function. Since a break there would give you $m_1$ (just divide the answer by $2$ if it is successful), the probability that you have recovered $m_1$ is now $0.02$.

Repeat this process replacing $2$ with $3,4,5,\cdots,100$ and you have a guaranteed break of the plaintext. I.e, compute $c_i = m_1\cdot i^e\bmod{n} = (m_1\cdot i)^e\bmod{n}$ and run $c_i$ through your RSA-Crack() function. If it is successful, divide the answer by $i$ to get $m_1$.

-
It's important to note that for random choice of $i$ you reach almost every possible ciphertext with almost equal probability. Without that property the crackable 1% might never be reached with this method. – CodesInChaos Dec 5 '12 at 14:12