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.
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 &lt; 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 &lt; 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 &lt; mo$
$2s &gt; mo$

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

I send $s+k$.


If the oracle responds it means $s+k &gt; mo,$ so I assign $k:=\lfloor k/2 \rfloor$
If the oracle doesn't respond it means $s+k &lt; mo,$ so I assign $s:=s+k$



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