0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ What if you make $r\cdot m > n$? $\endgroup$
    – kelalaka
    Apr 8 at 18:48
  • $\begingroup$ It will round via $\bmod n$ $\endgroup$
    – kelalaka
    Apr 8 at 19:37
  • $\begingroup$ @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$ $\endgroup$
    – This Agio
    Apr 8 at 19:38
  • 2
    $\begingroup$ @kelalaka Thankyou! Now I understood, you were so much helpful. $\endgroup$
    – This Agio
    Apr 9 at 9:45
  • 1
    $\begingroup$ When you succeed, could you write an answer? $\endgroup$
    – kelalaka
    Apr 9 at 19:27
0
$\begingroup$

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.

$\endgroup$

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.