RSA with $p = 23$, $q = 41$, $e = 9$, $d = 489$. Show that $e$ is a legitimate public exponent and that $d$ matches it. Alice sends the ciphertext $c = 492$; how does Eve change it so that Bob decrypts $5 \cdot m$?

Question

Accepted Answer

$\varphi(N) = 880$ and $\gcd(9, 880) = 1$, so $e$ is valid; $9 \cdot 489 = 4401 \equiv 1 \pmod{880}$, so $d$ fits. Eve sends $c' \equiv 5^{9} \cdot 492 \equiv 697 \pmod{943}$.
1. Is $e = 9$ legitimate? $N = 943$ and $\varphi(N) = 22 \cdot 40 = 880 = 2^4 \cdot 5 \cdot 11$. Since $9 = 3^2$ and 3 does not divide 880, $\gcd(9, 880) = 1$. Without a calculator: $880 / 3 = 293.3\ldots$ is not an integer.
2. Does $d$ match? $e \cdot d = 9 \cdot 489 = 4401 = 5 \cdot 880 + 1 \equiv 1 \pmod{880}$. Yes.
3. Eve's manipulation (homomorphic property): she encrypts the factor 5 with the public key and multiplies:
$$c' \equiv 5^{e} \cdot c = 5^{9} \cdot 492 \equiv 172 \cdot 492 \equiv 697 \pmod{943}$$
Bob decrypts $c'^{\,d} = (5^{e} c)^{d} = 5^{ed} \cdot c^{d} \equiv 5 \cdot m$. Here $m = 123$, so Bob reads $615$.
Why it works: textbook RSA is multiplicatively homomorphic, $E(a) \cdot E(b) = E(a \cdot b)$. Eve needs neither $d$ nor $m$. RSA encryption alone gives no integrity; padding (OAEP) destroys this structure.