Homomorphic RSA [closed]

Question

Anyone know how can I perform this ? $$E(x_1)*E(x_2)=E(x_1*x_2)$$ I have already produced the keys and I can encrypt and decrypt using RSA. My goal is to multiply 2 encrypted integers in order to decrypt them and show how homomorphism works. I cant find the product of the two encrypted integers because i am not sure how to multiple( byte by byte or whole integers)? If any

Answer 1

With textbook RSA encryption defined as $E(x)=(x^e\bmod N)$ and decryption $D(y)=(y^d\bmod N)$, restricting to $0\le x_1<\sqrt N$ and $0\le x_2<\sqrt N$, we have$$E(x_1*x_2)=((E(x_1)*E(x_2))\bmod N)$$which let one compute $E(x_1*x_2)$ from $E(x_1)$ and $E(x_2)$; and $D(E(x_1*x_2))=x_1*x_2$, thus the enciphered product can be deciphered.

Note: in the above, all quantities are integers, $*$ is is integer multiplication, and $\bmod$ is modular reduction (similar to the % operator of C and Java), applied to large integers. $x^k\bmod N$ is equivalent to $1$ multiplied $k$ times by $x$ then reduced modulo $N$, but is to be computed with some efficient modular exponentiation method. The code implementing this multiplication, modular reduction, and modular exponentiation must be consistent with whatever representation of integers as bytes is used; no "byte by byte" multiplication has such consistency.

Problems are: textbook RSA encryption is not safe by modern cryptographic standards (in particular, any guess of $x$ can be checked by one knowing $x^e\bmod N$); and variants of textbook RSA safe against this are not homomorphisms (they are not even functions).