Is there a way to modify the RSA so that it's homomorphically additive?

I did some research and came across a paper which describes MREA (Modified RSA Encryption Algorithm), an RSA modification that, supposedly, is homomorphically additive.

The authors define the encryption algorithm as follows: $$E(message) = g^{message^e \bmod {n}} \cdot r^{m} \bmod m^{2}$$

$$e$$ and $$n$$ have the same meaning like in RSA.
$$m = r \cdot s$$.
$$r$$ and $$s$$ are randomly generated large prime numbers.
$$g = m + 1$$.

I tried proving that $$E(message_{1} + message_{2}) \equiv E(message_{1}) \cdot E(message_{2})$$.

Here's my attempt: $$E(message_{1}) \cdot E(message_{2}) = g^{(message_{1} + message_{2})^e \bmod {n}} \cdot r^{\textbf{2}m} \bmod m^{2}$$ $$\neq$$ $$g^{(message_{1} + message_{2})^e \bmod {n}} \cdot r^{m} \bmod m^{2} = E(message_{1} + message_{2})$$

I do believe that I made a mistake somewhere but I fail to spot it.

Does anyone see where I messed up?

• Whoever may suggest one reads this paper as part of instruction on cryptography (rather than on the pitfalls of the academic publishing system) is incompetent or/and ill-intentioned. Read this instead.
– fgrieu
Apr 30, 2022 at 17:51
• No one suggested I read that paper. I was just researching a way to modify RSA to obtain the mentioned property. Thanks for the suggested paper, but it's not quite what I'm looking for. May 2, 2022 at 16:34

I tried proving that $$E(message_{1} + message_{2}) \equiv E(message_{1}) \cdot E(message_{2})$$.

Does anyone see where I messed up?

It is appeared you messed up when you tried to take this paper seriously.

This system glues together the Paillier cryptosystem with textbook RSA; Paillier and textbook RSA both have homomorphic properties, however they don't combine properly. For Paillier, multiplying two ciphertexts effectively adds the plaintexts; however adding two textbook RSA ciphertexts doesn't do anything (you need to multiple the RSA ciphertexts to homomorphically multiply the plaintexts).

If you need an additively homomorphic system, just use straight Paillier.

• From the security analysis section, they claim "If RSA which is based on single modulus, is broken in time $$x$$ and additive homomorphic based on dual modulus, is broken in time $$y$$ then the time required to break MREA algorithm is $$x \cdot y$$". It should be obvious that, because the public key contains both the RSA and the Paillier public key, it would suffice to break both individually, and so the security is no better than $$x + y$$. If both problems are about the same amount of difficulty, you end up doubling the amount of work the attacker needs to do, at the cost of increasing the encryptor/decryptor by a factor of 6 - not a great trade-off.