I've seen a couple of posts stating the following fact: If $(n = pq,e)$ is the public key of an RSA instance and some plaintext block $m$ has a common factor with $n$, then also the corresponding ciphertext block $c$ has the same common factor with $n$.

Yet, I could not find any formal proof of this statement. I tried to come up with one by myself, but I could not quite make it. What I have so far:

As $m<n$, $m = p * z$ or $m = q*z$ for some $z \in \mathbb{Z}$. Assume w.l.o.g $m = p * z$. Then $c = m^e \mod n = (p * z)^e \mod n$. I don't really know how to continue. One could rewrite this further as $c = ((p^e \mod n) * (z^e \mod n)) \mod n$ but that didn't help me either. Does someone have a hint for me?

Any help is appreciated! Thank you.


Fix $m = p \cdot z$ for some $z$. Let $c = m^e \bmod n = p^e \cdot z^e \bmod n$, so that $c \equiv p^e \cdot z^e \pmod n$. This means that there exists some $k$ such that $$c = p^e \cdot z^e + k \cdot n = p^e \cdot z^e + k \cdot p \cdot q.$$ Does $p \mid c$?


Here's one way to argue for this property using the Chinese Remainder Theorem:

Let $m,e,n=pq$ be arbitrary with $\gcd(p,q)=1$. Let's assume $\gcd(m,n)>1$ and more precisely wlog $\gcd(m,n)=p$. Now we shall apply the Chinese Remainder Map $\theta:\mathbb Z_n\to\mathbb Z_p\times \mathbb Z_q:x\mapsto(x\bmod p,x\bmod q)$ which will yield $\theta(m)=(0,y)$ for $y:=m\bmod q$. Now, $\theta$ is a ring isomorphism, meaning that it preserves multiplication and addition, that is $\theta(m^e)=(0,z:=y^e\bmod q)$. Because $\theta$ is a bijection, its inverse is unique and the solution $c\in\mathbb Z_n$ to the following set of equations:

\begin{align*} c&\equiv0\pmod p\\ c&\equiv z\pmod q \end{align*} And as you can easily verify, $c=zp$ satisfies these equations, meaning it is the encryption of $m$ and thus a multiple of $p$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.