Return to Answer

Some attacks on some ad-hoc RSA encryption or signature padding, or/and their defective implementation, including several attacks due to Daniel Bleichenbacher, require an RSA public exponents $e$ of small value.

The limit has to do with some part of the padding (including a hash of $h$ bits), raised to the $e^\text{th}$ power, not being much wider than the public modulus $N$ of $n$ bits. It follows that $e\gg n/h$ block these attacks (but far from all attacks on ad-hoc RSA padding). There is no relation to $e$ being prime.

In RSA, ad-hoc padding should thus be avoided in favor of padding with reducibility to the RSA problem (like RSAES-OAEP, RSASSA-PSS, ISO/IEC 9796-2 mode 2 or 3), or schemes that do not need padding (like RSA-KEM). Security authorities prescribe that for new applications, and $e\ge65537$ everywhere; see this for more.

Digression: Why 65537?

Using prime RSA public exponent $e$ is customary: it makes drawing randomly seeded primes $p$ with $\gcd(p-1,e)=1$ (as required in RSA) easier and less subject to implementation goofs.

Using $e$ of the form $2^k+1$ is customary: raising to such $e^\text{th}$ power reduces to squaring $k$ times, then multiplying once by the original number (including for operations modulo $N$ as in RSA).

Primes of the form $2^k+1$ are thus customary. They demonstrably all are with $k$ a power of two, and known as Fermat primes. With $h\ge128$ and $n\le16384$ in most practical uses of RSA, using for $e$ the fifth (and largest known or practically usable) Fermat prime $F_4=2^{(2^4)}+1=65537$ is always very much on the safe side w.r.t. matching $e\gg n/h$.

Some attacks on some ad-hoc RSA encryption or signature padding, or/and their defective implementation, including several attacks due to Daniel Bleichenbacher, require an RSA public exponents $e$ of small value.

The limit has to do with some part of the padding (including a hash of $h$ bits), raised to the $e^\text{th}$ power, not being much wider than the public modulus $N$ of $n$ bits. It follows that $e\gg n/h$ block these attacks (but far from all attacks on ad-hoc RSA padding). There is no relation to $e$ being prime.

In RSA, ad-hoc padding should thus be avoided in favor of padding with reducibility to the RSA problem (like RSAES-OAEP, RSASSA-PSS, ISO/IEC 9796-2 mode 2 or 3), or schemes that do not need padding (like RSA-KEM). Security authorities recommend that for new applications, and $e\ge65537$ everywhere; see this for more.

Digression: Why 65537?

Using prime RSA public exponent $e$ is customary: it makes drawing randomly seeded primes $p$ with $\gcd(p-1,e)=1$ (as required in RSA) easier and less subject to implementation goofs.

Using $e$ of the form $2^k+1$ is customary: raising to such $e^\text{th}$ power reduces to squaring $k$ times, then multiplying once by the original number (including for operations modulo $N$ as in RSA).

Primes of the form $2^k+1$ are thus customary. They demonstrably all are with $k$ a power of two, and known as Fermat primes. With $h\ge128$ and $n\le16384$ in most practical uses of RSA, using for $e$ the fifth (and largest known or practically usable) Fermat prime $F_4=2^{(2^4)}+1=65537$ is always very much on the safe side w.r.t. matching $e\gg n/h$.

Some attacks on some ad-hoc RSA encryption or signature padding, or/and their defective implementation, including several attacks due to Daniel Bleichenbacher, require an RSA public exponents $e$ of small value.

The limit has to do with some part of the padding (including a hash of $h$ bits), raised to the $e^\text{th}$ power, not being much wider than the public modulus $N$ of $n$ bits. It follows that $e\gg n/h$ block these attacks (but far from all attacks on ad-hoc RSA padding). There is no relation to $e$ being prime.

In RSA, ad-hoc padding should thus be avoided (in favor of padding with reducibility to the RSA problem, like RSAES-OAEP, RSASSA-PSS, ISO/IEC 9796-2 mode 2 or 3). Security authorities prescribe ad-hoc padding should be avoided in new applications, and $e\ge65537$ used everywhere; see this for more.

Digression: Why 65537?

Using prime RSA public exponent $e$ is customary: it makes drawing randomly seeded primes $p$ with $\gcd(p-1,e)=1$ (as required in RSA) easier and less subject to implementation goofs.

Using $e$ of the form $2^k+1$ is customary: raising to such $e^\text{th}$ power reduces to squaring $k$ times, then multiplying once by the original number (including for operations modulo $N$ as in RSA).

Primes of the form $2^k+1$ are thus customary. They demonstrably all are with $k$ a power of two, and known as Fermat primes. With $h\ge128$ and $n\le16384$ in most practical uses of RSA, using for $e$ the fifth (and largest known or practically usable) Fermat prime $F_4=2^{(2^4)}+1=65537$ is always very much on the safe side w.r.t. matching $e\gg n/h$.

