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?
$\begingroup$
$\endgroup$
9
-
1$\begingroup$ Is it Textbook RSA? does the attacker know there is a relation? $\endgroup$– kelalakaCommented Nov 30, 2019 at 5:32
-
$\begingroup$ Yes it is. And yes the attacker knows this relation. $\endgroup$– PitsiCommented Nov 30, 2019 at 5:37
-
$\begingroup$ No the adversary does not know that. No other information for p. $\endgroup$– PitsiCommented 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 ♦Commented Nov 30, 2019 at 9:54
-
$\begingroup$ Is $m$ being a multiple of $p$ the only possible relation? $\endgroup$– SEJPMCommented Nov 30, 2019 at 12:39
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
6
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.
-
$\begingroup$ Yes it is $e$. Yes $y$ was better if we assume that $y=(mp)^e \bmod n$ $\endgroup$– kelalakaCommented 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$– PitsiCommented 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 ♦Commented 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$– PitsiCommented 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 ♦Commented Dec 2, 2019 at 9:54