RSA Multiplicative Homomorphism
Multiply two ciphertexts, decrypt once — and get the product of the original plaintexts. No plaintext ever required on the server.
Educational example — does not provide actual cryptographic protection — Bastiaan Quast
Choose two primes
n = P · Q
14
φ(n)
6
modulus n²
196
Derived key pair
e is chosen as the smallest odd integer coprime to φ(n). d is its modular inverse.
e — public exponent
5
gcd(e, φ) = 1 ✓
d — private exponent
5
e · d mod φ = 1 ✓
encryption / decryption
encrypt: c = me mod n² · decrypt: m = cd mod n
plaintext product m₁ · m₂ mod n
12
This is the target value. Decrypting the cipher product must yield this.
Encrypt m₁
c₁
47
3⁵ mod 196
decrypt(c₁)
3
47⁵ mod 14
Encrypt m₂
c₂
44
4⁵ mod 196
decrypt(c₂)
4
44⁵ mod 14
Cipher product (no decryption needed yet)
c₁ · c₂ mod n²
108
47 · 44 mod 196
decrypt
12
108⁵ mod 14
RSA is multiplicatively homomorphic: a party can multiply two ciphertexts and — upon decryption — recover the product of the original plaintexts. Neither plaintext m₁ nor m₂ was ever revealed. The use of n² as the encryption modulus (rather than n) is what gives the cipher product enough headroom to survive decryption correctly.