RSA least significant bit oracle attack

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.

• Have you read e.g. Fischlin and Schnorr's "Stronger Security Proofs for RSA and Rabin Bits"? – K.G. Oct 15 '13 at 10:47
• Just a small sidenote: N is not prime (4th paragraph), it is odd. It should be ".. remainder will be odd, since N is odd, 2P is even and 2P<2N". – tylo Oct 15 '13 at 15:16
• @tylo you are completely right, changed the mistake. I was able to solve it yesterday very much like you suggested in your answer. I will be adding my eventual approach as well for completeness, but you have my upvote – Pankrates Oct 15 '13 at 16:17

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).
• Answer (even,odd) means $N/4<P<N/2$.
• (odd,even) means $N/2<P<3N/4$
• and (odd,odd) means $3/4N<P<N$.

Actually, some of those $<$ should be $\le$, but you get the picture.

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.

• we know that P < N, if 2P is odd, then 2P > N => P > N/2, if 4P is odd, then 4P > N => P > N/4. Where does that 3/4 comes from? – David 天宇 Wong Apr 16 '16 at 15:57
• ah, found out why :) the second iteration in an odd odd, you are not using 4P, but rather 2(2P-N) because we already had 2P > N – David 天宇 Wong Apr 16 '16 at 16:45

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;