# Find private exponent in RSA [duplicate]

The other answers for this confuse me, I know the principle of d in terms of the equation it has to satisfy. However I'm not sure how I would go about finding the private exponent without trial and error. I want to implement this in a program, but I'm not quite sure the algorithm I would use to find d. Can someone explain the equation or algorithm for finding d?

## marked as duplicate by Ilmari Karonen, yyyyyyy, otus, SEJPM♦, e-sushiJan 11 '16 at 2:59

• Do you know the prime factors of the modulus? – CodesInChaos Dec 21 '14 at 16:54
• Yes, I am finding the private key, I have all the information needed. – Mac Dec 21 '14 at 17:29
• If you think the above does not answer your question, please edit your question to detail why. – otus Jan 10 '16 at 12:49

If you know the prime factors (p,q) of the modulus, then it would be easy to find the private exponent. You'll proceed as follow:

• Compute the Carmichael function $\lambda(n)=\operatorname{lcm}(p-1,q-1)=\frac{(p-1)\times(q-1)}{\operatorname{gcd}(p-1,q-1)}$
• Choose a number e such that $\operatorname{gcd}(e,\lambda(n))=1$,
• Apply the Extended Euclid Algorithm to compute the inverse of $d=\frac{1}{e}\bmod\lambda(n)$, Cf Donald Knuth:Semi-Numerical Algorithms II (or any other reference book),

Then the public Key is $(n, e)$, while the private Key is $(n,d)$. This correspond to the straightforward parameters of RSA Keys. You can also generate with a similar way, the parameters associated to the CRT algorithm with allow a substantial gain when executing Modular exponentiation with the private Key. If required I could depicted it.

• So to calculate d its just: (1/e)%ϕ(n) When I try that on an example I was working on e=7,ϕ(n)=20, I get d to be 0.14285714285714285 when I know d should be 3 as (7*3)%20=1 – Mac Dec 21 '14 at 19:47
• To make simple, e the public exponent is to be selected firt. Traditionnally the public exponent e is chosen to be relativelly small, less than Min{p,q}. In your exemple, I suppose you have chosen p=5 and q = 11, which gives a public modulus n=55. You have selected e=7 as a public exponent, If you remember Chinese Remainder Theorem Partial reduction e = 7 = 3 mod (p-1). You then observe that the solution e.d = 1 mod 20 is symetrical. You are free to choose a large exponent as the public exponent and the private exponent the smallest, but this is not the practical issue in RSA applications. – Robert NACIRI Dec 21 '14 at 22:26
• @Mac The $1/e$ means the multiplicative inverse of $e$ modulo $\phi(n)$ (i.e. in $\mathbb Z/_{\phi(n)\mathbb Z}$), not the inverse in $\mathbb{Q}$ (or $\mathbb{R}$ or your computer's floating point numbers). – Paŭlo Ebermann Dec 22 '14 at 10:23
• @Robert : $\;\;\;$ "Euler totient $\phi(n)$" $\: \mapsto \:$ "Carmichael function $\lambda(n)$" $\;\;\;\;\;\;\;$ – user991 Dec 22 '14 at 10:39
• @Mac What you missed is "use the extended euclidean algorithm to calculate the inverse". Check out wikipedia for this. – tylo Jan 21 '15 at 11:47