6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – SEJPM Sep 11 '15 at 20:20
  • $\begingroup$ 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. $\endgroup$ – Pranav Sharma Sep 11 '15 at 20:30
  • $\begingroup$ So $ed\equiv 1 \pmod{pq}$? $\endgroup$ – SEJPM Sep 11 '15 at 20:36
  • 1
    $\begingroup$ 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? $\endgroup$ – Pranav Sharma Sep 11 '15 at 20:44
  • 1
    $\begingroup$ 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)$? $\endgroup$ – SEJPM Sep 11 '15 at 21:51
7
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ I've seen implementations that require $d < n$, I don't think it's particularly rare. $\endgroup$ – Gilles Sep 15 '15 at 21:29
0
$\begingroup$

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

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