RSA linearity of messages

cryptographymodular arithmeticnumber theory

Suppose there are two ciphertexts $c_1$, $c_2$, encrypted with a Public RSA Key ($N,e$). Furthermore we can write $m_1$ = $m_2 + a$, where a is a known public parameter. How is it possible to recover $m_1$ without knowledge about the private key?

Best Answer

This 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, the former is problematic and OAEP is preferred when one needs encryption with RSA. Actually, we don't use RSA for encryption. We prefer it in digital signatures and that requires PSS padding.