9
$\begingroup$

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?

$\endgroup$
  • 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 Aug 17 '16 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 Aug 21 '16 at 14:49
7
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\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 Aug 20 '16 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 Aug 20 '16 at 16:01

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.