# Breaking RSA if small subset invertible

I am trying to solve a problem which states that one can invert RSA if a small subset of the cipher text are invertible, the problem is as follows:

Given a function which can invert the RSA encryption that is given $C=M^e$, the function can compute $M$ for small subset (typically 1% of the ciphertext space) of the ciphertexts. Then show that all the ciphertexts generated by RSA can be inverted with a good probability.

There was a hint given with the question that : $M_1^e*M_2^e \equiv (M_1*M_2)^e mod N$, suggesting to take a direction that uses this property

• This question may be better suited for cs.stackexchange.com , but you can probably get an answer here too. The point is that you want to show you can break the cipher QUICKLY with high probability given the assumptions. RSA can be broken easily if you spend enough time to factor the public key N. It just may take a really, really long time. Nov 18 '14 at 22:48
• ^^ +1 Specifically, consider how the data you are given collapses the tree of possible prime factors and thus decreases the number of things you need to check. Nov 18 '14 at 22:56
• In the above question I do not know the structure or any other property of the small ciphertext space that can be inverted, I just know that there exists an adversary that can invert cipher texts in a small subspace. I do not understand how this information can help mr reduce the number of prime factors to search for. Nov 18 '14 at 23:02
• Is there a reason you deleted your question? Nov 19 '14 at 19:51

Let $\mathcal{K}$ be your pairs of known ciphertexts and plaintexts (the ~1% you mention in your question). You know $N$ and $e$ and receive $C = M^e$. You want to compute $M$.

Algorithm:

1. If $(C,\color{gray}{M}) \in \mathcal{K}$, decode to $M$.

2. Else, pick an arbitrary $(C_1,M_1) \in \mathcal{K}$ and compute

$$C_2 = C_1 C = M_1^e M^e = (M_1 M)^e \pmod{N}.$$

If $(C_2,\color{gray}{M_2}) \in \mathcal{K}$, decode to $M_2 M_1^{-1} \pmod{N}$.

3. Else, repeat step 2 for a different pair.

Experimentally, this appears to work. I haven't attempted to work out the probability of failure.

• In the above solution there is a very good possibility that even if you repeat step 2 for all the possible $(C_1,M_1) \in K$ you might not get a $C_2 \in K$, this is because $K$ is a very small subspace of the overall space. Nov 18 '14 at 23:36
• Hm... my intuition was that on each step you had about a $|\mathcal{K}|/N$ chance of getting a hit, which adds up quick enough. Nov 18 '14 at 23:51
• @Akshay: I just tried it out experimentally (with parameters $p=1237$, $q=2237$, $N=2767169$, $e=65537$, $|\mathcal{K}|=27671$, and a cutoff of 500 iterations). The algorithm worked fine. Nov 19 '14 at 1:59
• these are quite small numbers for RSA primes, typically you have primes of 512 bit length each. The probability K/N for such large primes is very low. Nov 19 '14 at 7:51
• $(0.01*2^{512})/2^{512} = (0.01*2767169)/2767169$ Nov 19 '14 at 15:05