0
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Mac Dec 21 '14 at 19:47
  • 1
    $\begingroup$ 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. $\endgroup$ – Robert NACIRI Dec 21 '14 at 22:26
  • $\begingroup$ @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). $\endgroup$ – Paŭlo Ebermann Dec 22 '14 at 10:23
  • 4
    $\begingroup$ @Robert : $\;\;\;$ "Euler totient $\phi(n)$" $\: \mapsto \:$ "Carmichael function $\lambda(n)$" $\;\;\;\;\;\;\;$ $\endgroup$ – user991 Dec 22 '14 at 10:39
  • $\begingroup$ @Mac What you missed is "use the extended euclidean algorithm to calculate the inverse". Check out wikipedia for this. $\endgroup$ – tylo Jan 21 '15 at 11:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.