Is RSA-OAEP secure against Shor's factoring algorithm

Question

I've seen in this answer Can Shor's algorithm compromise RSA when both the public and private key are secret? that if textbook RSA is used (deterministic) the Shor's algorithm can reak it. However, if RSA is used with OAEP then Shor's algorithm cannot break it. The reason is that the known-plaintext pair doesn't include the randomness in the OAEP;

rfc8017 section-9.2

d. Generate a random octet string seed of length hLen.

rfc8017 B.2.1. MGF1

maskLen intended length in octets of the mask, at most 2^32 hLen

Then one needs $2^{31}$ try to break the RSA on average if they are able to produce enough Q-bits.

• Is my understanding correct?

  • If so, then make the seed >128-bit and be safe from Shor. Then, why there are so much fear of Shor's algorithm for RSA?

Answer 1

If so, then make the seed >128-bit and be safe from Shor. Then, why there are so much fear of Shor's algorithm for RSA?

Well, remember that the assumption in the original question was that we kept the RSA public key secret. That is a nonstandard assumption; we generally assume that the attacker knows the RSA public key (and in practice with most uses of RSA, he can easily learn it).

And, with knowledge of the RSA public key, Shor's algorithm can efficiently break it (assuming a reasonable sized Quantum Computer, of course); that is, he can learn the private key (and then do anything that the legitimate owner of the RSA private key can do) - the RSA padding mechanism does not offer any additional protection.