2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ It is random. Expect 1/2 has one bit less, 1/4 has two-bit less. 1/8 etc.. $\endgroup$
    – kelalaka
    Jul 12, 2020 at 17:05
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Jul 12, 2020 at 18:06
  • $\begingroup$ @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. $\endgroup$
    – corsiKa
    Jul 13, 2020 at 7:42

2 Answers 2

2
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – kelalaka
    Jul 12, 2020 at 18:11
  • $\begingroup$ +1 for the bound on $d$ when $d = e^{-1} \bmod \varphi(n)$ $\endgroup$
    – fgrieu
    Jul 13, 2020 at 4:15
  • $\begingroup$ @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. $\endgroup$
    – user69015
    Jul 13, 2020 at 8:36
2
$\begingroup$

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<p\,q/2$ 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$.

$\endgroup$
2
  • $\begingroup$ Yes, d was computed as follows: phi = (p - 1) * (q - 1); d = inverse(e, phi). $\endgroup$
    – user80928
    Jul 12, 2020 at 20:10
  • 1
    $\begingroup$ @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. $\endgroup$
    – fgrieu
    Jul 12, 2020 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.