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?


1 Answer 1


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$.

  • $\begingroup$ 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). $\endgroup$ May 22, 2018 at 14:23
  • 3
    $\begingroup$ @JᴀʏMᴇᴇ: the practice of giving hints to homework is well established on crypto.SE; this is discussed in that meta-question $\endgroup$
    – fgrieu
    May 22, 2018 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.