CODEWITHSUNDEEP
mathencryptionrsapublic-keysecret-key
Chris
Chris

Reputation: 40641

For RSA, how do i calculate the secret exponent?

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

Upvotes: 15

Views: 25932

Answers (1)

Jim Lewis
Jim Lewis

Reputation: 45115

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.

Upvotes: 19

Related Questions