# Can the encryption exponent e be greater than ϕ(N)?

So I was just wondering in RSA, can the encryption exponent e be greater than ϕ(N)??

For an examples sake, lets just say N = 707, so p = 101 & q = 7. So, we have ϕ(707) = 600.

Can I have e = 707? because I can calculate d = 443 by de=1 mod 600.

I have seen it almost everywhere that 1 < e < ϕ(N). But my question is WHY?

Why can't I have e = 707 & d = 443 in the setting I described above?

• I also understand that we need a large enough d. But isn't 443 large enough as compared to 707? d can be larger for larger values of N & we can still have e > ϕ(N) Dec 17, 2012 at 12:45

From Euler's Theorem, it turns out that, for $\gcd{(a, n)} = 1$, we have:

$$\large a^e \equiv a^{e ~ \mathrm{mod} ~ \varphi{(n)}} \pmod{n}$$

So, really, having $e > \varphi{(n)}$ doesn't do anything - you may as well use the reduced exponent:

$$e ~ \mathrm{mod} ~ \varphi{(n)}$$

You can absolutely use $e = n$ if you want to, it does not leak information about the private key. It's just slow. I mean use $e = n$ directly, of course - do not reduce it modulo $\varphi{(n)}$ to make it faster, since all you would get is a reduced public exponent of $p + q - 1$, and a free ticket to instant factorization of $n$.

## Choice of $$e$$

It is mathematically OK to choose a huge $$e$$ (or even a negative one), as long as the only link between $$e$$ and the factors $$p$$, $$q$$ of $$N$$ are the mandatory $$\gcd(e,p-1)=1$$ and $$\gcd(e,q-1)=1$$, and nothing is made to chose $$e$$ so that $$d$$ has special properties. For example $$e$$ could be:

• A random odd integer (including negative) with $$e≠±1$$, $$\gcd(e,p-1)=1$$ and $$\gcd(e,q-1)=1$$.
• A huge prime, random or independent of either $$p$$ or $$q$$; e.g. $$e=2^{1257787}-1$$.
• A public function of $$n$$ with the necessary properties, such as $$e=n^k$$ for some $$k≥1$$. In fact, $$e=k$$ was suggested by Clifford C. Cocks as early as 1973 (see this), before RSA even got its name.

However standards-conformance, regulatory, interoperability and performance concerns dictate otherwise:

• The PKCS#1 v2.2 standard requires $$2 (making $$e=n-2$$ the highest suitable $$e$$)
• NIST's FIPS 186-5 and other regulatory bodies require $$2^{16}
• Many implementations have a limit of $$e<2^{32}$$
• Modular exponentiation to the (positive) power $$e$$ has cost $$O(\log(e))$$: for $$e=2^k+1$$, it requires computing $$k$$ modular squares and one modular multiplication. That is a reason to chose $$e$$ small.
• Negative $$e<0$$ would introduce extra complexity (a modular inversion at each use of $$e$$) and slowness. That's not used.

so that and at the end of the day, $$e=2^{16}+1=65537$$ is the choice one is the least likely to regret (except performance-wise, and then not by a huge factor: at most a factor of 8.5 compared to $$e=3$$).

## Choice of $$d$$

Mathematically, any choice of $$d$$ with $$e\,d\bmod\lambda(N)=1$$ will do (no matter how large or negative), where $$\lambda(N)=\operatorname{lcm}(p-1,q-1)$$ when $$N=p\,q$$ with $$p$$ and $$q$$ distinct odd primes. This is precisely the condition necessary and sufficient for $$x↦x^e\bmod N$$ and $$x↦x^d\bmod N$$ to be reciprocals mappings of $$[0,N-1]$$. However

• PKCS#1 v2.2 (the industry standard) additionally wants $$0.
• FIPS 186-5 is even more restrictive and requires $$2^{\lceil\log_2 N\rceil/2}
• Some texts take $$d=e^{-1}\bmod\varphi(N)$$, where $$\varphi(N)=\phi(N)=(p-1)(q-1)$$ when $$N=p\,q$$ with $$p$$ and $$q$$ distinct odd primes. That implies $$1\le d<(p-1)(q-1)$$. That choice of $$d$$ is allowed by PKCS#1 v2.2, but often leads to $$d$$ too large for FIPS 186-5.
• Use of (positive) $$d$$ also has cost $$O(\log(d))$$. That makes $$d=e^{-1}\bmod\lambda(N)$$ attractive, as that's that's the smallest working positive $$d$$ for a given $$(N,e)$$.
• Negative $$d<0$$ would introduce extra complexity (a modular inversion at each use of $$d$$) and slowness. That's not used.

## Using a large $$e$$

There's at last one reason to use a large $$e$$: it makes use of the public key more costly for one not knowing the private key, and it has been suggested as a proof-of-work.

If one chooses a huge $$e$$, one should not choose it as $$e=e_0+k⋅\varphi(N)$$ or $$e+k⋅\lambda(N)$$ with $$e_0$$ guessable (like $$e_0$$ small, or $$e_0$$ linked to $$n$$ or some public data in some public way) and $$k≠0$$. Such $$e$$ will work just as well as $$e_0$$, but knowledge of $$e$$ and guessing $$e_0$$ will leak $$e-e_0=k⋅\lambda(N)$$, which allows efficient factorization of $$N$$ (at least for moderate $$k$$ or $$k$$ public; I do not know exactly what happens for huge random secret $$k$$).

Also, choosing $$e$$ as a function of $$d$$ small (or sparse) may allows factorization attacks.

Rather, $$e$$ could be chosen before $$p$$ and $$q$$, perhaps as a large prime ($$e$$ prime is not required, but slightly simplifies the choice of $$p$$ and $$q$$ with $$\gcd(e,p-1)=1$$ and $$\gcd(e,q-1)=1$$ ). Alternatively, $$e=N^k$$ for some moderate $$k$$ should be fine.

In principle you can have arbitrary large exponents. All $e + k \cdot \phi(N)$ are equivalent. But it's rarely useful. Larger $e$s are slower but not stronger.

I know one use for large exponents: Time-lock puzzles, where the challenged needs to calculate $b^{2^x}$, which is slow, but the challenger who knows the private key can reduce the exponent modulo $\phi$, which is much faster.