RSA: revealing the modulus factorization by choosing a bad message I started reading the book Cryptanalysis of RSA and its variants by M. Jason Hinek and I stumbled upon a phrase that intrigued me:


  plaintext
  messages that are relatively prime to the modulus (i.e., $gcd(m, N) &gt; 1$) should
  be avoided, since their ciphertexts $c = m^e\; mod \; N$ reveal the factorization of
  the modulus. 


Firstly, if $m$ is relatively prime to $N$, shouldn't $gcd(m, N) = 1$?

Secondly, how is it possible to extract the factorization of $N$ by choosing a bad message $m$?
Firstly, it's not co-prime to the modulus, so $\gcd(m,N)$ would be greater than $1$. 

Secondly, $N$ is the product of two (and only two) prime numbers $p$ and $q$, so if $\gcd(m,N)&gt;1$, then you know $m$ is one of the factors (and prime factors) of $N$.