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

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.

• What do you mean by: "Even has to flip the (e, n)."? – otus Jul 17 '15 at 7:23
• Do you mean: Eve is restricted to invent (e', n') that differ from (e, n) in a small number of bits ? If yes, what is the convention used to map (e, n) to a bitstring ? In particular, would it prevent changing the customary e=65537 to e=1 by flipping the high-order bit, or would that be otherwise rejected by Alice ? – fgrieu Jul 17 '15 at 10:38
• @otus, flipping bits in the key. – drdot Jul 21 '15 at 5:45

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)

• Nice. Flipping a single bit of $e$ to make it $1$, if $e$ is suitable (most $e$ used in practice are), and that's accepted by Alice (which would not be unseen), is another way, involving less work. – fgrieu Jul 17 '15 at 14:13
• Thank you for the answer. A "random" odd integer of size circa n has a circa $2/log_{e}n$ probability of prime. I assume this $e$ is not the public exponent and is the natural logarithm constant, correct? Is it possible to point me to a reference of this claim? – drdot Jul 17 '15 at 14:44
• "alternatively, there would a probability approximately...", I think the number after this sentence is multiplication rather than exponentiation. – drdot Jul 17 '15 at 15:20
• @dannycrane: Yes, in $2/{\log_e n}$ the letter $e$ is the base of natural logarithm, not the public exponent. $\;$ No, in $(1 - 2/{\log_e n}) ^ {\log_2 n - 1} \approx 0.044$, exponentiation is meant; think of $\log_2 n - 1$ as a number of trials, each flipping a bit with odds $1-2/{\log_e n}$ of not reaching a prime. – fgrieu Jul 17 '15 at 15:55
• ... but I presume you could detect a forgery if you were suspicious, as setting $d$ to such a low value would make the "private key" easy to factor. – Maarten Bodewes Jul 17 '15 at 22:55