0
$\begingroup$

For example, given:

p = 173, q = 149, e = 3

Using phi(n) gives d = 16971

While using lambda(n) gives d = 4243

Both values satisfy the checking equation (de)%phi=1, so are both correct, and if so, is one better than the other?

$\endgroup$
  • $\begingroup$ Yes, See or search Carmichael lambda. Possible duplicate of lcm versus phi in RSA $\endgroup$ – kelalaka Mar 30 at 22:02
  • 1
    $\begingroup$ "Can there be more than one valid private exponent"; assuming that a valid private exponent exists, there will always be an infinite number of valid private exponents... $\endgroup$ – poncho Mar 30 at 22:13
  • $\begingroup$ @poncho Thank you for your rapid and clear answer. Since there are an infinite number of valid private exponents, are any of them theoretically better than others? And if so, is there a way to find the best one? $\endgroup$ – Zachary Clark Mar 30 at 22:20
1
$\begingroup$

Both values satisfy the checking equation (de)%phi=1, so are both correct, and if so, is one better than the other?

Actually, $(3 * 4243) % phi = 8484$; however $d=4243$ is a valid private exponent, because both $(3 * 4243) \bmod (p-1) = 1$ and $(3 * 4243) \bmod (q-1) = 1$

In any case, as I stated in a comment, if there is a valid private exponent, there there are an infinite number of valid private exponents. If $d$ is value, then so is $d + k (p-1)(q-1)/\gcd( p-1, q-1 )$, for any integer $k$.

Since there are an infinite number of valid private exponents, are any of them theoretically better than others?

Cryptographically speaking, they are all equivalent, and so in that sense, no one is any better than any other.

Practically speaking, well, in some rare cases, there may be, but in a surprising number of cases, it doesn't make a difference.

We generally use a CRT optimization when performing RSA private operations; with this, we precompute the values $d_p = d \bmod p-1$ and $d_q = d \bmod q-1$, and those those values exclusively (not referring to $d$ otherwise). And, any valid value of $d$ will give you the exact same value for $d_p, d_q$, and so it doesn't matter which value of $d$ you started with.

In some rare cases, we may use the value of $d$ directly (perhaps we value simplicity over performance, perhaps we don't want the holder of the private key to know the factorization [1].

In that case, computing $C^d \bmod N$ would likely be a bit faster if $d$ where smaller; in that case, the value $d = e^{-1} \bmod \text{lambda}(p-1, q-1)$ might be somewhat preferable...


[1] On the other hand, if someone gets the values of both $d$ and $e$, they can factor, and so there may be little interest in this.

| improve this 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.