I just did some math:

  1. Pick $p$ and $q$ distinct primes;
  2. Calculate $N=p\cdot q$;
  3. Calculate Euler`s totient => $\phi=(p-1)\cdot(q-1)$;
  4. Pick an $e$ (public key), coprime with $\phi$;
  5. Calculate $d$ (private key) which is equal to $e^{-1} \bmod \phi$.

And figured out that $d$ (private key) can be multi-valued:

$$d = (\phi * k + 1) / e$$

This $k$ lets calculate a lot of different $d$`s. And are all of them correct private keys?

Where did I go wrong?

  • 2
    $\begingroup$ I think you're getting yourself confused about modulo math. E^(-1) (mod φ) yields a unique value. Adding (kφ + E^-1) (mod φ) does produce the same result, but that's not the equation you're required to compute. $\endgroup$
    – billc.cn
    Commented Aug 17, 2016 at 22:13
  • $\begingroup$ I'm a bit confused on if the $/e$ in the latter equation is supposed to be regular division, or multiplication by the inverse $e^{-1}$. If division, where did the idea come from? If multiplication with the inverse, there should (trivially) be any number of matching $d = \phi*k*e^{-1} + e^{-1}$ since they are all congruent $mod \space \phi$. $\endgroup$
    – ilkkachu
    Commented Aug 21, 2016 at 14:49

1 Answer 1


You are wrong in assuming that any $(\phi * k + 1) / e$ gives modular inverse of $e$ modulo $\phi$; actually if $e$ and $\phi$ are coprime the modular inverse $d \in [0..\phi-1]$ such that $de = 1 (\mod \phi)$ is unique, and only a single $k \in [0..e-1]$ gives the modular inverse.

As an example consider $(p,q) = (5,11)$, $\phi= 4\cdot 10 = 40$. Let us choose $e=3$, coprime with $\phi$: $gcd(3, 40) = 1$; then $d=e^{-1}(\mod 40) = 27$.

Using your expression:

  • $(k = 0) : 0$ (wrong)
  • $(k = 1) : (40 + 1) / 3 = 13$ (wrong)
  • $(k = 2) : (40\cdot 2 + 1) / 3 = 27$ (got it, $27 * 3 \mod 40 = 1$)

But the choice of decrypting exponent is indeed not unique. To obtain the minimal decrypting exponent one should use $d^\prime=e^{-1}(\mod lcm((p-1),(q-1)))$ instead of $d=e^{-1}(\mod (p-1)(q-1))$. For the above example, $lcm(4,10) = 20$ and $d^\prime=7$, which is less than $d=27$ and so a better (faster) decrypting exponent.

As a sanity check, let us encrypt/decrypt number $8$:

  • encryption: $8^3 \mod 55 = 17$
  • decryption using $d=27$: $17^{27} \mod 55 = 8$
  • decryption using $d^{\prime}=7$: $17^{7} \mod 55 = 8$

Any $d=7+k\cdot 20$ where $k = 0, 1, 2, ..$ is a valid decryption exponent for the above example.

  • $\begingroup$ @kludg: the $de= 1\mod\phi$ in your answer parses literally as $de=(1\bmod\phi)$, that is $de=1$, which (assuming $e>1$) has no integer solution. You perhaps mean $de\equiv1\pmod\phi$, but contrary to the answer's statement this allows multiple $d$ (if $d$ is valid, then $d+\phi$ is). On the other hand, $d=e^{-1}\bmod\phi$, to be parsed as $d=(e^{-1}\bmod\phi)$, does uniquely define $d$. This is not the only working $d$ for RSA though; any $d$ such that $de\equiv1\pmod{\operatorname{LCM}(p-1,q-1)}$ will do. $\endgroup$
    – fgrieu
    Commented Aug 20, 2016 at 15:32
  • $\begingroup$ @fgrieu thank you, you are right, the choice of decrypting exponent $d$ is not unique; the interesting choice though is minimal possible $d$ , since the use of $d=e^{-1}\mod lcm(p-1,q-1)$ instead of $d=e^{-1} \mod \phi(p-1,q-1)$. $d+\phi$ is valid but not interesting. $\endgroup$
    – kludg
    Commented Aug 20, 2016 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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