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

Question

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?

Answer 1

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

Answer 2

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<e<n$ (making $e=n-2$ the highest suitable $e$)
• NIST's FIPS 186-5 and other regulatory bodies require $2^{16}<e<2^{256}$
• 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<d<n$.
• FIPS 186-5 is even more restrictive and requires $2^{\lceil\log_2 N\rceil/2}<d<\lambda(N)$
• 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.

Answer 3

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.