# RSA algorithm, relationship of the plaintext $m$ with $p$

I am studying the RSA algorithm. If for example the plaintext $$m$$ has some relationship with prime $$p$$, let's say $$m$$ is multiple of $$p$$ (where $$p$$ is the $$p$$ in $$n=p \times q$$). Can this give an attacker some information given we know ciphertext $$y$$ and public key?

• Is it Textbook RSA? does the attacker know there is a relation? – kelalaka Nov 30 '19 at 5:32
• Yes it is. And yes the attacker knows this relation. – Pitsi Nov 30 '19 at 5:37
• No the adversary does not know that. No other information for p. – Pitsi Nov 30 '19 at 8:43
• Hint (clarified): Identify two quantities that the adversary knows and that $p$ divides. What qualification can you give to $p$ w.r.t. theses two quantities? – fgrieu Nov 30 '19 at 9:54
• Is $m$ being a multiple of $p$ the only possible relation? – SEJPM Nov 30 '19 at 12:39

So after trying a few examples with small numbers, it turns out that if message $$m$$ is a multiple of $$p$$, $$m=a\times p$$ then $$\gcd(y,n)=p$$, where y the known ciphertext. The rest is easy to compute.
• Yes it is $e$. Yes $y$ was better if we assume that $y=(mp)^e \bmod n$ – kelalaka Dec 1 '19 at 10:02
• That's now much better! Beware however that you did not really give an explicit proof that $\gcd(y,n)=p$, and that you need the unstated $m\ne0$ (or equivalently $y\ne0$) for that to hold. – fgrieu Dec 1 '19 at 19:23
• You can prove that if $m$ is a multiple of $p$ and in $[1,n)$, so is $y=m^e\bmod n$ (hint: if $r\equiv s\pmod u$ and $v$ divides $u$, then $r\equiv s\pmod v$). Then that $\gcd(y,n)$ is a positive multiple of $p$. Then that it is $\gcd(y,n)=p$. – fgrieu Dec 2 '19 at 9:54