Some attacks on some ad-hoc RSA encryption or signature padding, or/and their defective implementation, including several attacks due to Daniel Bleichenbacher, require an RSA public exponents $e$ of small value.

The limit has to do with some part of the padding (including a hash of $h$ bits), raised to the $e^\text{th}$ power, not being much wider than the public modulus $N$ of $n$ bits. It follows that $e\gg n/h$ block these attacks (but far from all attacks on ad-hoc RSA padding). There is no relation to $e$ being prime.

In RSA, ad-hoc padding should thus be avoided in favor of padding with reducibility to the RSA problem (like RSAES-OAEP, RSASSA-PSS, ISO/IEC 9796-2 mode 2 or 3), or schemes that do not need padding (like RSA-KEM). Security authorities prescribe that for new applications, and $e\ge65537$ everywhere; see this for more.

Digression: Why 65537?

Using prime RSA public exponent $e$ is customary: it makes drawing randomly seeded primes $p$ with $\gcd(p-1,e)=1$ (as required in RSA) easier and less subject to implementation goofs.

Using $e$ of the form $2^k+1$ is customary: raising to such $e^\text{th}$ power reduces to squaring $k$ times, then multiplying once by the original number (including for operations modulo $N$ as in RSA).

Primes of the form $2^k+1$ are thus customary. They demonstrably all are with $k$ a power of two, and known as Fermat primes. With $h\ge128$ and $n\le16384$ in most practical uses of RSA, using for $e$ the fifth (and largest known or practically usable) Fermat prime $F_4=2^{(2^4)}+1=65537$ is always very much on the safe side w.r.t. matching $e\gg n/h$.

Some attacks on some ad-hoc RSA encryption or signature padding, or/and their defective implementation, including several attacks due to Daniel Bleichenbacher, require an RSA public exponents $e$ of small value.

The limit has to do with some part of the padding (including a hash of $h$ bits), raised to the $e^\text{th}$ power, not being much wider than the public modulus $N$ of $n$ bits. It follows that $e\gg n/h$ block these attacks (but not all attacks on ad-hoc RSA padding). There is no relation to $e$ being prime.

In RSA, ad-hoc padding must thus be avoided (in favor of padding with a proof of reducibility to the RSA problem). Security authorities prescribe ad-hoc padding must be avoided in new applications, and $e\ge65537$ everywhere; see this for more.

Digression: Why 65537?

Using prime RSA public exponent $e$ is customary: it makes drawing randomly seeded primes $p$ with $\gcd(p-1,e)=1$ (as required in RSA) easier and less subject to implementation goofs.

Using $e$ of the form $2^k+1$ is customary: raising to such $e^\text{th}$ power reduces to squaring $k$ times, then multiplying once by the original number (including for operations modulo $N$ as in RSA).

Primes of the form $2^k+1$ are thus customary. They demonstrably all are with $k$ a power of two, and known as Fermat primes. With $h\ge128$ and $n\le16384$ in most practical uses of RSA, using for $e$ the fifth (and largest known or practically usable) Fermat prime $F_4=2^{(2^4)}+1=65537$ is always very much on the safe side w.r.t. matching $e\gg n/h$.

Some attacks on some ad-hoc RSA encryption or signature padding, or/and their defective implementation, including several attacks due to Daniel Bleichenbacher, require an RSA public exponents $e$ of small value.

The limit has to do with some part of the padding (including a hash of $h$ bits), raised to the $e^\text{th}$ power, not being much wider than the public modulus $N$ of $n$ bits. It follows that $e\gg n/h$ block these attacks (but far from all attacks on ad-hoc RSA padding). There is no relation to $e$ being prime.

In RSA, ad-hoc padding should thus be avoided (in favor of padding with reducibility to the RSA problem, like RSAES-OAEP, RSASSA-PSS, ISO/IEC 9796-2 mode 2 or 3). Security authorities prescribe ad-hoc padding should be avoided in new applications, and $e\ge65537$ used everywhere; see this for more.

Digression: Why 65537?

Using prime RSA public exponent $e$ is customary: it makes drawing randomly seeded primes $p$ with $\gcd(p-1,e)=1$ (as required in RSA) easier and less subject to implementation goofs.

Using $e$ of the form $2^k+1$ is customary: raising to such $e^\text{th}$ power reduces to squaring $k$ times, then multiplying once by the original number (including for operations modulo $N$ as in RSA).

Primes of the form $2^k+1$ are thus customary. They demonstrably all are with $k$ a power of two, and known as Fermat primes. With $h\ge128$ and $n\le16384$ in most practical uses of RSA, using for $e$ the fifth (and largest known or practically usable) Fermat prime $F_4=2^{(2^4)}+1=65537$ is always very much on the safe side w.r.t. matching $e\gg n/h$.