# How do RSA implementations avoid cases where the ciphertext and N are not coprime?

I'm trying to better understand RSA. One attack I've read about is when the encrypted message $$y$$ and $$N = p\cdot q$$ share a common factor. If this happens, we can easily factor $$N$$ to obtain $$p$$ and $$q$$.

What are some strategies that can mitigate this potential issue?

• Who cares about that? What is the probability of such an event? Did they tell you a real case of this attack? Besides, you should provide the link of your resources. Commented Mar 6 at 17:14
• Added a resource @kelalaka - I guess it's unlikely and not handled explicitly in practice, then? Commented Mar 6 at 17:31
• "Coprime" is the opposite of this situation - it means two numbers don't share any factors other than 1. Commented Mar 7 at 2:49
• @user2357112 right my question is what happens if they are coprime and we can factor $N$. Commented Mar 7 at 4:02
• @rookie: You still have the terminology backward. If they're not coprime, then we can easily factor $N$. Commented Mar 7 at 4:03

## 2 Answers

Actual RSA implementations do not attempt to avoid cases where the ciphertext and $$N$$ are not coprime. They don't need to. And in some sense instead, they make sure $$N$$ is the product of distinct primes.

Maybe you have been given a proof that textbook RSA correctly decrypts under the hypothesis that the message is in $$\mathbb Z_N^*$$, that is an integer in $$[0,N)$$ and coprime to $$N$$, which is equivalent to the ciphertext being in $$\mathbb Z_N^*$$. However it turns out that a different proof can be made that instead uses the hypothesis that $$N$$ is the product of distinct primes, and allows as message and ciphertext any integer in $$[0,N)$$. That's the practice.

Also, in practice, $$N$$ is so large that a vanishingly small fraction of $$X$$ in $$[0,N)$$ are not coprime to $$N$$. When $$N=p\,q$$ with $$p$$ and $$q$$ distinct primes, there are only $$p+q-1$$ such $$X$$, that is a proportion roughly $$2/\sqrt N$$ when $$p$$ and $$q$$ are of comparable size. Thus stepping on such exceptional $$X$$ can not happen accidentally, or by trying at random.

Further, since the factorization of $$N$$ is secret, $$0$$ is the only such $$X$$ that adversaries can manage to find. Argument: if they could find any $$X\in(0,N)$$ not coprime to $$N$$, they could efficiently compute a non-trivial divisor of $$N$$ as $$\gcd(X,N)$$, and thus break RSA when $$N$$ is the product of two primes, or make it much easier to factor $$N$$ otherwise. Since $$N$$ is (by hypothesis) chosen such that it's hard to factor (even in part), finding such $$X$$ must be hard.

• "in practice, N is so large that a vanishingly small fraction" - it doesn't matter - we generally require software to work every time whenever that is possible, not just most of the times. Commented Mar 7 at 1:30
• we don't expect software to work when the computer gets hit by lightning. with a 2048 bit N, the chance of this causing a problem is less than 1 in 2^1000 which means it will never happen. Commented Mar 7 at 5:58
• @user253751 - That's not true in practice. Some of the most reputable and widely used software such as git only work almost every time, not actually every time. Indeed, the internet itself (what you are using to post your comment) just works almost every time. There is a very tiny chance that when you posted the comment this website would receive "ik daesn't matter" instead of "it doesn't matter" but you yourself have considered that chance to be so small as to continue using the internet. Commented Mar 7 at 6:51
• @user253751: and, as pointed in the answer's second paragraph, even if it accidentally happens that RSA manipulates one of the exceptional value, RSA still enciphers/signs flawlessly. It would only open the possibility that someone cares to detect that fact and makes nefarious use of it to factor the public modulus. But that attacker has much more efficient avenues to try to factor the public modulus, including running Lenstra's ECM. And $N$ is chosen large enough that even this won't succeed.
– fgrieu
Commented Mar 7 at 7:08
• RSA is not used for data but encryption keys. Clearly it's trivial to append a bit so it's even. Commented Mar 7 at 21:36

Let’s say there is a 1024 bit key N = p x q. If I guess a number N’ and it is not co-prime with N then I can easily get a factor. My chances are about one in $$2^{512}$$. It’s not going to happen.

So preventing a message that is not co-prime with N is just pointless. First, because it’s not going to happen. Second because instead of hoping that the message might be not co-prime, the attacker can just guess a number and hope it’s not co-prime. And actually guessing numbers and hoping they are not co-prime to N is just about the worst algorithm to find a factor.

(Now there has been a point where lots of co-prime numbers appeared: Someone created lots of primes and used them to build private keys and put them into devices. Someone found that some devices had the same public keys - doesn’t help you breaking RSA but proves that primes were reused. So they checked and it turned out there were devices where one used primes #i and #i+1, and the next one used primes #i+1 and #i+2.)

Turns out to be a nice mathematical problem: Giving 100 million products of prime pairs, with about 1,000 primes being used in two products, find these products in reasonable time. Faster than calculating 10^16 gcd’s.