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

[KMatle]

As some of you maybe have read, I am going to develop a RSA (lib) for B4x and (more important) a php script. This would be a great step for b4x because we then are able to exchange keys SAFE.

Agrahams lib supports RSA but it is very difficult to match it to the server-side (different reasons like: SSL has to be buyed from your hoster, many functions like OpenSSL or other RSA solutions can't be used, etc.)

I'm almost there, except my ability to get this into code (I did not find good sources).

See this thread: http://crypto.stackexchange.com/que...en-given-public-exponent-and-the-modulus-fact

Anyone?

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.