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

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?

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

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

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