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?

  • 1
    $\begingroup$ Is it Textbook RSA? does the attacker know there is a relation? $\endgroup$ – kelalaka Nov 30 '19 at 5:32
  • $\begingroup$ Yes it is. And yes the attacker knows this relation. $\endgroup$ – Pitsi Nov 30 '19 at 5:37
  • $\begingroup$ No the adversary does not know that. No other information for p. $\endgroup$ – Pitsi Nov 30 '19 at 8:43
  • 2
    $\begingroup$ 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? $\endgroup$ – fgrieu Nov 30 '19 at 9:54
  • $\begingroup$ Is $m$ being a multiple of $p$ the only possible relation? $\endgroup$ – 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.

|improve this answer|||||
  • $\begingroup$ Yes it is $e$. Yes $y$ was better if we assume that $y=(mp)^e \bmod n$ $\endgroup$ – kelalaka Dec 1 '19 at 10:02
  • $\begingroup$ @fgrieu forgive me for the confusion. In my initial question I wrote m as the message and in my answer I meant x as the message. I corrected it. $\endgroup$ – Pitsi Dec 1 '19 at 18:50
  • $\begingroup$ 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. $\endgroup$ – fgrieu Dec 1 '19 at 19:23
  • $\begingroup$ @fgrieu you are right. This is not a proof for sure. It seems to work for different examples but I would also like to know more. $\endgroup$ – Pitsi Dec 2 '19 at 2:34
  • $\begingroup$ 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$. $\endgroup$ – fgrieu Dec 2 '19 at 9:54

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.