# How is it possible to derive the public exponent from an RSA private key?

I am gonna write down formulas that I know and use to generate RSA keys.

1. we choose $$p$$, $$q$$
2. $$N = p\cdot q$$
3. $$\varphi(n) = (p-1)\cdot(q-1)$$
4. choose $$e$$ such as
• $$1 < e < \varphi(N)$$
• $$e$$ is coprime with $$N$$, $$\varphi(n)$$
5. choose $$d$$ so that $$d\cdot e\bmod\varphi(n)=1$$

That's it. With these, if we have $$p=2$$ and $$q=7$$, I successfully get $$d=11$$ and $$e=5$$ which is correct.

Now Imagine, that I only have private key which is $$(11,14)$$ (that is $$d=11$$, $$N=14$$). How do I get $$e=5$$. I understand that with $$d$$ and $$N$$, you can't directly get $$e$$, but as RSA works, it tries different variants of $$e$$ , then checks and if it's valid, that's how you get public key from private key.

Can anyone explain to me what steps should I take here to figure out what $$e$$ could be and then from those, which $$e$$ should I choose ?

• Note: You forgot $p\ne q$, which is necessary if you define $\varphi(n) = (p-1)\cdot(q-1)$, or want encryption/decryption to always work. The requirement that $e$ is coprime with $N$ is unusual. The requirement that $1<e<\varphi(n)$ is also slightly unusual for RSA as practiced, it's more usual to have $1<e<N$ (PKCS#1) or $2^{16}<e<2^{256}$ (FIPS 186-4).
– fgrieu
Jul 10, 2021 at 8:52
• If you've got a signature you can just test your guess by verifying it. That wont work for ciphertext though, at least not if you use a randomized padding scheme. With textbook RSA that might still work. I'm not sure if you can calculate $e$ if you've got nothing to verify against and if $e$ is chosen randomly. It might be possible to do something if it is chosen deterministically given this answer: guess $e$, calculate $p$ and $q$, check if it matches the deterministic algorithm. Jul 10, 2021 at 9:10
• What formula do I use so that at least I can start gessing e if I have d and N ? In my above formulas, it still doesn't make sense how I write a program that guesses e.. Jul 10, 2021 at 9:15
• In practice, the private key consists of (at least) $p,q,$ and $e$. $d$ and $N$ can easily be computed from these, and are often stored along with $p,q,$ and $e$; but they are not essential. If all you have is $d$ and $N$, then you can't compute $e$ without factorising $N$. Jul 11, 2021 at 0:09

It's asked how, in RSA, one finds $$e$$ given $$d$$ and $$N$$. I'll ignore the question's requirement that $$e$$ is coprime with $$N$$, which is highly unusual and has no mathematical relevance. I'll also assume $$p\ne q$$, because it's necessary for the stated $$\varphi(N)=(p-1)\cdot(q-1)$$ to hold.

With the question's definition of RSA, the method to find $$e$$ goes

• Factor $$N$$ to find $$p$$ and $$q$$
• Compute $$\varphi=(p-1)\cdot(q-1)$$
• Compute $$e$$ knowing $$e\cdot d\bmod\varphi=1$$ and $$1. That $$e$$ is uniquely defined, and the modular inverse of $$d$$ in the multiplicative group of integer modulo $$\varphi$$. For small numbers, a working method is trial and error of small odd $$e>1$$. A more constructive method is the (half)-extended Euclidean algorithm, which computes $$e=d^{-1}\bmod \varphi$$ directly. For a practical algorithm that uses only non-negative integers:
1. $$a\gets d\bmod \varphi$$ , $$b\gets \varphi$$ , $$x\gets0$$ and $$y\gets1$$
Note: $$a\cdot x+b\cdot y=\varphi$$ will keep holding
2. if $$a=1$$, then output "the desired inverse $$e$$ of $$d$$ modulo $$\varphi$$ is $$y$$" and stop
3. If $$a=0$$, then output "the desired inverse $$e$$ of $$d$$ modulo $$\varphi$$ does not exist" and stop
4. $$r\gets\lfloor b/a\rfloor$$
5. $$b\gets b-a\cdot r$$ and $$x\gets x+r\cdot y$$
6. if $$b=1$$, then output "the desired inverse $$e$$ of $$d$$ modulo $$\varphi$$ is $$\varphi-x$$" and stop
7. If $$b=0$$, then output "the desired inverse $$e$$ of $$d$$ modulo $$\varphi$$ does not exist" and stop
8. $$r\gets\lfloor a/b\rfloor$$
9. $$a\gets a-b\cdot r$$ and $$y\gets y+r\cdot x$$
10. Continue at 2

