Re: RSA decryption exponent d (c++)

TJakobsen <TJakobsenDK@gmail.com> wrote:
>According to various
>sources i've used, d is calculated like this:
>
>d = e^-1 (mod phi(n))
>
>Anyway can anyone explain to me how i calculate d using c++ code or
>just in plain easy-to-understand mathematics?

Your equation says that d should be an inverse of e modulo phi(n).

First, you need to understand what an inverse is. This is easy: a is
an inverse of b modulo n iff a times b is congruent to 1 modulo n.
For example: 3 is an inverse of 7 modulo 20 because

        3*7 = 21 = 1 (mod 20).

Second, you need to understand how to calculate an inverse of a
number modulo a modulus. The hint is to use the extended Euclidian
algorithm. The basic idea is: You want to find an inverse of the
number x modulo a modulus n. If you can find integer solutions s
and t to the equation

        sx + tn = 1

then it is easy to show that s is an inverse of x modulo n.

-- 
Kristian Gjøsteen