Prove that RSA is multiplicative in the sense that P A (M 1 ) P A (M

Question:

Prove that RSA is multiplicative in the sense that P_A(M₁) P_A(M₂) ≡ P_A(M₁M₂) (mod n).

Use this fact to prove that if an adversary had a procedure that could efficiently decrypt 1 percent of messages from ℤ_n encrypted with P_A, then he could employ a probabilistic algorithm to decrypt every message encrypted with P_A with high probability.

Fantastic news! We've Found the answer you've been seeking!