2
$\begingroup$

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$

  • 2
    Then $d=13$, because $5d \equiv 1\pmod{32}$?2012-10-16

2 Answers 2

3

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.

1

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.