You can use the extended Euclidean algorithm to solve for d in the congruence
de = 1 mod phi(m)
For RSA encryption, e is the encryption key, d is the decryption key, and encryption
and decryption are both performed by exponentiation mod m. If you encrypt a message a
with key e, and then decrypt it using key d, you calculate (ae)d = ade mod m. But
since de = 1 mod phi(m), Euler's totient theorem tells us that ade is congruent
to a1 mod m -- in other words, you get back the original a.
There are no known efficient ways to obtain the decryption key d knowing only the
encryption key e and the modulus m, without knowing the factorization m = pq, so
RSA encryption is believed to be secure.
Jim Lewis
2010-07-09 04:19:24