Partial homomorphism in RSA
Let's take the RSA algorithm to explain this correspondence between ciphertext operations and plaintext operations (in this case, multiplication).
We know that RSA's encryption is as follows:
[M]^e ≡ c (mod N)
Here, we have the following:
- [
M
] is the message. - (
e
) is the public parameter of encryption. - (
N
) is the public key composed by[p*q]
. - (
c
) is the cryptogram.
Now, we are supposed to have two messages, [M1]
and [M2]
, and we encrypt them using the same public parameters (e
, N
) to generate two different cryptograms (c1
, c2
). The result of the encryption will be as follows:
c1 ≡ M1^e (mod N) c2 ≡ M2^e (mod N)
If we multiply the ciphers (c1*c2
), we get as a result a third cryptogram (c3
), such that the following applies:
c3 = c1 * c2 c3 ≡ M1^e (mod N) * M2^e (mod N) c3 ≡ M1^e * M2^e (mod N)
I have simply substituted the operations on encrypted messages [M1]
and...