5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Balthazar Dec 17 '12 at 12:45
9
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.