Is this RSA problem solvable?

Question

A secret message M has been encrypted using the RSA algorithm producing the cyphertext C=12. The public key for the RSA algorithm is e=3, n=51. Compute the decryption component d and hence decipher the message to find M.

So my problem is if Ed=1 (mod n), but e=3 And 3 is a factor of 51 so it can't ever have remained 1? Thanks for any help

Answer 1

An RSA public key pair $(n,e)$ must satisfy the condition

$$\gcd(e,\varphi(n))=1$$

Here, $\varphi(n)=(17-1)(3-1)=32$. And $\gcd(3,32)=1$. So this is a valid public key.

Your mistake is when you say that $ed\equiv 1$ mod $n$. This should be $ed\equiv 1$ mod $\varphi(n)$.

Answer 2

Well, an RSA encryption can be broken if the modulus (product of two primes) $n$ can be factored. Here its simple $n=3\cdot 17$. Then from the public key pair $(e,n)$ one can determine the secret key $d$ by the extended Euclidean algorithm, as stated by TonyK.