Side-Channel attack on RSA decryption using comparison result with p,q? I was pointed to whether we could learn the secret key of RSA by repeatedly using following side channel:

We assume that there exists a side channel in RSA decryption using CRT that, if the most-significant bits of the input x (down to about half the size of x) are zero, reveals if:

$$x \bmod p &gt; x \bmod q$$

Can we learn the secret key through that side channel?
Some hints:


You know $p\,q$.
First assume $q&lt;p$ and find $q$ by dichotomic search.
Move to the slightly more difficult case $p&lt;q$.




In dichotomic search, it is given an integer interval $\big[a,b\big]$ and a Boolean function $F$ defined on that interval such that $F(a)\ne F(b)$. Dichotomic search always find $c$ in $\big[a,b\big)$ with $F(c)=F(a)$ and $F(c+1)=F(b)$, using $\approx\log_2(b-a)$ evaluations of $F$. It proceeds by repeatedly computing $c=\lfloor(a+b)/2\rfloor$, stopping when $c=a$, otherwise replacing $a$ or $b$ by $c$ according to if $F(c)=F(a)$ holds or not.



Define $F(x)$ to be the result obtained by submitting $x$ to the side channel. That is $F(x)=\text{true}\iff(x\bmod p)&gt;(x\bmod q)$.

By definition of the $\bmod$ operator in $x\bmod m$ (recognizable by neither having an opening parenthesis immediately on the left of $\bmod$, nor appearing on the right side of an expression with a matching $\equiv$ sign), for all $x$ and all $m&gt;0$ it holds that $0\le(x\bmod m)&lt;m$ and $m$ divides $x-(x\bmod m)$. It follows the properties
$$\begin{align}
x=(x\bmod m)&amp;\iff 0\le x&lt;m&amp;&amp;\text{and}\\
x&gt;(x\bmod m)&amp;\iff x\ge m
\end{align}$$

For the second bullet: When $0\le x&lt;p$ and thanks to the above properties, $F(x)$ reduces to $x&gt;(x\bmod q)$, then to $x\ge q$. Set $a=1$ and $b=\lfloor\sqrt{p\,q}\rfloor$, which we can compute. From the hypothesis $q&lt;p$, we get $q\le b&lt;p$. Therefore when $x\in\big[a,b\big]$ the function $F(x)$ tells whether $x\ge q$. It holds that $F(a)=\text{false}$ and $F(b)=\text{true}$. Thus dichotomic search yields $c$ in interval $\big[1,\lfloor\sqrt{p\,q}\rfloor\big)$ with $F(c)=\text{false}$ and $F(c+1)=\text{true}$, that is $c&lt;q$ and $c+1\ge q$. That reveals $q=c+1$.