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?
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.
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.
