RSA least significant bit oracle attack

Question

I have been reading up on RSA attacks and came across one that could be called a least-significant-bit (LSB) oracle attack.

For the sake of clarity lets define RSA primes $(p, q)$, private key $d$ and the public key $(e, N)$ where $N$ is the modulus.

Now assume an oracle exists that will decrypt a given ciphertext $C$ using the private key $d$ and checks the parity of the decrypted cipher. i.e. it will return true or false if the decrypted cipher was even or odd respectively.

If an attacker intercepts an encrypted plaintext $C = P^e \mod N$ he could multiply it by $2^e\mod N$ (essentially doubling the original plaintext) and send it to the oracle. The oracle will decrypt and find $2P\mod N$. Now if $2P>N$ then the remainer will be odd, since $N$ is odd. If $2P<N$ then the remainder will be guaranteed to be even. The attacker will now know that either $P<N/2$ (oracle returned even) or $P>N/2$ (oracle returned odd).

This is the part where I am stuck, because apparantly you can somehow iteratively apply this principle and by iteratively shrinking the bounds of $P$ completely recover $P$ in $\log_{2}N$ iterations. I am having trouble seeing how the iteration would work.

If possible I would prefer a hint over a fully written out solution as I will learn more from doing it myself. I just need a little nudge in the right direction. Much appreciated.

Answer 1

Here's the next step in the iteration, which should be easy to understand:

Let's call the oracle on 2P and 4P:

• Answer (even,even) means, that $P<N/4$ (this is still easy: Otherwise either 2P or 4P would be greater than N).
• (even,odd) means $N/4\le P<N/2$.
• (odd,even) means $N/2\le P<3N/4$
• (odd,odd) means $3/4N\le P<N$.

If you continue with multiplying the factor for P with 2, you get the next round of iteration, where "odd" indicates the upper half of the interval and "even" indicates the lower half.

Answer 2

The approach with which I solved the problem is indeed as @tylo suggested. Initially we know that the target plaintext $P$ is within the bounds $[0,N]$ where the lower bound $LB=0$ and the upper bound $UB=N$.

Now we iterate the following algorithm $log_{2}N$ times to find P from the original intercepted ciphertext $C$

$C' = (2^{e}\mod N) * C$

if (Oracle(C') == even)
    UB = (UB + LB)/2;
else
    LB = (UB + LB)/2;