# RSA: How close d should be to n, given default public exponent e = 65537

For small public exponent e, private exponent d should be less than but close to modulus n.

Is there any particular test, applied in common implementations, to verify that? If so, what would be the threshold?

I have noticed that using Python's Crypto.Util.number.getStrongPrime (docs):

key_size = 2048
prime_size = int(key_size / 2)
e = 65537
p = getStrongPrime(prime_size, e)
q = getStrongPrime(prime_size, e)


the bit length difference between d and n is never bigger than 6.

• It is random. Expect 1/2 has one bit less, 1/4 has two-bit less. 1/8 etc.. – kelalaka Jul 12 at 17:05
• No, that's not right. Although the first bit of the modulus is always one, you can expect a value between 0 and N. That means that the chance of it being a bit smaller depends on N, and would be - on average - more like 2/3rd. Doesn't matter much in the scheme of things, but there it is. – Maarten Bodewes Jul 12 at 18:06
• @kelalaka No offense, but this is one SE site where you really should defend a statement like "it is random" with some sort of logic, citation, or other backing evidence. Random is, well, a really funny word after all. – corsiKa Jul 13 at 7:42

Is there any particular test, applied in common implementations, to verify that private exponent $$d$$ is less than but close to modulus $$n$$ ?

Yes, for some lenient definition of close. FIPS 186-4 is a de-facto standard that some implementations follow. It prescribes$$d\gets e^{-1}\bmod\bigl(\operatorname{lcm}\left(p-1,q-1\right)\bigr)\tag{1}\label{eq1}$$which implies $$d thus¹ a $$d$$ at least one bit less than the modulus is. And in the end of FIPS 186-4 appendix B.3.1 additional criteria 3 lies the prescription:

• In the extremely rare event that $$d\le2^{nlen/2}$$ (where $$nlen$$ is the bit size of the public modulus), then new values for $$p$$, $$q$$ and $$d$$ shall be determined. A different value of $$e$$ may be used, although this is not required.

Such test is pointless from a theoretical standpoint when both:

1. $$e$$ is chosen before $$p$$ and $$q$$, as is usually the case.
2. The only significant dependence about the value of $$e$$ of the mostly independently and randomly chosen $$p$$ and $$q$$ is that $$\gcd(p-1,e)=1=\gcd(q-1,e)$$.

Condition 2 should always hold for a proper RSA key generation procedure. Even if $$p\bmod e$$ and $$q\bmod e$$ where fixed public constants, condition 2 could still hold for truly small $$e$$ including $$e=65537$$, up to at least say 20 bits: revealing that little information about $$p$$ and $$q$$ appears unlikely to ease factorization.

The only technically sound rationale for $$d\le2^{nlen/2}$$ or other test against small $$d$$ is to prevent the import of an inappropriately generated private key; and in an otherwise proper RSA key generation procedure with modulus bit size $$nlen\ge1024$$ (the minimum in FIPS 186-4), to catch a malfunction or a bug.

In a fielded security device (Smart Card, HSM), if that test fails at key generation, the Right Thing is to fall into a safe state where the gizmo needs at the very least to be physically reset before anything else goes, perhaps after metaphorically falling on one's sword, that is burninating/zeroizing all secret material. In code under development, that test should be an assertion. If something needs to be rubber-stamped, do whatever is morally defensible to satisfy the authority with the rubber-stamp.

I have noticed that using (strong primes per some criteria) the bit length difference between $$d$$ and $$n$$ is never bigger than $$6$$.

It was not tried hard enough, or something is broken in the key generation procedure. There is no good reason why that would hold for $$e=65537$$. That's even though, contrary to $$\eqref{eq1}$$ mandated by FIPS 186-4, $$d$$ is computed per $$d\gets e^{-1}\bmod\bigl((p-1)(q-1)\bigr)\tag{2}\label{eq2}$$ As explained in that other answer, $$d$$ per $$\eqref{eq2}$$ is expected to be roughly uniform in the interval $$\bigl[(1+\varphi(n))/e,\varphi(n)\bigr)$$ and we should sometime see it near the bottom, thus with 15, perhaps 16 bits less than the public modulus. However we need to perform about $$e$$ attempts to approach that limit.

If the test against $$d\le2^{nlen/2}\eqref{eq1}$$ is used, that should be with $$d$$ per $$\eqref{eq1}$$. Absent error, that test mathematically can't fail for $$d$$ per $$\eqref{eq2}$$ with $$e<2^{256}$$ and $$n>2^{1023}$$ as mandated by FIPS 186-4. Failure of the test is at least theoretically possible when using $$\eqref{eq1}$$, should $$\gcd(p-1,q-1)$$ happen to be huge. Which is extremely unlikely for proper generation of $$p$$ and $$q$$.

Both $$\eqref{eq1}$$ and $$\eqref{eq2}$$ are allowed by PKCS#1 since the origin, thus $$\eqref{eq1}$$ is unlikely to cause an interoperability problem even if a private key is moved across implementations (which should be the only case when the method used for the determination of $$d$$ matters, since all mathematically valid $$d$$ for a given public key produce the same numerical results when properly used in RSA). Contrast with the use of $$\eqref{eq2}$$ which has fair probability to lead to failure at key import by an implementation written with FIPS 186-4 as a reference.

¹ By definition of $$e^{-1}\bmod\lambda$$, and given that $$\lambda=\operatorname{lcm}\left(p-1,q-1\right)$$, and given that primes $$p$$ and $$q$$ are large, thus $$p-1$$ and $$q-1$$ both are multiple of $$2$$.

• Yes, d was computed as follows: phi = (p - 1) * (q - 1); d = inverse(e, phi). – automatictester Jul 12 at 20:10
• @automatictester: that's $d$ per equation (2). As explained, it's fine, except in a FIPS 186-4 context, and that it makes the test of a minimum $d$ even more pointless than when using equation (1). I have updated the question about why. – fgrieu Jul 12 at 20:12

The private exponent $$d$$ is generally constructed as $$d = e^{-1} \bmod \varphi(n)$$. Is means it is the smallest positive integer that satisfy $$e \equiv d \pmod{ \varphi(n)}$$, and in particular $$d < \varphi(n)$$, which is the upper bound.

Another view of this is that there exists an integer $$k$$ such that $$ed = 1 + k\varphi(n),$$ The integer $$k$$ is at least $$1$$ and we can get a lower bound for $$d$$: $$d = (1 + k\varphi(n)/e \geq (1+\varphi(n))/e.$$ Then, we can say, roughly, that $$d$$ is expected to be an integer between $$(1+\varphi(n))/e$$ and $$\varphi(n)$$.

Of course, it shall be noted that adding a multiple of $$\varphi(n)$$ to $$d$$ gives a valid private exponent, and those are bigger than $$\varphi(n)$$ (and makes the computation more costly).

• The smallest is chosen with Carmichael lambda and $\lambda(n) | \varphi(n)$. And, this answer gives nothing about the probability of the size of $d$. – kelalaka Jul 12 at 18:11
• +1 for the bound on $d$ when $d = e^{-1} \bmod \varphi(n)$ – fgrieu Jul 13 at 4:15
• @kelalaka smallest'' was a reference to the $\bmod$ operation. And I have not seen a mention about the probability of the size of $d$ in the original question. Replacing $\varphi(n)$ by $\lambda(n)$ should give similar results. – corpsfini Jul 13 at 8:36