# Re: RSA decryption exponent d (c++)

*From*: "bert" <bert.hutchings@xxxxxxxxxxxxxx>*Date*: 31 Mar 2006 00:33:39 -0800

TJakobsen wrote:

I have used the following numbers:and

p = 37

q = 89

n = p*q = 37*89 = 3293

phi(n) = (p-1)(q-1) =3168

e = 25

hehe sorry but i dont really understand how to use this in my program

as im only a high school student (last year though). We don't have

advanced mathematics yet and we haven't really worked with any of the

mathematics related to RSA such as modulo etc.

could someone be so kind as to go through this Extended Euclidian

algorithn using the numbers i've used in my program please?

so we can calculate d.

3168 / 25 = 126 remainder 18

25 / 18 = 1 remainder 7

18 / 7 = 2 remainder 4

7 / 4 = 1 remainder 3

4 / 3 = 1 remainder 1

Now build up the inverse from (126, 1, 2, 1, 1) like this:

a0 = 0, a1 = 1, a2 = 126 * a1 + a0, a3 = 1 * a2 + a1,

a4 = 2 * a3 + a2, . . .

a0 = 1, a1 = 1, a2 = 126, a3 = 127, a4 = 380, a4 = 507,

a5 = 887. See how, for each n, 25 * a_n mod 3168 is

related to the remainders in the first sequence. To get

the correct inverse in this case we have to go back to

the division sequence and add "3 / 1 = 2 remainder 1"

to get a6 = 2281, which is the required d.

--

.

**References**:**RSA decryption exponent d (c++)***From:*TJakobsen

**Re: RSA decryption exponent d (c++)***From:*Kristian Gjøsteen

**Re: RSA decryption exponent d (c++)***From:*TJakobsen

- Prev by Date:
**Re: RSA decryption exponent d (c++)** - Next by Date:
**Re: RSA decryption exponent d (c++)** - Previous by thread:
**Re: RSA decryption exponent d (c++)** - Next by thread:
**Re: RSA decryption exponent d (c++)** - Index(es):