1
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Yes it is $e$. Yes $y$ was better if we assume that $y=(mp)^e \bmod n$ $\endgroup$
    – kelalaka
    Dec 1, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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