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

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.

Answer 3

Except for standards, regulatory, and interoperability concerns, it is OK to choose a huge $e$, 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$ as 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$.

However the PKCS#1v2 standard requires $2<e<n$ (making $e=n-2$ the highest suitable $e$), FIPS 186-3 requires $2^{16}<e<2^{256}$, many implementations have a limit of $e<2^{32}$, and at the end of the day $e=2^{16}+1$ is the choice you are 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$).

Notice that RSA, as defined by PKCS#1v2 (the industry standard), does not prescribe $d=e^{-1}\bmodφ(N)$ as some texts (including the original RSA article) do; it prescribes that $e.d\bmodλ(N)=1$, where $λ(N)=\operatorname{lcm}(p-1,q-1)$ when $N=p⋅q$ with $p$ and $q$ distinct odd primes. That allows more freedom in the choice of $d$ and $e$, and 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]$.

If one chooses a huge $e$, one should not choose it as $e=e_0+k⋅φ(N)$ or $e+k⋅λ(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⋅λ(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.