# Calculate d for RSA

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

• 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.
– fgrieu
Sep 22 '19 at 6:29
• Hi, Thanks for this link. Really interesting, I really appreciate this :) Sep 22 '19 at 14:06

I think you will find that $$42840 - 7789 = 35051$$.
• 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? Sep 22 '19 at 2:19
• 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. Sep 22 '19 at 2:56