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

Question

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 ?

Answer 1

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<e<\varphi$. 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<N$ 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<e<\varphi(N)$, 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.