RSA algorithm: Must $e$ be less than $\varphi(N)$?

Question

I understand why $e$ must be co-prime to the totient of $N$, but I see in many explanations of RSA that $e$ should be less than $\varphi(N)$. Is there a reason for this? Is it for ease of a small number or is there some law in play here?

Answer 1

First, the Euler's theorem

if $n$ and $a$ are coprime positive integers then

$$a^{\varphi(n)} \equiv 1 \pmod n$$ where $\varphi(n)$ is Euler's totient function.

Take $e> \varphi(n)$. Then, there exists $e' < \varphi(n)$ such that: $$e \equiv e' \pmod {\varphi(n)}$$

Then, we can write $$e = e' + k \cdot \varphi(n).$$

This $e'$ is the smaller representation of $e$ that does the same job.

$$a^{e} \equiv a^{e' + k \cdot \varphi(n)} \equiv a^{e'} a^{k \cdot \varphi(n)} \equiv a^{e'} (a^{\varphi(n)})^k \equiv a^{e'} (1)^k \equiv a^{e'} \pmod n$$ Therefore, there is no need for $e > \varphi(n)$.

We choose $e$ small so that the encryption can take a small amount. This is what we can control. We don't want the private exponent $d$ small, since it is insecure. If we take a random $e$, then we will not have the benefit.

Commonly used $e$'s are $\{3, 5, 17, 257\text{ or }65537\}$ and there is no danger even with $e=3$, as long as correct padding is used.

For encryption: Use Optimal Asymmetric Encryption Padding (OAEP) (RSA-OAEP) or RSA PKCS#1 v1.5 padding, the former is easier to implement, the later had many attacks due to improper implementations.

For signatures: Use Probabilistic Signature Scheme (PSS) and known as RSA-PSS.

---

Note 1: We first choose the $e$, then we choose the primes, not the reverse, since we may not get $\gcd(e,\varphi(n)) =1$ for all $n = p \cdot q$ is product of two distinct primes $p$ and $q$.

Note 2: We use Carmichael lambda $\lambda$ instead of $\varphi$, since it can produce smaller $d$s, since $\lambda(n)∣\varphi(n)$

Answer 2

Must $e$ be less than $\varphi(N)$?

The answer lies in how we read the question, and in particular in the definition of RSA. Among possible answers:

• No, for the definition of RSA in PKCS#1v2.2, which is a widely recognized industry standard, and states:

  the RSA public exponent $e$ is an integer between $3$ and $n-1$ satisfying $\operatorname{GCD}(e,\lambda(n))=1$

  where $n$ is the question's $N$, and $\lambda$ is the Carmichael function. This defintion allows $e$ to be larger than $\varphi(n)$, e.g. $e=n-2$. That value of $e$ makes sense: it maximizes the time required to encipher, which can be desirable to a degree as an anti-spam measure, and can speed-up decryption. $e=n$ also makes sense, and was actually the first value of $e$ considered, see second bullet here. I've asked about the security of these variants here.

• Yes, for the definition of RSA in the original RSA paper, which computes $e$ from $d$ as $e=d^{-1}\bmod\phi(n)$ [ where $\phi(n)$ is the question's $\varphi(N)$ ] and additionally requires $e\ge\log_2(n)$.

• Yes but that upper bound is much too large, for the definition of RSA in FIPS 186-4, which [ in a context where the public modulus is not yet defined, and will be at least 1024-bit ], states:

  The exponent $e$ shall be an odd positive integer such that: $2^{16}<e<2^{256}$.

• That's necessary but not sufficient for a mathematician's definition of RSA putting the upper bound on $e$ at $\lambda(N)$, ensuring a positive $e$ is uniquely defined for a given secret exponent $d$.

• We don't need any larger $e$, as stated by this other answer.