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

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
@CodesInChaos, can you tell me why is Mike trying to divide the answer by i to get m1. Confused a bit. Why isn't c2 written as c2 = c1 . m^e mod n? – Ali Gajani Dec 5 '13 at 19:48
@AliGajani the output of RSA-Crack() would be $m_1\cdot i$. So to get $m_1$, you'd have to divide by $i$. Remember the goal is to get $m_1$ from a function which works with 0.01 probability. – mikeazo Dec 5 '13 at 20:00
@AliGajani you say why isn't c2 written as c2=.m^e mod n. What is m? In writing c2 the way I did I simply wanted to show that given a ciphertext you could compute another ciphertext with is related to the original in a predictable manner. In this case it was a multiply by 2. It could have been multiply by m too and that would have been fine. – mikeazo Dec 5 '13 at 20:04
@mikeazo Interesting. The description in wikipedia says E(mt) which I believe is the same thing you're trying to do here, which is right. So for instance if we compute the RSA-Crack() with the ciphertext 100 times, we will divide it by 100, which is 'i' This gives us a probability of 1.0 which serves as an answer. Correct? – Ali Gajani Dec 5 '13 at 20:42