Re: RSA decryption exponent d (c++)

TJakobsen wrote:
I have used the following numbers:
p = 37
q = 89
n = p*q = 37*89 = 3293
phi(n) = (p-1)(q-1) =3168
e = 25
and
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.
--

.

Relevant Pages

  • Re: RSA decryption exponent d (c++)
    ... hehe sorry but i dont really understand how to use this in my program ... as im only a high school student. ... advanced mathematics yet and we haven't really worked with any of the ... algorithn using the numbers i've used in my program please? ...
    (sci.crypt)
  • Re: RSA decryption exponent d (c++)
    ... as im only a high school student. ... advanced mathematics yet and we haven't really worked with any of the ... // then ss would be the inverse of ee modulo mm. ... --Mike Amling ...
    (sci.crypt)
  • Re: RSA decryption exponent d (c++)
    ... as im only a high school student. ... advanced mathematics yet and we haven't really worked with any of the ... algorithn using the numbers i've used in my program please? ... for i:= 1 to PhiN-1 do ...
    (sci.crypt)