# Chosen Ciphertext Attack textbook RSA

I'm trying to perform a chosen-ciphertext attack against an RSA oracle. I have $$c$$ as the ciphertext I want to decrypt, $$e$$ and $$n$$. I already know that I could choose a number $$r$$, compute $$r^e \cdot c$$, make the oracle decrypt, and return $$r\cdot m$$.

The problem is that this particular oracle checks if $$m \bmod mo = 0$$ where $$m$$ is the decrypted ciphertext I sent and $$mo$$ is the original message which I'm trying to get. If it's equal to $$0$$ (like $$rn$$) it won't print $$m$$ so I can't use that attack.

I don't really know what to do.

$$n$$ is pretty big (1024bit) so I can't factorize it. Maybe there is a small adjustment to the mentioned attack, but I'm really stuck. If anybody could give me a hint I would really love it.

• What if you make $r\cdot m > n$? It will round via $\bmod n$ Commented Apr 8, 2021 at 18:48
• @kelalaka I think that $r \cdot m$ should be less than n. I tried making the $r$ that big and I'm able to pass $m \mod mo = 0$ which is very good, but when i do $m/r$ is always less than 1 so i think that's not the right thing to do. Sorry if i just changed the answer, i was making a coding mistake. $r$ it's just to big, when i devide by it I always get a number smaller than $1$ Commented Apr 8, 2021 at 19:38
• Let $m$ be the return value from the oracle, then $m = mo \cdot r \bmod n$ then $m = mo \cdot r + k \cdot n$ for some integer $k$ Commented Apr 8, 2021 at 19:42
• @kelalaka Thankyou! Now I understood, you were so much helpful. Commented Apr 9, 2021 at 9:45
• When you succeed, could you write an answer? Commented Apr 9, 2021 at 19:27

Thanks to the help of @kelalaka i found a solution.

### The idea

My exploit was based on the fact (I don't really know if it's always true) that if $$r \cdot mo < n$$ the oracle won't print anything, otherwise it will print some number, which unfortunate is not $$r \cdot mo$$.
So, $$\lfloor \frac{n}{mo} \rfloor^e \cdot (mo^e \mod n)$$ would produce no answer ($$\lfloor \frac{n}{mo} \rfloor \cdot mo < n$$) while $$\lfloor \frac{n}{mo} + 1\rfloor^e \cdot (mo^e \mod n)$$ would produce an answer, even if uncorrect.

### The solution

First I choose a number $$r$$ smaller than the original message $$mo$$. Then, until the oracle responds i keep sending $$r\cdot 2^i$$ increasing $$i$$ by $$1$$ each step.
When the oracle respond it means that I found a number $$s = r\cdot 2^{i-1}$$ such that

• $$s < mo$$
• $$2s > mo$$

Let $$k:=\frac{s}{2}$$. I iterate the following process until $$k > 0$$:

1. I send $$s+k$$.
• If the oracle responds it means $$s+k > mo,$$ so I assign $$k:=\lfloor k/2 \rfloor$$
• If the oracle doesn't respond it means $$s+k < mo,$$ so I assign $$s:=s+k$$

In the end $$s$$ should be exactly $$mo$$.
The "algorithm" (it's a bit confused, I'm sorry) I proposed should get $$mo$$ in $$O(\log_2 n)$$ so it's tractable.