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$
3
  • $\begingroup$ By the way, is this a homework exercise? $\endgroup$
    – kelalaka
    Jan 8, 2020 at 19:01
  • $\begingroup$ Do the two occurences of $c_1$ and $c_2$ respectively refer to the same number? $\endgroup$
    – Maeher
    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$
    – fgrieu
    Jan 9, 2020 at 17:25

1 Answer 1

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.

$\endgroup$
6
  • $\begingroup$ As our current policy of the HW questions, I'll delete this answer when the question is closed. $\endgroup$
    – kelalaka
    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$
    – SJ19
    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$ Jan 9, 2020 at 0:33
  • $\begingroup$ Thank you so much @SAIPeregrinus. You saved me a lot of headaches. $\endgroup$
    – SJ19
    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$
    – SJ19
    Jan 17, 2020 at 11:48

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.