I have been reading up on RSA attacks and came across one that could be called a

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=Pemod N he could multiply it by 2emodN (essentially doubling the original plaintext) and send it to the oracle. The oracle will decrypt and find 2PmodN. 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 log2N 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.

Explanation / Answer

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

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

Actually, some of those < should be ?, 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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.