0
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ "I just see no obvious reason why a large $e$ is more probable than a small one." Well, there are more large integer than small ones. ;) $\endgroup$ – fkraiem Sep 15 '18 at 13:01
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you very much for your expertise. If I got that right, there is no general implication large $d\Rightarrow$ large $e$? $\endgroup$ – Philipp Imhof Sep 15 '18 at 19:47
  • $\begingroup$ @Philipp Imhof: right. Only most $d$, including virtually all random $d$, give large $e$. $\endgroup$ – fgrieu Sep 15 '18 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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