# RSA most significant bit oracle attack

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

For the sake of clarity, let's 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 decrypted cipher -- it will return true or false if the decrypted cipher's most significant bit is 1 or 0.

How can I achieve such an attack while given a challenge cipher $$C$$! http://www.cits.rub.de/imperia/md/content/may/hw2.pdf

• are you looking for RSA least significant bit oracle attack – kelalaka Oct 30 '18 at 16:14
• No, on the contrary, I am looking for the solution for the MSB version – iosmanthus Oct 31 '18 at 1:44
• One issue is that, depending on the value of $N$, no such attack may be possible. For example, consider the case that $N \approx. 2^{2048} + 2^{1000}$ (and finding $p, q$ that yield such an $N$ is easy); in that case, the probability of finding a plaintext that encrypts to a ciphertext with a 1 msbit is essentially zero (probability $< 2^{-1048}$); hence the oracle gives you no useful information – poncho Oct 31 '18 at 4:27