# RSA : common factor between M and n

Let's say that we have a classic RSA encryption, with n = p*q. For a given C, I saw on internet the RSA might be weak if we know that the plaintext M and n have a common factor. However, I wasn't able to find a proof of that.

We know that $$M=C^e \space mod\;n$$, with e being the public key. I tried to say that $$M = a + k*n$$, with a and k being positive integers, and to redo the algorithm. Therefore :

$$C = M^e\;mod\;n = (a + k*n)^e\;mod\;n = a^e\;mod\;n$$

And

$$M = C^d\;mod\;n = a^{d*e}\;mod\;n$$

However, this sounds useless, since we don't know a (even with brutal force, we would have to many values to compute if $$n$$ is big) and $$d$$, obviously since it's the private key. Does anyone can help me on this one?

It's quite simple; we know both $$C$$ and $$n$$; if $$M$$ has a common factor with $$n$$, so does $$C$$. So, we can just compute $$\gcd(C, n)$$. Since we know that $$M$$ and $$n$$ have a common factor, then this is not 1; we assume that $$C < n$$, so it's not $$n$$. Hence, that has to be a proper factor of $$n$$; if $$n$$ is a product of two primes, this will then be one of them, and so the two prime factors of $$n$$ are then $$\gcd(C, n)$$ and $$n / \gcd(C, n)$$.
Once we have the factorization of $$n$$ then (assuming we know the value $$e$$), computing $$d$$ is straight-forward.