# Is there an upper bound to the private exponent in RSA?

In the RSA algorithm, we choose $p$ and $q$ as prime numbers and we select a value $e$ which is coprime to $\varphi(pq)=(p-1)(q-1)$.

Then we calculate $d:=e^{-1}\bmod\varphi(pq)$.

My question is: What could be the maximum value of $d$? Is there an upper bound to it?

• Yes there is, simply by the way you compute it. Hint: Look at the equation for computing d and think about what happens when d gets large. – SEJPM Sep 11 '15 at 20:20
• So in my thinking, the value of d might not go beyond the value of n which is essentially p*q. Correct me if i'm wrong. – Pranav Sharma Sep 11 '15 at 20:30
• So $ed\equiv 1 \pmod{pq}$? – SEJPM Sep 11 '15 at 20:36
• I'm not really sure what you mean. It could go beyond (p-1)*(q-1). Or it could not. I'm not aware of what the upper value for d could be. Which is my actual question. What is the upper bound for d? Is it (p-1)*(q-1) or is it p*q or is it some other value? – Pranav Sharma Sep 11 '15 at 20:44
• if it would go beyond $(p-1)(q-1)$ wouldn't it be then again reduced by $(p-1)(q-1)$, keeping it smaller than $(p-1)(q-1)$? – SEJPM Sep 11 '15 at 21:51

If $d$ is a valid RSA decryption exponent, then so is $d \pm k \lambda(pq)$ for any integer $k$.

As a corollary, we may always choose the decryption exponent to lie in the range $0 < d < \lambda(pq)$. In fact, there's generally no reason to choose the decryption outside that range: a larger exponent would just make decryption slower, while using a negative exponent would require computing a modular inverse (which is even slower yet).

Thus, in practice, pretty much all RSA decryption exponents are positive integers less than $\lambda(pq) = \operatorname{lcm}(p-1, q-1)$, or at least less than $\varphi(pq) = (p-1)(q-1)$.

Further, since $\lambda(pq) \le \varphi(pq) < pq = n$, it follows that a normal (i.e. not deliberately chosen to be unnecessarily large) RSA decryption exponent is always (positive and) smaller than the modulus $n$.

Mathematically speaking, there is no upper bound on the private exponent in RSA: assuming $d$ is a valid private exponent, then the valid exponents are the set of $d'=d+k\cdot\lambda(p\cdot q)$ with $k\in\mathbb Z$, where $\lambda(p\cdot q)=\operatorname{lcm}(p-1,q-1)$ since $p$ and $q$ are distinct primes; this set is unbounded.

If you compute $d$ as an integer with $d\equiv e^{-1}\pmod{\varphi(p\cdot q)}$, then by definition $d$ verifies $e\cdot d-1$ multiple of $\varphi(p\cdot q)$, and is unbounded. If you compute $d$ as the integer $d=e^{-1}\bmod\varphi(p\cdot q)$, by a common definition of that notation, $d$ is additionally non-negative and less than $\varphi(p\cdot q)$, which is then an upper bound.

In practice, available memory and time, existing software, or standards, limit the value of $d$. A most common standard, PKCS#1, requires $0<d<n$; the FIPS 186-4 standard requires $2^{\lceil\log_2(N)\rceil/2}<d<\operatorname{lcm}(p-1,q-1)$; some implementations allow $0<d<256^{\lceil\log_{256}(p\cdot q)\rceil}$; $d\ge\varphi(p\cdot q)$ is unusual.

• I've seen implementations that require $d < n$, I don't think it's particularly rare. – Gilles 'SO- stop being evil' Sep 15 '15 at 21:29

Aside from being pedantic and telling you that you can choose arbitrarily large $d$ in some congruence class, you can always achieve $d\equiv -1 \bmod \phi(pq)$ by choosing $e$ to be the same.

So in the interval $[1,\phi(pq)]$ the largest $d$ could be is $\phi(pq)-1$.