How many bits to flip in an RSA public key to do signature forgery?

Question

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.

Answer 1

If Eve can find an $n'$ that is prime (and $n'-1$ is relatively prime to $e$),then she can easily sign any message with that $n', e$ pair.

So, the question is: what is the probability that there exists a prime $n'$ such that there is only one bit difference between $n$ and $n'$, and $n' \not\equiv 1 \pmod {e}$ ? The answer is that it is quite good if $e > 3$, and decent even if $e = 3$. We'll assume $e$ is prime; in practice, it almost always is.

There are $log_2 n$ integers that have one bit difference from $n$ (we'll assume that Eve cannot flip bits that increase the size of $n$); flipping bit 0 will obviously yield a composite; flipping any other bit will yield an odd integer. A "random" odd integer of size circa $n$ has a circa $2/{\log_e n}$ probability of prime; if we model each of the odd integers as "random", then we would expect around $(\log_2 n - 1) 2/{\log_e n} \approx. 2.89$ primes to be about one bit flip away from $n$; alternatively, there would a probability approximately $(1 - 2/{\log_e n}) ^ {\log_2 n - 1} \approx. 0.044$ that none of the values 1 bit away from $n$ happen to be prime. When we include the condition with $e$, we know $n$ always satisifies the condition, and so a value with a bit flipped would have probability $1/(e-1)$ of satisfying it; from that, we can see that with $e=3$, we have an expected $1.44$ values satisfying it (hence we have a better than average chance); for $e>3$, the probability is even higher.

And, once we consider $n'$ values that aren't prime, but are easily factored (they're a large prime times a smooth number), the probability becomes much higher)