math - For RSA, how do i calculate the secret exponent?

Question

For RSA, how do i calculate the secret exponent?

Given p and q the two primes, and phi=(p-1)(q-1), and the public exponent (0x10001), how do i get the secret exponent 'd' ?

I've read that i have to do: d = e^-1 mod phi using modular inversion and the euclidean equation but i cannot understand how the above formula maps to either the a^-1 ≡ x mod m formula on the modular inversion wiki page, or how it maps to the euclidean GCD equation.

Can someone help please, cheers

Answer 1

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 (a^e)^d = a^de mod m. But since de = 1 mod phi(m), Euler's totient theorem tells us that a^de is congruent to a¹ 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.