RSA: large private exponent often yields large public exponent

Question

In this answer to a question about choosing RSA's exponent (whether it is better to choose the private or the public exponent), user @Jus12 stated:

When choosing $d$ first: [...] guarantees with high probability that $e$ will be large, making encryption slow.

When choosing $e$ first: can choose very small or pre-determined value of $e$; [...] guarantees with high-probability that $d$ is large so various attacks still don't work.

I easily understand that a small value for $e$ leads to a large value for $d$, as $e\cdot d\geq k\varphi(N)+1$ with $k\in\mathbb Z$ and $N=pq$ being the RSA modulus.

However, I do not see why a large $d$ will probably also result in a large value for $e$. I just see no obvious reason why a large $e$ is more probable than a small one.

I did a quick test for $p=5$ and $q=11$. Considering every $d>\max(p,q)$ as "large" I get the following results:

 d   e
------
13  37
17  33
19  19
21  21
29  29
31  31
33  17
37  13
39  39
------
23   7
27   3

In this case, large $e$'s are more than four times more frequent than small ones. But why is this?

Answer 1

For any integer $k>1$, the function $F$ onto $\Bbb Z^*_k$ (the subet of integers in $[0,k)$ that are coprime with $k$ ) defined by $x\mapsto x^{-1}\bmod k$ is a permutation of $\Bbb Z^*_k$.

For any finite set $\Bbb S$ and any permutation $F$ of $\Bbb S$, if $x$ is uniformly random on $\Bbb S$ then $F(x)$ is uniformly random on $\Bbb S$.

It follows that if we choose $d$ uniformly randomly in $\Bbb Z^*_{\varphi(N)}$ (which is a fair model of choosing a large random $d$ ), and compute $e=d^{-1}\bmod\varphi(N)$, then the resulting $e$ is uniformly random on $\Bbb Z^*_{\varphi(N)}$. The average of $e$ is going to be about $\varphi(N)/2$, thus not "small" in the sense that has in RSA for "small $e$".

In an RSA context, $\log_2(N)\approx\log_2(\varphi(N))$. If $N$ is $n$-bit, a random element of $\Bbb Z^*_{\varphi(N)}$ is going to be $k$-bit or less with probability less than $2^{k-n+1}$, thus very seldom "small" (e.g. for 2048-bit $N$, 128-bit or less with probability $2^{-1919}$ ). That applies to $e$ for a random $d$ (large or not).

Summary: Choosing $d$ at random and computing $e$ from that gives overwhelming assurance that $e$ is not small. There's no such thing as large $d$ implying large $e$.

---

Note: the question is correct when stating that choosing $e$ small then $d=e^{-1}\bmod\varphi(N)$ ensures that this $d$ is large. But it is wrong in assuming that a large $d$, or/and a large $e^{-1}\bmod\varphi(N)$, is enough that the attacks alluded to don't work (this is referring in particular to Dan Boneh and Glenn Durfee's Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999).

For example, we could chose $r$ a random prime of $\frac27\log_2N$ bits, then $e=(\varphi(N)/2+r)^{-1}\bmod\varphi(N)$, then $d=e^{-1}\bmod\varphi(N)$. That $d$ is $\varphi(N)/2+r$, thus about 1 bit less than $N$, thus large. However $r$ is another working $d$, and is consistently small enough to allow the attack.

What matters to prevent the attack is that there exists no small positive working $d$, in other words that $e^{-1}\bmod\lambda(N)$ is not small, where $\lambda(N)$ is the the Carmichael function, with $\lambda(N)=\varphi(N)/\gcd(p-1,q-1)$ when $N$ is the product of two distinct primes $p$ and $q$. That is insured when $e$ is small and the factors of $N$ chosen randomly and mostly independently, making it unlikely that $\gcd(p-1,q-1)$ is unduly large.