What are the three multiplicative properties of RSA, and how are they exploited both positively and negatively?
RSA has three forms of multiplicative homomorphism: product of ciphertexts, additive exponent splitting, and multiplicative exponent splitting. Each enables both attacks and useful applications.
* The same homomorphism enables both malicious malleability and useful blind/double signatures — and OAEP padding removes all three at once. *
Property 1 — Product of ciphertexts: $$(a \cdot b)^e \mod N = (a^e \cdot b^e) \mod N$$
- Attack: Multiply ciphertext by $2^e$ → plaintext is doubled (no integrity)
- Application: Create blind signatures (multiply message by $r^e$ before signing)
Property 2 — Additive exponent splitting: $$s \equiv m^d \mod N \equiv m^{d_1+d_2} \mod N \equiv (m^{d_1} \cdot m^{d_2}) \mod N$$
- Application: Double signatures with independent partial signatures
- Each party signs the message directly: $s_1 = m^{d_1}$, $s_2 = m^{d_2}$, combine: $s = s_1 \cdot s_2$
Property 3 — Multiplicative exponent splitting: $$s \equiv m^d \mod N \equiv m^{d_1 \cdot d_2} \mod N \equiv (m^{d_1})^{d_2} \mod N$$
- Application: Double signatures with sequential signing
- Party 1 signs: $s_1 = m^{d_1}$. Party 2 signs Party 1's output: $s = s_1^{d_2}$
- Constraint: $\gcd(d_1, \varphi(N)) = 1$ required (not arbitrary!)
OAEP padding destroys ALL three properties — which is both good (prevents attacks) and bad (prevents blind/double signatures). This trade-off is fundamental to RSA system design.
Go deeper:
Malleability (cryptography) — the homomorphism as a weakness: turning $E(m)$ into $E(mt)$ without the key.- OAEP — the padding that removes all three properties (and with them, malleability and blind/double signatures).