4
$\begingroup$

I understand why $e$ must be co-prime to the totient of $N$, but I see in many explanations of RSA that $e$ should be less than $\varphi(N)$. Is there a reason for this? Is it for ease of a small number or is there some law in play here?

$\endgroup$
6
$\begingroup$

First, the Euler's theorem

if $n$ and $a$ are coprime positive integers then

$$a^{\varphi(n)} \equiv 1 \pmod n$$ where $\varphi(n)$ is Euler's totient function.

Take $e> \varphi(n)$. Then, there exists $e' < \varphi(n)$ such that: $$e \equiv e' \pmod {\varphi(n)}$$

Then, we can write $$e = e' + k \cdot \varphi(n).$$

This $e'$ is the smaller representation of $e$ that does the same job.

$$a^{e} \equiv a^{e' + k \cdot \varphi(n)} \equiv a^{e'} a^{k \cdot \varphi(n)} \equiv a^{e'} (a^{\varphi(n)})^k \equiv a^{e'} (1)^k \equiv a^{e'} \pmod n$$ Therefore, there is no need for $e > \varphi(n)$.

We choose $e$ small so that the encryption can take a small amount. This is what we can control. We don't want the private exponent $d$ small, since it is insecure. If we take a random $e$, then we will not have the benefit.

Commonly used $e$'s are $\{3, 5, 17, 257\text{ or }65537\}$ and there is no danger even with $e=3$, as long as correct padding is used.

For encryption: Use Optimal Asymmetric Encryption Padding (OAEP) (RSA-OAEP) or RSA PKCS#1 v1.5 padding, the former is easier to implement, the later had many attacks due to improper implementations.

For signatures: Use Probabilistic Signature Scheme (PSS) and known as RSA-PSS.


Note 1: We first choose the $e$, then we choose the primes, not the reverse, since we may not get $\gcd(e,\varphi(n)) =1$ for all $n = p \cdot q$ is product of two distinct primes $p$ and $q$.

Note 2: We use Carmichael lambda $\lambda$ instead of $\varphi$, since it can produce smaller $d$s, since $\lambda(n)∣\varphi(n)$

$\endgroup$
5
$\begingroup$

Must $e$ be less than $\varphi(N)$?

The answer lies in how we read the question, and in particular in the definition of RSA. Among possible answers:

  • No, for the definition of RSA in PKCS#1v2.2, which is a widely recognized industry standard, and states:

    the RSA public exponent $e$ is an integer between $3$ and $n-1$ satisfying $\operatorname{GCD}(e,\lambda(n))=1$

    where $n$ is the question's $N$, and $\lambda$ is the Carmichael function. This defintion allows $e$ to be larger than $\varphi(n)$, e.g. $e=n-2$. That value of $e$ makes sense: it maximizes the time required to encipher, which can be desirable to a degree as an anti-spam measure, and can speed-up decryption. $e=n$ also makes sense, and was actually the first value of $e$ considered, see second bullet here. I've asked about the security of these variants here.

  • Yes, for the definition of RSA in the original RSA paper, which computes $e$ from $d$ as $e=d^{-1}\bmod\phi(n)$ [ where $\phi(n)$ is the question's $\varphi(N)$ ] and additionally requires $e\ge\log_2(n)$.

  • Yes but that upper bound is much too large, for the definition of RSA in FIPS 186-4, which [ in a context where the public modulus is not yet defined, and will be at least 1024-bit ], states:

    The exponent $e$ shall be an odd positive integer such that: $2^{16}<e<2^{256}$.

  • That's necessary but not sufficient for a mathematician's definition of RSA putting the upper bound on $e$ at $\lambda(N)$, ensuring a positive $e$ is uniquely defined for a given secret exponent $d$.

  • We don't need any larger $e$, as stated by this other answer.

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