Re: RSA decryption exponent d (c++)

Timo Johansson <johansson@despammed.com> writes:

>Hello,

>TJakobsen wrote:
>>d is calculated like this:
>>
>> d = e^-1 (mod phi(n))

>d = e^{-1} = e^{phi(n)-1} (mod phi(n))

>since phi(n) = 0 (mod phi(n))

>> 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

>So, maybe it's more simple for you to compute

>e^{phi(n)-1} = 25^3167

>The result is a quite huge number, but you can use modulo reduction after
>every multiplication:

>unsigned long int d,e;
>int i;

>e=25;
>d=25;
>for(i=0;i<3168-1;i++){
> d *= e;
> d %= 3168;
>}

3167=110001011111
e^3167= e*(e^2)(e^2^2)(e^2^2^2)(e^2^2^2^2)(e^2^2^2^2^2^2).....
(e^2^2=(e^2)^2
Ie, You can claculate the squares of e and its squares and then multiply
them together. This is only 12 squarings and 8 multiplication (modulo
reducing each one) (ie 20 multiplications and modulo reductions) rather
than 3167 of them.
z=e;
d=1;
p=3167;
for(i=1;i<=12;i++)
{
if((p%2) == 1) d=(d*z)%3167;
p/=2;
z=(z*z)%3167;
}

>although i'd prefer using the extended euclidean alg...!
>Remark, this is a quick shot and not tested, so I'm almost shure there are a
>few mistakes, but I guess you got the idea of what I mean...

Similarly.

>regards, Timo
Received on Mon May 1 01:54:17 2006