Encrypt the letter J in ASCII (decimal) with public key RSA (n=147, e=7), then compute the private key and decrypt the result confirming that the message has been sent.
First part
J = 74 (ASCII), $n = 147$, $e = 7$ then $y=x^e (mod 147)$. Thus and cipher message is $$74^7 (mod 147) = 74^{2 + 2 +2+1} (mod 147) = 74^2*74^2*74^2*74 (mod 147) = 37*37 *37*74 (mod 147)$$ $$= 1369*2738 (mod 147) = 46*92 (mod 147) = 4232 (mod 147) = 116 $$
116 = t.
OK?
Second part
I got $t$, so $t = 116$, and $x= y^d$ $(mod$ $n)$ and $n= 147 = 7^2*3$.
I need to find $d$ such that $e*d = 1$ $(mod$ $\phi(n))$ where $\phi(n) = (7^2 - 7^1)(3^1 - 3^0) = ( 49 - 7)(3 - 1) = 84$. But this is wrong because $gcd (84,7) = 7 \ne 1$.
Shouldn't we have $n= p*q$ where $p$ and $q$ are primes?
In this case we have 49*3,where only 3 is prime, if both were prime the formula $(49 - 1)(3 - 1) = 48*2= 96$ would work, because $gcd (96, 7) = 1 $ and $d = 55$, but $116^{55}$ $(mod$ $147)= 116 = t$.
I know the problem isn't quite mathematical but I'm lost here and any help is welcome.
Thanks in advance.