Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$$

share|improve this question
2  
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
2  
Then $d=13$, because $5d \equiv 1\pmod{32}$? –  student.llama Oct 16 '12 at 20:14

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.