RSA Encryption in php

ok im trying to create some php functions to do rsa encryption / decription. not on the same page of course.

i got the encryption done like this.

[CODE]function rsaEncrypt($M, $N, $e){
$Me = bcpow($M, $e);
$C = bcmod($Me, $N);
return $C;
}[/CODE]

where $M is the message, $N is the public key (worked out by p*q (p and q are prime numbers)) and $e is a relitive prime to (p-1)(q-1) (Ie. p-1*q-1)

so if we take p as 5 and q as 7 then we get a public key (N) of 35.

a relitive prime of (5-1)(7-1) = 4*6 = 24 is 3 so there we have a value for e.

we shal take a message (M) of 123 for now.

so Me = M^{^e} (Me = M to the power of e)
Me = 123^{^3} = 1860867.

and therefor C = 35(mod 1860867) = 22

so our encrypted number is 22 from the original one of 123.

equations are:
N = pq
e = φ(p-1)(q-1)

φ means relitive prime i think. but anyway thats what im using it for here. lol.

now ive done the explaining of where i think i am up to time for the problem. if i have got that wrong please someone tell me and point me in the right direction.

i have the encrypted number but i dont understand how to decrypt it.

the equations are:
ed = 1(mod (p-1)(q-1))

so therefor it would be something like
3d = 1(mod(4*6))
3d = 1(mod 24)
and this is where i get stuck how do i get “d” and how do i do “1(mod 24)”

to my understanding 1(mod 24) would be done by

[CODE]$ans = bcmod(1,24);[/CODE]

but this returns 1.

does anyone know what im doing wrong and please could you tell me where or point me in the right direction.

ps. i have already looked at these sites.
[URL=”http://mathcircle.berkeley.edu/BMC3/rsa/node4.html”]http://mathcircle.berkeley.edu/BMC3/rsa/node4.html[/URL]
[URL=”http://en.wikipedia.org/wiki/Rsa”]http://en.wikipedia.org/wiki/Rsa[/URL]
and a few others that i forget right now.

Also in #PHP _↴