This same method is typically used to compute $$d$$ from $$e$$, since $$d$$ and $$e$$ are symmetric in $$e\cdot d\bmod\varphi=1$$. That's however not how $$d=11$$ was computed in the question; for some strange reason the question requires $$e<\varphi(N)$$ but not $$d<\varphi(N)$$, or the more usual $$d or $$d<\operatorname{lcm}(p-1,q-1)$$.

Serious problem with this approach for RSA as practiced (thus very large $$N$$, at least hundreds decimal digits): It won't work, because $$N$$ will be so large that it can't be factored, thus $$\varphi$$ can't be computed in this way.

Also, the question's condition $$e\cdot d\bmod\varphi(N)=1$$ is a sufficient, but not a necessary condition for textbook RSA encryption using $$(e,N)$$ to be undone by RSA decryption using $$(d,N)$$, and vice versa. The necessary condition is $$e\cdot d\bmod\lambda(N)=1$$, where $$\lambda(N)=\operatorname{lcm}(p-1,q-1)$$. That condition is often used in practice: it's allowed by PKCS#1, and mandated by FIPS 186-4. Artificially small example: $$N=341$$, $$e=7$$, $$d=13$$ works just fine for textbook RSA encryption/decryption, yet $$e\cdot d\bmod\varphi(N)=1$$ does not hold (in this example $$p=11$$, $$q=31$$, $$\varphi(N)=300$$, $$\lambda(N)=30$$ ).

However, in RSA as practiced, $$e$$ is small, often small enough that $$e$$ can be found by enumeration. Thus a method could be:

• compute $$c\gets2^d\bmod N$$
• compute $$c_2\gets c^2\bmod N$$
• set $$e\gets1$$
• repeat
• set $$e\gets e+2$$
• set $$c\gets c\cdot c_2\bmod N$$; notice $$c=2^{d\cdot e}\bmod N$$
• if $$c=2$$
• for $$m$$ the first hundred odd primes (note: for small $$N$$, we want to stop as soon as $$m^2>N$$ )
• if $$m^{e\cdot d}\bmod N\ne m$$, continue at repeat above
• output $$e$$ and stop.

It's almost certain that if an $$e$$ is output, it's valid in the sense that textbook RSA encryption using $$(e,N)$$ is undone by RSA decryption using $$(d,N)$$, and (equivalently) $$e\cdot d\bmod\lambda(N)=1$$. It's not quite sure $$e\cdot d\bmod\varphi(N)=1$$, but knowing $$e\cdot d$$ and $$N$$ it's possible to factor $$N$$ (using this algorithm), and then compute the $$e$$ with $$e\cdot d\bmod\varphi(N)=1$$ and $$1, if for some reason that's desired.

Addition: The above is far from optimal. When $$\delta=\ln(e)/\ln(N)$$ is below a certain threshold, in the order of $$0.292$$, there are ways to factor $$N$$ (and thus solve the problem by the first method discussed). Basically, we swap $$d$$ and $$e$$ in Dan Boneh and Glenn Durfee's Cryptanalysis of RSA with Private Key $$d$$ Less than $$N^{0.292}$$, in proceedings of Eurocrypt 1999. See there for more.

• Of course, $p-1$ and $q-1$ should not have any big factor in common, or else your method of generating primes sucks and makes attacks undesiredly feasible (in fact, a lort more simple relations between $p,q$ must be avoided)). So preferably, $\lambda(p-1,q-1)$ is something like $\frac12\phi(N)$. - Moreover, in practice one often picks a nice (public) $e$ such as a smallish, but not too small prime near a power of $2$; this makes computing the encryption faster while at the same time it is not much of a problem to avoid primes $\equiv 1\pmod e$ in the very process of generating them Jul 10, 2021 at 17:50