Calculating RSA private exponent when given public exponent and the modulus factors using extended euclid When given $p = 5, q = 11, N = 55$ and $e = 17$, I'm trying to compute the RSA private key $d$.

I can calculate $\varphi(N) = 40$, but my lecturer then says to use the extended Euclidean algorithm to compute $d$. That's where I get stuck.



Here's my work so far:

First I use the Euclid algorithm to calculate:

40 = 2(17) + 6 
17 = 2(6) + 5
6 = 1(5) + 1 = gcd


So I know the GCD is 1. Applying the 'extended' section of the algorithm:

6 = 40-2(17)
5 = 17-2(6)
1 = 6-1(5)
1 = 6-1(17-2(6))
3(6) = 1 (17)
3(40 - 2(17)) - 1(17)
3(40) - 3(17)


I know the answer is $33$, but I have no idea how to get there using the extended Euclidean algorithm. I can't figure out why I'm getting $3(40) - 3(17)$ when I know the answer should contain $33$.
The extended Euclidean algorithm is essentially the Euclidean algorithm (for GCD's) ran backwards.

Your goal is to find $d$ such that $ed \equiv 1 \pmod{\varphi{(n)}}$.

Recall the EED calculates $x$ and $y$ such that $ax + by = \gcd{(a, b)}$. Now let $a = e$, $b = \varphi{(n)}$, and thus $\gcd{(e, \varphi{(n)})} = 1$ by definition (they need to be coprime for the inverse to exist). Then you have:

$$ex + \varphi{(n)} y = 1$$

Take this modulo $\varphi{(n)}$, and you get:

$$ex \equiv 1 \pmod{\varphi{(n)}}$$

And it's easy to see that in this case, $x = d$. The value of $y$ does not actually matter, since it will get eliminated modulo $\varphi{(n)}$ regardless of its value. The EED will give you that value, but you can safely discard it.



Now, we have $e = 17$ and $\varphi{(n)} = 40$. Write our main equation:

$$17x + 40y = 1$$

We need to solve this for $x$. So apply the ordinary Euclidean algorithm:

$$40 = 2 \times 17 + 6$$

$$17 = 2 \times 6 + 5$$

$$6 = 1 \times 5 + 1$$

Write that last one as:

$$6 - 1 \times 5 = 1$$

Now substitute the second equation into $5$:

$$6 - 1 \times (17 - 2 \times 6) = 1$$

Now substitute the first equation into $6$:

$$(40 - 2 \times 17) - 1 \times (17 - 2 \times (40 - 2 \times 17)) = 1$$

Note this is a linear combination of $17$ and $40$, after simplifying you get:

$$ (-7) \times 17 + 3 \times 40 = 1$$

We conclude $d = -7$, which is in fact $33$ modulo $40$ (since $-7 + 40 = 33$).

As you can see, the basic idea is to use the successive remainders of the GCD calculation to substitute the initial integers back into the final equation (the one which equals $1$) which gives the desired linear combination.



As for your error, it seems you just made a calculation error here:

3(40 - 2(17)) - 1(17)

which incorrectly became:

3(40) - 3(17)

It seems you forgot the factor of 3 for the left 17, the correct result would be:

3(40 - 2(17)) - 1(17) = 3 * 40 - 3 * 2 * 17 - 1 * 17 = 3 * 40 + (-7) * 17

Which is the -7 expected.