Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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) –  Balthazar Dec 17 '12 at 12:45
add comment

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
    
Thank you for the answer. That does help a lot. –  Balthazar Dec 17 '12 at 13:16
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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