5
$\begingroup$

FIPS 186-4 and NIST SP800 56B states following limits for public exponent $e$

$e$: a pre-determined public exponent − an odd integer, such that $65,537 ≤ e < 2^{256}$.

What security issue arises if a larger/ smaller fixed $e$ is chosen?

What happens if $e_{BitLen} > (RSA_{modulusBitLen}/2)$. Does the such $e$ introduce some vulnerability or weaken the system (like shorter length of $d$)? is there any correlation between bit length of $e$ and $d$?

$\endgroup$
0

1 Answer 1

4
$\begingroup$

For a list of reasons why a minimum $e$ other than $3$ is enforced in RSA key generation procedures, see this. These reasons are not convincing in the context of FIPS 186-4†, much less in the context of NIST SP 800-56. But if it's wanted a key generation procedure suitable for all applications of RSA, attacks on RSA decryption implementations thru side channels in padding check, including Bleichenbacher's attack on RSAES-PKCS1-v1_5, are a pragmatic justification.

$65537$ is the minimum because that's $F_4=2^{(2^4)}+1$, the fourth (and highest known) Fermat prime, and also is the highest odd $e$ that can be built with a 17-steps addition chain. $F_3=2^{(2^3)}+1=257$ would still sometime allow the $e^\text{th}$ root attack‡ on textbook RSA, and perhaps was excluded for that reason.

$e<2^{256}$ may be there because there must be some upper limit for interoperability and testing reasons, including performance (cost of using an RSA public key grows about as the bit size of $e$). Microsoft initially had a 32-bit upper limit, and I have seen 128 in Smart Card applications, where size of public keys and certificates is closely watched. As an aside, such upper limit makes it less easy to deliberately weaken the key by using e.g. $e=p\,q-p-q+2$, which makes textbook RSA encryption and decryption degenerate to the identity function.

Also, allowing a wide range of $e$ allows randomness to be injected in $e$. That's not known to be useful or dangerous, but has been considered as recommendable.


What happens if $e_\mathrm{BitLen} > (\mathrm{RSA}_\mathrm{modulusBitLen}/2)$. Does the such $e$ introduce some vulnerability or weaken the system?

A noticeable thing is that any use of the public key becomes slower by a large factor, because cost is roughly proportional to $e_\mathrm{BitLen}$, which for recommendable $n$ gets into the thousands instead of $17$ for the usual $e=65537$.

Also, it becomes easier to make silly choices of $e$ and $d$ for perfectly reasonable choice of prime factors of $n$, e.g. $e$ just above $\max(p,q)$ for $n=p\,q$ (which allows factorization of $n$ by searching for a factor just below $e$), or random 512-bit $d$ for 2048-bit $n$ and $e=d^{-1}\bmod((p-1)(q-1))$, which is unsafe (see this). As noted in comment, enforcing a 256-bit maximum for the size of $e$ helps block such misguided attempts, because the sum of the bit length of $e$ and of $d$ tends to be at least the bit length of $n$ (within at most 1 when $d$ is computed as $e^{-1}\bmod\varphi(n)$ where $\varphi$ is Euler's totient, and within a few bits for any other way to compute $d$ and most natural choices of $n$).


Is there any correlation between length of $e$ and $d$?

None noticeable when using a recommendable RSA key generation method. All such methods are such that the last one generated of $d$ and $e$ will have a bit length essentially determined by $n$, and mostly independent of the bit length of the first one generated of $d$ and $e$.

Modern RSA key generation methods compute $d$ from $e$ (when they compute $d$ at all), typically either per $d=e^{-1}\bmod\varphi(n)$, or per $d=e^{-1}\bmod\lambda(n)$ where $\lambda$ is the Carmichael function. The original RSA article chooses $d$ randomly, and computes $e=d^{-1}\bmod\varphi(n)$, but that's not much used because it yields large $e$, which makes signature verification and encryption slow; and could be misunderstood as a license to use too small a $d$, which would be unsafe.


† that is RSA signature with one of ANS X9.31 (aka CKM_RSA_X9_31), RSASSA-PKCS1-v1_5 and RSASSA-PSS signature padding. These schemes are unbroken, including as defined by ANS X9.31:1998 and PKCS#1, which explicitly allow $e=3$.

‡ The $e^\text{th}$ root attack attempts to invert textbook RSA encryption $m\mapsto c=m^e\bmod n$ by computing $\sqrt[e]c$ and checking if that's an integer, which would be $m$. It fails when $m>\left\lfloor\sqrt[e]n\right\rfloor$. Extensions are known only for slightly larger $m$, see this.

$\endgroup$
1
  • 2
    $\begingroup$ $e<2^{256}$ might help also against people shooting themselves in the foot by trying to accelerate the operations decryption/signing using the secret key by choosing a smallish e in the key generation and then switching e and d. $\endgroup$
    – garfunkel
    Feb 2, 2023 at 16:37

Your Answer

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

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