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?

$\endgroup$
  • $\begingroup$ By the way, is this a homework exercise? $\endgroup$ – kelalaka Jan 8 at 19:01
  • $\begingroup$ Do the two occurences of $c_1$ and $c_2$ respectively refer to the same number? $\endgroup$ – Maeher Jan 9 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$ – fgrieu Jan 9 at 17:25
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$
  • $\begingroup$ As our current policy of the HW questions, I'll delete this answer when the question is closed. $\endgroup$ – kelalaka Jan 8 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$ – SJ19 Jan 8 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$ – SAI Peregrinus Jan 9 at 0:33
  • $\begingroup$ Thank you so much @SAIPeregrinus. You saved me a lot of headaches. $\endgroup$ – SJ19 Jan 17 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$ – SJ19 Jan 17 at 11:48

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.