# Why does gcd(m,N) have to be 1 in RSA?

In the RSA algorithm, if an attacker wants to get $d$, the attacker does this simply by encrypting random messages $m < N$.

If the attacker ﬁnds a message $m_1$ that the attacker can not encrypt since $\gcd(N ,m_1) \neq 1$, does this help the attacker in any way in any way?

I don't know why the $\gcd(m,N)$ has to be $1$. What happens if $\gcd(m,N) \neq 1$?

What happens if $\gcd(m,N) \neq 1$?
Actually, RSA works just fine; we have $((m^e)^d) \equiv m \pmod N$ in all cases, includes ones which $m$ and $N$ are not relatively prime.
What is an issue is if someone notices that $\gcd(m, N) \neq 1$. If that is the case (and $m \ne 0$), then $\gcd(m, N)$ is a nontrivial factor of $N$, that is, either $p$ and $q$, and so that rather leaks the factorization of $N$.
Now, the probability of guessing $m$ that is not relatively prime to $N$ is astronomically small for the sizes of $N$ we use in practice, and so we don't worry about it.
• Addition: In Rivest, Shamir, and Adleman's work as of April 1977 (references), the proof required $\gcd(m,N)\neq1$. And, including in the published paper, $p$ and $q$ are large random primes but not explicitly distinct (nor explicitly independent). If we allow $p=q$ (modern expositions of RSA do not), $\gcd(m,N)\neq1$ is required for reversible encryption. That condition also ensures reversible encryption in some variants of RSA that have been investigated, including $N=p^2\cdot q$. – fgrieu Apr 8 '18 at 12:35