1
$\begingroup$

I understand that the RSA keys $pk$ and $sk$ are choosen such that one is the multiplicative inverse of the other, in $\mod \phi(n)$

But for the encryption and decryption to work, in other words, that

${m^{pk}}^{sk} \mod n = m$

holds, $pk$ and $sk$ must also be multiplicative inverse to each other in $\mod n$, right?

|improve this question
$\endgroup$
  • 1
    $\begingroup$ Why do you think this must be the case? $\endgroup$ – fkraiem Apr 6 '17 at 14:07
  • $\begingroup$ (Of course, this is obviously false; just generate a keypair and you will see that decryption works even though the keys are not inverse modulo $n$.) $\endgroup$ – fkraiem Apr 6 '17 at 14:10
4
$\begingroup$

I understand that the RSA keys $pk$ and $sk$ are chosen such that one is the multiplicative inverse of the other, in $\bmod \phi(n)$

Mostly correct. Actually, they're always multiplicative inverses modulo $\lambda(n) = \phi(n) / \gcd(n)$; selecting them as inverses modulo $\phi(n)$ does work (they will encrypt and decrypt properly), but using the smaller $\lambda(n)$ also works, and yields smaller key values.

$pk$ and $sk$ must also be multiplicative inverse to each other in $\bmod n$, right?

That is wrong; $pk \cdot sk \bmod n$ need not be any specific value; there's no reason it needs to be 1. One trivial example is $n = 85, e = 5, d = 13$; in this case, $e$ is not relatively prime to $n$, hence it doesn't have a multiplicative inverse.

After all, when you look at ${m^{pk}}^{sk} \bmod n$, you're not multiplying by $pk$ or $sk$; you're raising $m$ to the power of $pk, sk$; those are different operations.

|improve this answer
$\endgroup$
  • $\begingroup$ Hmm it looks like I am still misunderstanding something crucial. I mean..${m^{pk}}^{sk}$ is the same as $m^{sk*pk}$, and that must be $m^1$, so $pk * sk$ must be 1, right?This is why I thought pk must be the inverse of sk. $\endgroup$ – user66875 Apr 6 '17 at 14:25
  • $\begingroup$ @user66875: yes, however $m ^ {pk \cdot sk} = m ^ {pk \cdot sk \bmod \lambda(n)}$, and so the idea that they are inverses modulo $\lambda(n)$ already captures that notion... $\endgroup$ – poncho Apr 6 '17 at 14:27
3
$\begingroup$

Theorem. Let $a$ be an element of a finite group $G$ and $b,c$ be integers. Then $a^b = a^c$ in $G$ if and only if $b$ and $c$ are congruent modulo the order of $a$ in $G$ (that is, the smallest positive integer $k$ such that $a^k = 1$).

In the special case where $G$ is the multiplicative groups of integers modulo $n$, the order of $a$ is a divisor of $\varphi(n)$ (the order of the group), thus in order to have $(a^\mathrm{pk})^\mathrm{sk} = a^{\mathrm{pk}\cdot\mathrm{sk}} = a$ it is sufficient to have $\mathrm{pk}\cdot\mathrm{sk} \equiv 1 \pmod{\varphi(n)}$. This does not imply anything about how congruent they are modulo $n$.

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