Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
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
up vote 4 down vote accepted

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.

share|improve this answer
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 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 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;
    LB = (UB + LB)/2;
share|improve this answer
Great! Now, don't forget to accept the answer you think fits your question best. ;) – e-sushi Oct 15 '13 at 17:28
I will give @tylo the credits for his efforts :) – Pankrates Oct 15 '13 at 17:29
By the way: welcome at Crypto.SE! – e-sushi Oct 15 '13 at 17:30
I thank you kind sir/madam – Pankrates Oct 15 '13 at 17:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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