RSA linearity of messages

Question

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?

Answer 1

This is first studied when $e=3$

• Low-Exponent RSA with Related Messages by Don Coppersmith, Matthew Franklin, Jacques Patarin, Michael Reitert, EUROCRYPT 1996: Advances in Cryptology — EUROCRYPT ’96 pp 1-9

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

• A New Related Message Attack on RSA Oded Yacobi and Yacov Yacobi, PKC 2005: Public Key Cryptography - PKC 2005 pp 1-8.

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.