# 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) > 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$?

• This may be a typo in the book (or your quote)? (-> "plaintext messages that are not relatively prime to the modulus (i.e. $\gcd(m,N)>1$)...") – SEJPM Jul 23 '16 at 11:56
• I don't get this argument though; sure, an adversary might just happen to notice that $m^e$ is not relatively prime to $N$, and hence factor $N$. But it's equally likely they would notice, say $(m + s)^e$ is not relatively prime to $N$, for any particular $s$; by that line of reasoning, any input message is unsafe. – Thomas Jul 23 '16 at 14:11
• It's possible to reveal the factorization of a semi-prime by publishing a factor. Surprise, surprise. – CodesInChaos Jul 23 '16 at 15:10
• The wording is strange because you do not usually have to avoid picking bad messages. Accidentally picking an $m$ that is not co-prime to $N$ is equivalent to just randomly guessing one of the factors, which is exceedingly unlikely for properly sized moduli. The only thing I can think of is if you, for some strange reason, decide that you want to purposefully encrypt one of the prime factors of $N$ as part of a protocol. That is a bad idea and should definitely be avoided. – Travis Mayberry Jul 24 '16 at 2:06

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)>1$, then you know $m$ is one of the factors (and prime factors) of $N$.
• ... and $N/m$ would be the other one respectively... – SEJPM Jul 23 '16 at 11:59