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$
  • $\begingroup$ It is random. Expect 1/2 has one bit less, 1/4 has two-bit less. 1/8 etc.. $\endgroup$ – kelalaka Jul 12 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 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 at 7:42
3
$\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$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, d was computed as follows: phi = (p - 1) * (q - 1); d = inverse(e, phi). $\endgroup$ – automatictester Jul 12 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 at 20:12
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).

| improve this answer | |
$\endgroup$
  • $\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 at 18:11
  • $\begingroup$ +1 for the bound on $d$ when $d = e^{-1} \bmod \varphi(n)$ $\endgroup$ – fgrieu Jul 13 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$ – corpsfini Jul 13 at 8:36

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.