# Using the RSA system…

Using the RSA system with $(m,e)=(51,5)$ find a $d\ge1$ that will decode the messages.

What I have so far (not sure if this is right):

Since, $m=51$ and $e=5$ then the $\gcd(51,5)=1$ then: $$5d \equiv 1\pmod{51}$$ $$5d\equiv 55\pmod{51}$$ $$d=11$$

-
If I remember RSA correctly, what you want is not $de\equiv 1\bmod m$, but $de\equiv 1\bmod \varphi(m)$ where $\varphi$ is the totient function. It is $\varphi(m)$ that is hard to compute for large $m$. –  Henning Makholm Oct 16 '12 at 20:09
Then $d=13$, because $5d \equiv 1\pmod{32}$? –  student.llama Oct 16 '12 at 20:14

For starters: it is more common to call the public key $(n, e)$ rather than $(m, e)$, since $m$ is often used for the message to be encrypted rather than for the product of the primes $p$ and $q$.

Either way, $d \equiv e^{-1} \pmod{\varphi({n})}$, which means that $d \cdot e \equiv 1 \pmod{\varphi({n})}$.

We see that $\varphi({n}) = 32$, so we are left to solve $5 \cdot d \equiv 1 \pmod{32}$, which would mean that $d = 13$ (solvable using Euclid's extended gcd algorithm).

When using RSA in practise, n would be sufficiently large, making $\varphi({n})$ infeasible to compute.

-

You can check this. "Randomly choose" the message be $15$. Then the encrypted message is $15^5 \pmod {51}=36$. If you are right, $36^{13} \pmod {51}$ should equal $15$, which it does.

-