RSA: Find "d" - how to code this? (-> extended Euclidean algorithm)

The extended Euclidean algorithm is essentially the Euclidean algorithm (for GCD's) ran backwards.

Your goal is to find d such that ed≡1(modφ(n)).

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


ex+φ(n)y=1


Take this modulo φ(n), and you get:


ex≡1(modφ(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 φ(n) regardless of its value. The EED will give you that value, but you can safely discard it.

Now, we have e=17 and φ(n)=40. Write our main equation:


17x+40y=1


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


40=2×17+6



17=2×6+5



6=1×5+1


Write that last one as:


6−1×5=1


Now substitute the second equation into 5:


6−1×(17−2×6)=1


Now substitute the first equation into 6:


(40−2×17)−1×(17−2×(40−2×17))=1


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


(−7)×17+3×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.

Click to expand...