Is it possible to have multiple RSA private keys? I just did some math:


Pick $p$ and $q$ distinct primes;
Calculate $N=p\cdot q$;
Calculate Euler`s totient => $\phi=(p-1)\cdot(q-1)$;
Pick an $e$ (public key), coprime with $\phi$;
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?
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.