2
$\begingroup$

Suppose your RSA modulus is $55 = 5 * 11$ and your encryption exponent is $e = 3$.

Find the decryption modulus d.

I know $d = 40-13 = 27$

However, I get $1$.
$$40 = (P_1-1)(P_2-1)$$

extended euclidean algorithm:
$$40 = 3(13)+1 $$

$$1 = 40(1) + 3(-13)$$

From what I understand $d = 1$.
What am I doing wrong?
Thanks.

$\endgroup$
  • 1
    $\begingroup$ $d$ needs to satisfy $de \equiv 1 \pmod{40}$. So you need $d=-13$ or equivalently $d=27$. $\endgroup$ – Nate Eldredge Apr 29 '14 at 0:11
  • $\begingroup$ Nate, you have answered it; then why call it a comment; post it as an answer and settle this question. $\endgroup$ – P Vanchinathan Apr 29 '14 at 0:29
  • $\begingroup$ Im still not following. Did you solve it by. d(3) ≡ 1(mod 40) ? $\endgroup$ – Armin Apr 29 '14 at 0:30
2
$\begingroup$

The extended Euclidean algorithm computation looks fine. You're just looking at the wrong number in it.

Remember, the goal is to find $d$ which is the multiplicative inverse of $e$ mod $(p_1-1)(p_2-1)$, or in other words $de \equiv 1 \pmod{(p_1-1)(p_2-1)}$. You have shown $1 = 40 \cdot 1 -13e$. If you read this equation mod 40, it says $1 \equiv -13e \pmod{40}$. So $d=-13$ achieves what we want. Of course, if you want a "positive" answer, note that $-13 \equiv 27 \pmod{40}$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Just a short note: If the goal is to find a decrpytion exponent for $n=55, e=3$, then $d=27$ is not the solution, $d=7$ or $d=47$ or more generally $d = 7 + k\lambda(55) = 7 + 20k$ will work too. $\endgroup$ – gammatester Apr 29 '14 at 7:59
  • $\begingroup$ Got it! Thanks. Made it way to complex in my head. $\endgroup$ – Armin Apr 29 '14 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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