# In RSA, how to calculate the private exponent 'd', after choosing 'e'?

Seems there are 2 ways:

1. d = (ϕ(n)*k + 1) / e
In this case, need to choose a proper integer k.
Question 1: How to choose k, just try positive integers start from 1, until found one?
2. Use The Extended Euclidean algorithm, make d * e - k * ϕ(n) == 1, where k can be adjusted as need.
Seems need to add LCM(e, ϕ(n)) to d * e part, if d is negative ?

Question 2: Are the two ways identical, if not, which one is preferred? To me, seems way 1 is easier to calculate.

Question 3: Will there be multiple valid d, since both has a variablek? If yes, which one to use, the smallest or any one ?

Question 4: If possible, can u point out relevant file/functions in the source code of openssh.

## Example

input:
e = 3, p1 = 11, p2 = 17,
m = 123

encryption:
n = 11 * 17 = 187
c = 30

decryption:
ϕ = 10 * 16 = 160

3d - 160k = 1,          // e * d % ϕ(n) == 1
d = 107, k = 2,         // can be calculated via either way,

m = 123

public key:     n = 187, e = 3,
private key:    d = 107


I can calculate d in either way, and in both cases k = 2 is the first k met the requirement, I'm not sure is there more k that works.

There are several valid ways to choose $$d$$ after choosing $$e$$ in RSA.

All must insure that $$e\,d\equiv 1\bmod\lambda(n)$$, where $$\lambda$$ is the Carmichael function. That's the mathematically necessary and sufficient condition for $$d$$ to allow decryption as $$m\gets c^d\bmod n$$ of ciphertext $$c=m^e\bmod n$$ in textbook RSA†. Additionally, it's customary that $$0, because that's specified in PKCS#1. If $$n=p\,q$$ with $$p$$ and $$q$$ distinct primes as customary in RSA, then we can compute $$\lambda(n)$$ as $$\operatorname{lcm}(p-1,q-1)$$, or equivalently as $$(p-1)(q-1)/\gcd(p-1,q-1)$$.

Instead of $$e\,d\equiv 1\bmod\lambda(n)$$, we can use $$e\,d\equiv 1\bmod\varphi(n)$$, where $$\varphi$$ is Euler's totient. That's sufficient (though not necessary) for $$d$$ to allow decryption. Further, we can (and it used to be customary to) use $$d=e^{-1}\bmod\varphi(n)$$, which additionally implies $$0, and thus insures the customary $$0.

The question uses the later method, and asks how to calculate $$d=e^{-1}\bmod\varphi(n)$$; that is, by definition, the integer $$d\in\bigl[0,\varphi(n)\bigr)$$ with $$\varphi(n)$$ dividing $$e\,d-1$$.

The question's method 1 uses that there is a unique integer $$k\in[0,e)$$ with $$e\,d=k\,\varphi(n)+1$$. Thus a simple algorithm goes:

• $$v=1$$
• while $$e$$ does not divide $$v$$
• $$v\gets v+\varphi(n)$$
• output $$v/e$$

Problem with this is that the loop runs $$k$$ times, and that can be up to nearly $$e$$ times and in the the order of $$e/2$$ times on average. For very small $$e$$ (including up to say $$e=2^{(2^2)}+1=17$$) that's entirely fine. For the common $$e=2^{(2^4)}+1=65537$$, that's barely tolerable. If for some reason we use a very large $$e$$ (e.g. 60-bit or more), that's too much work.

The question's method 2 uses the (full) Extended Euclidean algorithm. This finds $$a$$ and $$b$$ such that $$a\,e+b\,\varphi(n)=1$$ in a systematic way. It follows that the desired $$d$$ is $$a\bmod\varphi(n)$$. The number of steps is $$\mathcal O(\log e)$$ rather than $$\mathcal O(e)$$, which makes the method practical whenever RSA itself is.

Since we do not need $$b$$, we can use a simplified version of the Extended Euclidean algorithm that maintain less variables, see this, or this for a minor variant that uses only only non-negative integers. There are yet other methods that avoid Euclidean division altogether, see this and it's references.

Are the two ways identical, if not, which one is preferred?

