2

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

iosmanthus
  • 21
  • 3
  • 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 01:44
  • 4
    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 04:27

0 Answers0