Scenario: Alice wants to verify a signature from Bob. Alice knows Bob's RSA public key (e, n). However, Alice is getting the data, the signature of the data and the public key from an attacker Eve. Assume the signature is compliant with PKCS# v1.5.
Now I know trivially Eve can generate an RSA key pair and signs the data herself and send the fake public key and fake signature to Alice. But I am going put a constraint on Eve. Eve cannot generate whatever key pairs she likes. Even has to flip the (e, n).
My question: What is the least number of bits she needs to flip in (e, n) such that she can forge the signature?
NOTE: she can either generate a signature from Bob's private key or she can generate a signature from some other private key she can compute from the corrupted public key or whatever attack she can come up with. As long as she can convince Alice the signature is from Bob.