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

  • $\begingroup$ are you looking for RSA least significant bit oracle attack $\endgroup$ – kelalaka Oct 30 '18 at 16:14
  • $\begingroup$ No, on the contrary, I am looking for the solution for the MSB version $\endgroup$ – iosmanthus Oct 31 '18 at 1:44
  • 3
    $\begingroup$ 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 $\endgroup$ – poncho Oct 31 '18 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.