RSA : common factor between M and n

Question

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?

Answer 1

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.

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.