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.

  • $\begingroup$ Textbook RSA or padded RSA? $\endgroup$ – mikeazo Dec 5 '12 at 13:28
  • $\begingroup$ Textbook RSA... $\endgroup$ – proctr Dec 5 '12 at 13:39
  • $\begingroup$ Can we get your RSA-Crack? ;-) $\endgroup$ – 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$.

  • 2
    $\begingroup$ 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. $\endgroup$ – CodesInChaos Dec 5 '12 at 14:12
  • $\begingroup$ @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? $\endgroup$ – Ali Gajani Dec 5 '13 at 19:48
  • 1
    $\begingroup$ @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. $\endgroup$ – mikeazo Dec 5 '13 at 20:00
  • 1
    $\begingroup$ @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. $\endgroup$ – mikeazo Dec 5 '13 at 20:04
  • $\begingroup$ @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? $\endgroup$ – Ali Gajani Dec 5 '13 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.