The methods 1 and 2 give the same result. Method 2 is preferable unless $$e$$ is very small. Also, method 2 detects an invalid $$e$$, that is one with $$\gcd\bigl(e,\varphi(n)\bigr)\ne1$$; when method 1 as written above loops forever (that's easily fixed by limiting to less than $$e$$ loops).

IMHO it's preferable to use one of the variant of method 2, and use that to compute $$d=e^{-1}\bmod\lambda(n)$$ rather than $$d=e^{-1}\bmod\varphi(n)$$. That's because the formual with $$\lambda(n)$$ yields the smallest valid non-negative $$d$$, which is

• mathematically pleasing
• required by some standards (e.g. FIPS 186-4)
• permitted by most others

Note: the use of $$\lambda(n)$$ often yields a smaller $$d$$, which then typically yields a faster computation of $$c^d\bmod n$$ when that's done directly. That argument is specious though, because the gain is typically tiny, and when performance matters, implementations do not use $$d$$ anyway; rather, they use $$d_p=e^{-1}\bmod(p-1)=d\bmod(p-1)$$ and $$d_q=e^{-1}\bmod(q-1)=d\bmod(q-1)$$ to compute $$c^{d_p}\bmod p$$ and $$c^{d_q}\bmod q$$, then combine these per the Chinese Remainder Theorem, and these $$d_q$$ and $$d_q$$ do not depend on how we choose $$d$$.

Will there be multiple valid $$d$$, since both has a variable $$k$$?

There are infinitely many $$d$$ with $$e\,d\equiv 1\bmod\varphi(n)$$, but methods 1 and 2 both yield the only one $$d$$ in the interval $$\bigl[0,\varphi(n)\bigr)$$.

Note: assuming $$p$$ and $$q$$ are odd, which is necessary for security, there are at least two $$d$$ in $$\bigl[0,\varphi(n)\bigr)$$ that are valid. If $$d$$ is one, then $$d-\varphi(n)/2$$ or $$d+\varphi(n)/2$$ is another. Again the smallest non-negative valid $$d$$ is $$e^{-1}\bmod\lambda(n)$$.

In the question's artificially small (thus totally insecure) example, $$e=3$$, $$p_1=11$$ (often named $$p$$), $$p_2=17$$ (often noted $$q$$). $$p_1$$ and $$p_2$$ are distinct odd primes, as they should. $$e=3$$ is coprime with $$p_1-1=10$$ and $$p_2-1=16$$, thus $$(e,p_1,p_2)$$ are a valid combination (note: since $$3$$ is prime, testing this reduces to checking that $$3$$ divides neither $$10$$ nor $$16$$). $$n=p_1\,p_2=187$$. $$\varphi(n)=(p_1-1)(p_2-1)=160$$. Computing $$d=e^{-1}\bmod\varphi(n)$$ by method $$1$$ goes:

• $$3$$ does not divide $$v=1$$, move to $$v=1+160=161$$
• $$3$$ does not divide $$v=161$$, move to $$v=161+160=321$$
• $$3$$ divides $$v=321$$, yielding $$d=321/3=107$$.

If we go for $$d=e^{-1}\bmod\lambda(n)$$: $$\lambda(n)=\varphi(n)/\gcd(p_1,p_2)=80$$, the same method yields $$d=81/3=27$$ on the second attempted division.

† For any plaintext $$m\in[0,n)$$, with the additional requirement $$\gcd(m,n)=1$$ when $$n$$ is divisible by the square of a prime. That later condition typically is forbidden in RSA. When $$n$$ is the product of two primes, which is customary, that would only occur if these primes are equal, or equivalently when $$n$$ can be factored by taking it's square root.

• So, method 1 has time complexity O(e), while method 2 has O(lg(e)). BTW, I think if we choose e first, then we can easily detect whether (p1 - 1) and (p2 - 1) are co-prime with e when choosing p1 and p2, if it's not, re-choose p1 and p2.
– Eric
Commented Jan 6, 2023 at 12:41
• BTW, I found λ(n)  magical.
– Eric
Commented Jan 7, 2023 at 7:58
• If $e$ is small, $k = (-\varphi(n))^{-1} \pmod e$ then $d = \frac{k\varphi(n)+1}{e}$ would be faster than large modular inversions I guess, but breaking with tradition would be unnecessary for an uncommon calculation like the final steps of key generation. Commented Nov 14, 2023 at 19:20