# 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 private key d.

I can calculate phi(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.

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?

Any help is much appreciated!

-
Unfortunately it has to be computed by hand... I've edited the question to included more of my work. –  DougalMaguire Jan 3 at 13:32

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.

-
Wow, that explains it perfectly. Thanks a lot! –  DougalMaguire Jan 3 at 14:54