Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

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

1 Answer

up vote 10 down vote accepted

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.

share|improve this answer
    
Wow, that explains it perfectly. Thanks a lot! –  DougalMaguire Jan 3 '13 at 14:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.