1
$\begingroup$

I'm trying to solve an exercise where you have to compute two plaintexts $p_1$ and $p_2$, knowing the corresponding ciphertexts $c_1$ and $c_2$ and the public key, of which $e=3$, and $n$ is a large number. Also given is a relation between $p_1$ and $p_2$. $p_2 = c_1 \cdot p_1 + c_2$. Where $c_1$ and $c_2$ are constants.

I'm guessing I should use the fact that $e$ is a low number (3) since RSA is unsafe in this case. I'm not sure where to start, how should I go about solving this exercise?

Improve this question
$\endgroup$
3
  • $\begingroup$ By the way, is this a homework exercise? $\endgroup$ Commented Jan 8, 2020 at 19:01
  • $\begingroup$ Do the two occurences of $c_1$ and $c_2$ respectively refer to the same number? $\endgroup$ Commented Jan 9, 2020 at 9:50
  • $\begingroup$ The lack of safety of textbook RSA encryption with public exponent $e=3$ is due more to the lack of proper encryption padding than it is due to the low exponent. Independently, I guess that $p_2 = k_1 \cdot p_1 + k_2$ where $k_1$ and $k_2$ are given constants unrelated to given ciphertexts $c_1$ and $c_2$. $\endgroup$ Commented Jan 9, 2020 at 17:25

1 Answer 1

Reset to default
3
$\begingroup$

Since this is an exercise, I'll provide the links of the articles as a hint;

The linearity of the messages is first studied when $e=3$

A more general case, where $e$ is not limited to 3 and the relation is linear is studied in

It is quite clear that these attacks are related to textbook RSA and it must not be used in practice.

For encryption, RSA has used either PKCS#1.5 padding or OAEP. Actually, we don't use RSA for encryption. We prefer it in digital signatures and that requires PSS padding or for Key Encapsulation, RSA-KEM.

Improve this answer
$\endgroup$
6
  • $\begingroup$ As our current policy of the HW questions, I'll delete this answer when the question is closed. $\endgroup$ Commented Jan 8, 2020 at 18:58
  • $\begingroup$ Thanks for the hint, however the articles you provided are a bit overwhelming to me. It just confuses me more honestly. Could you give me a more concrete hint or example as to how to find the plaintext of a cipher text when e=3? Also, what's the point of the given relation between the two plaintexts? $\endgroup$ Commented Jan 8, 2020 at 21:46
  • 1
    $\begingroup$ Section 2 of the first paper, you want the formula just above the one labeled 1, and the first formula listed ($m2=\alpha m1+\beta$). $\endgroup$ Commented Jan 9, 2020 at 0:33
  • $\begingroup$ Thank you so much @SAIPeregrinus. You saved me a lot of headaches. $\endgroup$ Commented Jan 17, 2020 at 11:46
  • $\begingroup$ Also thanks @kelalaka (sorry for late reply), even though you could've just pointed me to the formula instead of having me waste time looking through papers I don't understand. :) $\endgroup$ Commented Jan 17, 2020 at 11:48

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.