0
$\begingroup$

To decrypt some M, we use the fact that M $\equiv$ $(M')^d$ mod n. To find d, I did $e^{\Phi((p-1)(q-1))}$ mod ((p-1)(q-1)).

In my particular case, n = 1643, e = 223, p = 31, q = 53. Therefore, d $\equiv$ $223^{\Phi((30)(52))}$ mod 1560 $\equiv$ $223^{384}$ mod 1560.

I am getting 1 for this last step, which does not seem to be right.

$\endgroup$
7
  • $\begingroup$ Just edited my question with more detail. $\endgroup$
    – Payal Ahuja
    Apr 11, 2017 at 5:41
  • 3
    $\begingroup$ $\Phi = (p-1)(q-1)$ and $d = e^{-1} \pmod{\Phi} = 223^{-1} \pmod{1560} = 7$. $\endgroup$
    – Moo
    Apr 11, 2017 at 5:49
  • $\begingroup$ Just to clarify, it's not $\Phi((p-1)(q-1))$, but just $223^{1560}$? $\endgroup$
    – Payal Ahuja
    Apr 11, 2017 at 5:53
  • $\begingroup$ See the details in the comment I added above for calculating $d$, we have that $ed \equiv 1 \pmod{\Phi} \implies d \equiv e^{-1} \pmod{\Phi} \equiv e^{-1} \pmod{(p-1)(q-1)}$. Of course, we are also talking about modular inverses here. $\endgroup$
    – Moo
    Apr 11, 2017 at 5:54
  • 2
    $\begingroup$ $e^{-1} \equiv e^{\phi(pq)-1}\pmod{pq}$. The $-1$ on the right-hand side is important, and indeed without it, you will always erroneously get $1$ by Euler's theorem. $\endgroup$
    – Greg Martin
    Apr 11, 2017 at 6:00

2 Answers 2

Reset to default
2
$\begingroup$

Your decryption key should be 7

$d = e^{-1}(mod1560)$

$d = 223^{-1}(mod1560)$

Extended Euclidean Algorithm

$1560 = 223 * 6 + 222$

$223 = 222 * 1 + 1$

$222 = 1 * 222 + 0$

Go backward

$1 = 223 - 1*222$

$1 = 223 - 1 (1560 - 6*223)$

$1 = 7*223 - 1 *1560$

$1 = 7*223(mod1560)$

Therefore d=7

To check:

$ed \equiv 1 (mod1560)$

$223*7 \equiv 1 (mod1560)$

$1561 \equiv 1(mod1560)$

$\endgroup$
0
$\begingroup$

You have the wrong way to compute the decryption key. If $n=pq$, then public key $(n,e)$ has the private decryption key $d$ where $ed \equiv 1 \pmod{\phi(n)}$, not $e^{\phi(\phi(n))} \pmod {\phi(n)}$, as you think.

As here $\phi(n) = (p-1)(q-1) =1560$ you need to find the inverse of $223$ modulo $1560$. This is indeed $7$ as $7 \times 223 = 1561$ and can be found using the extended Euclidean algorithm.

$\endgroup$

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.