# 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 > x \bmod q$$

Can we learn the secret key through that side channel?

Some hints:

• You know $p\,q$.
• First assume $q<p$ and find $q$ by dichotomic search.
• Move to the slightly more difficult case $p<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)>(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>0$ it holds that $0\le(x\bmod m)<m$ and $m$ divides $x-(x\bmod m)$. It follows the properties \begin{align} x=(x\bmod m)&\iff 0\le x<m&&\text{and}\\ x>(x\bmod m)&\iff x\ge m \end{align}

For the second bullet: When $0\le x<p$ and thanks to the above properties, $F(x)$ reduces to $x>(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<p$, we get $q\le b<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<q$ and $c+1\ge q$. That reveals $q=c+1$.

• To knowingly only give hints is to provide a partial answer. This is a question and answer forum, this is not school in which you're a teacher. Deciding what's best for the OP is not the duty of whoever chooses to answer (incompletely or otherwise). May 22 '18 at 14:23
• @JᴀʏMᴇᴇ: the practice of giving hints to homework is well established on crypto.SE; this is discussed in that meta-question
– fgrieu
May 22 '18 at 14:27