1
$\begingroup$

I'm trying to calculate $d$. I have the following parameters given:

$p = 239$

$q = 181$

$n = p \times q = 43259$

$\phi(n) = (p - 1) \times (q - 1) = 42840$

$e = 11$

For calculating $d$ I use the Euclidean Algorithm:

$a = qb + r$

$42840 = 3894 \times 11 + 6$

$11 = 1 \times 6 + 5$

$6 = 1 \times 5 + 1$

$5 = 5 \times 1 + 0$

This leads me to this table here:

\begin{array}{|r|r|r|r|} \hline a & b & q & r & x & y \\ \hline 42840 & 11 & 3894 & 6 & 2 & -7789 \\ \hline 11 & 6 & 1 & 5 & -1 & 2 \\ \hline 6 & 5 & 1 & 1 & 1 & -1 \\ \hline 5 & 1 & 5 & 0 & 0 & 1 \\ \hline \end{array}

When I check this solution, everything is fine:

$1 = 42840 \times 2 + 11 \times (-7789)$

but my $d$ should be $35051$, because I need $e \times d = 1 \bmod 42840$.

We can check this via encryption and decryption as well. Let's say I encrypt the number $6$:

$E(M) = M^e \bmod n = 6^{11} \bmod 43259 = 27082$

The decryption works fine for $d=35051$

$D(C) = C^d \bmod n = 27082^{35051} \bmod 43259 = 6$

But it's wrong for $-7789$.

So, what did I do wrong to calculate $d$? Can you provide a full path to $d$?

Improve this question
$\endgroup$
  • $\begingroup$ The full Euclidean algorithm is overkill and error prone due to sign issues. See the 10-step method starting "the half-extended Euclidean algorithm can be used to efficiently compute $a^{-1}\bmod b$ .." here, which uses only non-negative integers. Independently: computations are slightly easier ($d$ is often smaller) if you use $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ rather than $\varphi(n)$, and that's mandated by official standard FIPS 186-4. $\endgroup$ – fgrieu♦ Sep 22 '19 at 6:29
  • $\begingroup$ Hi, Thanks for this link. Really interesting, I really appreciate this :) $\endgroup$ – Shibumi Sep 22 '19 at 14:06
2
$\begingroup$

I think you will find that $42840 - 7789 = 35051$.

Improve this answer
$\endgroup$
  • $\begingroup$ oh, why do I need to calculate 42840 - 7789? I always thought that y would be already the solution. Do you have any explanation for this? $\endgroup$ – Shibumi Sep 22 '19 at 2:19
  • $\begingroup$ RSA calculations are using unsigned integers, basically you're operating in the group defined by the modulus. So -7789 is identical to 35051 within the calculations - if you allow it to exist at all. $\endgroup$ – Maarten Bodewes♦ Sep 22 '19 at 2:24
  • $\begingroup$ ok, but why not using + instead of -? I understand that I need to operate in unsigned integers, but I don't understand why I need to subtract y from phi. $\endgroup$ – Shibumi Sep 22 '19 at 2:27
  • $\begingroup$ The point is that $35051 \equiv -7789 \pmod{42840}$, meaning $35051 = -7789 + 42840 k$ for some integer $k$. In this case, $k = 1$. What it means is that the euclidean algorithm gave you an equivalent representative of the remainder. $\endgroup$ – Squeamish Ossifrage Sep 22 '19 at 2:56
  • $\begingroup$ Thank you for the nice explanation. It's clear now :) $\endgroup$ – Shibumi Sep 22 '19 at 14:06

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.